Building Smooth Paths Using Bézier Curves
Last post, we built a super-simple Path
-based interpolator using straight line segments. To produce smoother interpolators, without corners - typically preferred for animating motion - we’ll need correspondingly smooth generating Paths. Our primary goal in this post, then, will be:
- given a sequence of $n$ points in the cartesian plane, calculate a smooth
Path
passing through all points in order.
We’ll start with the simplest possible case, and generalize from there.
$n$ = 2
This one’s a gimme - we can use Path.lineTo(...)
to connect the two given points with a straight line. While not very exciting, this curve does satisfy the smoothness condition since there are definitely no corners!
$n$ > 2
When given more than two distinct points, it’s no longer possible to connect them smoothly using straight lines only1:
We instead need to build our Path
from components with a greater number of degrees of freedom. In particular, we need to be able to specify both the end point positions and one or more derivatives of each component at those end points. That way, we can be sure that the composite curve created by joining together all our components will be smooth at the joins.
Enter Cubic Bézier Curves
Most of you will have played with Bézier curves before in consumer graphics programs. They are usually constructed in two steps:
- fix the locations of the two end points ($P_0$ and $P_3$ in the diagram below);
- position two control points ($P_1$ and $P_2$ in the diagram below) that completely determine the shape of the curve connecting the two end points.
We can append a single cubic Bézier curve to an existing Path
using the Path.cubicTo(...)
method. But how do we make sure that we choose control points that yield a smooth composite curve? In other words, how do we ensure that our composite curve looks like this:
and not like this:
Most of the rest of this post is dedicated to figuring out how to choose the ‘right’ control points for arbitrary given end points (aka knots in Bézier curve lingo). It’s not too hairy - there’s a lot of algebra, sure, but because cubic Bézier curves can be represented as polynomials2, the numbers work out nicely :). The language is fairly formal so that I can refer back to the derivations with confidence in the future. If you’re really not keen on math, you can skip ahead to the results section now.
Notation
Let $\lbrace k_i \in \mathbb{R}^m : i \in 0,\ldots,n \rbrace$ represent a collection of $n+1$ knots.
Let $\Gamma_i$ represent any cubic Bézier curve connecting $k_i$ to $k_{i+1}$ for $i \in 0,\ldots,n-1$. Each $\Gamma_i$ may then be represented by a parametric equation of the form
\[\Gamma_i(t) = (1-t)^3 k_i + 3(1-t)^2 t c_{i,0} + 3(1-t) t^2 c_{i,1} + t^3 k_{i+1}\]where $t$ ranges between $0$ and $1$, and $c_{i,0} \in \mathbb{R}^m$ and $c_{i,1} \in \mathbb{R}^m$ are the intermediate control points that determine the curvature of $\Gamma_i$.
Formal Goal
For any given collection of knots, we aim to compute control points that guarantee the composite curve $\Gamma$ formed by connecting all the individual Bézier curves $\Gamma_i$ satisfies the following conditions:
- $\Gamma$ is twice-differentiable everywhere;
- $\Gamma$ satisfies natural boundary conditions (i.e. $\Gamma’’ = 0$ at each end).
Each $\Gamma_i$ is clearly $ C^\infty $ away from the endpoints $k_i$ and $k_{i+1}$, so the first condition above is equivalent to requiring that $\Gamma$ be twice-differentiable at every knot.
The second condition is applied to fully specify the problem, leading to a unique solution and making calculations simpler.
Derivation
Note that
\[\Gamma_i^{\prime}(t) = 3 \left[ - (1-t)^2 k_i + (3t-1)(t-1) c_{i,0} - t(3t-2) c_{i,1} + t^2 k_{i+1} \right]\]and
\[\Gamma_i^{\prime\prime}(t) = 6 \left[ (1-t) k_i + (3t-2) c_{i,0} - (3t-1) c_{i,1} + t k_{i+1} \right].\]For $\Gamma$ to be $C^2$ at each interior knot, we require that
\[\left.\Gamma_{i-1}^{\prime}\right\vert_{k_{i}} = \left.\Gamma_{i}^{\prime}\right\vert_{k_{i}} \hspace{0.2in} \text{ and } \hspace{0.2in} \left.\Gamma_{i-1}^{\prime\prime}\right\vert_{k_{i}} = \left.\Gamma_{i}^{\prime\prime}\right\vert_{k_{i}}\]for $i \in \lbrace 1,\ldots,n-1 \rbrace$. Substituting the derivative expressions computed above, we see that these equalities are equivalent to choosing control points that satisfy
\[c_{i-1,1} + c_{i,0} = 2k_{i} \text{ for } i \in \lbrace 1,\ldots,n-1 \rbrace\]and
\[c_{i-1,0} - 2c_{i-1,1} = c_{i,1} - 2c_{i,0} \text{ for } i \in \lbrace 1,\ldots,n-1 \rbrace.\]So far, we have $2(n-1)$ constraints for $2n$ control points. The final constraints that will uniquely determine the locations of all control points are the boundary conditions
\[\left.\Gamma_0^{\prime\prime}\right\vert_{k_0} = 0 \hspace{0.2in} \text{ and } \hspace{0.2in} \left.\Gamma_{n-1}^{\prime\prime}\right\vert_{k_n} = 0.\]Equivalently,
\[k_0 - 2c_{0,0} + c_{0,1} = 0\]and
\[c_{n-1,0} - 2c_{n-1,1} + k_n = 0.\]Eliminating $c_{i,1}$ from all these equations gives a system of $n$ equations for $\lbrace c_{i,0} : i \in 0,\ldots,n-1 \rbrace$:
\[c_{i-1,0} + 4 c_{i,0} + c_{i+1,0} = 2(2k_{i} + k_{i+1}) \text{ for } i \in \lbrace 1,\ldots,n-2 \rbrace,\] \[2c_{0,0} + c_{1,0} = k_0 + 2k_1,\] \[2c_{n-2,0} + 7c_{n-1,0} = 8 k_{n-1} + k_n\]Writing these equations in matrix form:
\[\begin{bmatrix} 2 & 1 & 0 & 0 & 0 & \dots & 0 \\ 1 & 4 & 1 & 0 & 0 & \dots & 0 \\ 0 & 1 & 4 & 1 & 0 & \dots & 0 \\ \vdots & \ddots & \ddots & \ddots & \ddots & \ddots & \vdots \\ 0 & \dots & 0 & 1 & 4 & 1 & 0 \\ 0 & \dots & 0 & 0 & 1 & 4 & 1 \\ 0 & \dots & 0 & 0 & 0 & 2 & 7 \end{bmatrix} \begin{bmatrix} c_{0,0} \\ c_{1,0} \\ c_{2,0} \\ \vdots \\ c_{n-3,0} \\ c_{n-2,0} \\ c_{n-1,0} \end{bmatrix} = \begin{bmatrix} k_0 + 2k_1 \\ 2(2k_{1} + k_{2}) \\ 2(2k_{2} + k_{3}) \\ \vdots \\ 2(2k_{n-3} + k_{n-2}) \\ 2(2k_{n-2} + k_{n-1}) \\ 8k_{n-1} + k_{n} \end{bmatrix}\]This tridiagonal system can be solved in linear time using Thomas’ Algorithm, which in this case is guaranteed to be stable since the tridiagonal matrix is diagonally dominant. Once all $c_{i,0}$ are calculated, the remaining control points $\lbrace c_{i,1} : i \in 0,\ldots,n-1 \rbrace$ are given by the following formulae:
\[c_{i,1} = 2k_{i+1} - c_{i+1,0} \text{ for } i \in \lbrace 0,\ldots,n-2 \rbrace,\] \[c_{n-1,1} = \frac{1}{2}\left[ k_n + c_{n-1,0} \right].\]Implementation
The following Android/Java code uses Thomas’ Algorithm to compute appropriate control points and accomplish our original goal:
given a sequence of $n$ points in the cartesian plane, calculate a smooth
Path
passing through all points in order.
Note that the code was written with readability, rather than performance, in mind. EPointF
is a simple 2D point representation that provides some convenient componentwise operations; the definition is given below the main block of code.
Results
To test this implementation, I generated random points inside the square $[0,1]\times[0,1]$ and plotted the corresponding path returned by PolyBezierPathUtil. computePathThroughKnots(...)
. Here are a couple of examples with $n$ = 6 to convince you that everything works as expected:
Further Reading
A pleasing geometrical presentation of composite Bézier curves is provided by these lecture notes from UCLA’s Math 149: Mathematics of Computer Graphics course.
For an interesting application of Bézier curves, see the following technical articles on Square’s blog: Smooth Signatures and Smoother Signatures. Given that written letters often contain sharp corners, I would be interested to know whether Square’s algorithms could generate even better signatures if they were to switch back from cubic interpolation to linear interpolation near high-curvature regions.
-
Excepting the degenerate case in which the $n$ > 2 provided points are colinear. ↩
-
The general (parametric) form of a cubic Bézier curve can be found in the Wikipedia entry on Bézier Curves. ↩