Bézier curves and Hilbert curves have something important in common: they can both be defined recursively. Similar to the way a Hilbert curve consists of multiple smaller Hilbert curves of lower order, a Bézier curve can be subdivided into multiple smaller Bézier curves with different control points.
One way to perform this subdivision is an elegant algorithm known as de Casteljau’s algorithm. This algorithm constructs points on a Bézier curve geometrically — without evaluating the polynomial in Eq. (4.2) — by repeatedly
averaging the four control points \(\vec {p}_0, \dots , \vec {p}_3\). In the first step we take each pair of adjacent control points and compute their average:
As illustrated in Fig. 4.6, this final point lies on the Bézier curve; in fact, it is easy to show that we have \(\vec {s}=\vec {B}(1/2)\) (see Exercise 4.8).
Figure 4.6 De Casteljau’s algorithm repeatedly averages the control points of a given Bézier curve to produce a single point \(\vec {s}\) that splits the curve in the middle. The left and right half of the curve are also Bézier curves.
The point \(\vec {s}\) splits the original curve into two halves, \(\vec {B}_1(t)\) and \(\vec {B}_2(t)\), both of which are Bézier curves in their own right. As suggested by Fig. 4.6, the control points of the first half are
\(\vec {p}_0\), \(\vec {q}_0\), \(\vec {r}_0\), and \(\vec {s}\), and those of the second half are \(\vec {s}\), \(\vec {r}_1\), \(\vec {q}_2\), and \(\vec {p}_3\), so we have
The split() method in Listing 4.4 uses this equation to split a given BezierCurve
into two halves.
Listing 4.4ch4β―/β―BezierCurve
// Split Bézier curve in the middle, producing two smaller curves.
public BezierCurve[] split() {
Point q0 = mid(p0, p1), q1 = mid(p1, p2), q2 = mid(p2, p3);
Point r0 = mid(q0, q1), r1 = mid(q1, q2);
Point s = mid(r0, r1);
return new BezierCurve[]{
new BezierCurve(p0, q0, r0, s),
new BezierCurve(s, r1, q2, p3)};
}
// Compute the midpoint of a and b.
static Point mid(Point a, Point b) {
return Point.lerp(a, b, 0.5);
}
Of course, we can apply de Casteljau’s algorithm repeatedly and thereby subdivide the original Bézier curve into 4, 8, 16, and ultimately as many pieces as we like. This is the essence of de Casteljau’s algorithm: a procedure for splitting Bézier curves into a hierarchy of smaller
Bézier curves (Fig. 4.7).
Figure 4.7 Repeated application of de Casteljau’s algorithm. Each step produces a finer subdivision by doubling the number of curve segments. Notice also how the control points contract and move towards the curve itself.
Adaptive Subdivision
The main benefit of de Casteljau’s algorithm isn’t that it lets us compute a certain number of points on a Bézier curve — we could already do that before — but that each curve segment it produces is a Bézier curve in its own right. In this section, we first develop a simple test to
determine whether a Bézier curve is approximately straight and then use this test guide the subdivision process so that only curve segments that aren’t already straight enough are subdivided further. This idea is known as adaptive subdivision.
How do we test the straightness of a Bézier curve? A simple criterion is based on the following observation: If the inner control points \(\vec {p}_1\) and \(\vec {p}_2\) lie at \(1/3\) and \(2/3\) of the distance between the two end points \(\vec {p}_0\) and \(\vec
{p}_3\), it can be shown that the resulting Bézier curve is mathematically identical to a line segment (see Exercise 4.8). We can therefore consider a Bézier curve almost straight if the first control point \(\vec {p}_1\) is
close to \(\lerp (\vec {p}_0, \vec {p}_3, 1/3)\) and the second control point \(\vec {p}_2\) is close to \(\lerp (\vec {p}_0, \vec {p}_3, 2/3)\), which means that their distance is less than a given tolerance \(T\):
By setting \(T\) to a sufficiently small value, say, a value that is smaller than the size of a pixel, we can distinguish between curve segments that are visually indistinguishable from a line segment and segments that need further subdivision.
By combining this straightness test with de Casteljau’s subdivision algorithm, we can write a function subdivide() that recursively subdivides a Bézier curve until all segments satisfy the straightness
criterion in Eq. (4.6); see Listing 4.5. The parameter tolerance specifies the desired level of
straightness and corresponds to the parameter \(T\) in Eq. (4.6). The function produces a sequence of points on the curve and adds them to the final argument result.
The function first uses isStraight() to test whether the current curve must be subdivided further. If the current curve segment is sufficiently straight, subdivide() stops the subdivision process and appends the end point of the current segment p3 to the list of points. Otherwise, it splits the curve in half using de Casteljau’s algorithm and recursively calls itself to further
subdivide the two halves.
You may be wondering why subdivide() only adds the second end point p3 of each straight segment to result and not the starting point p0. The reason is
that adding both points would cause every interior point on the curve to be added twice to result since the end point of the each segment is the starting point of the next. Adding only the second end point solves the problem of duplicates, but it also omits the starting point of the entire curve.
This can be easily remedied by manually adding this point right before starting the subdivision process, as shown in Listing 4.6.
Listing 4.6ch4β―/β―BezierCurve
public List<Point> draw(double tolerance) {
List<Point> result = new ArrayList<>();
result.add(p0);
subdivide(tolerance, result);
return result;
}
The images in Fig. 4.8 illustrate how the straightness tolerance influences the final subdivision of a given Bézier curve. For \(T=1\), we obtain four line segments which corresponds to two applications of Casteljau’s algorithm,
but as we decrease the value of \(T\), additional points on the curve are generated to produce a finer subdivision. Notice that decreasing the tolerance always produces a refinement of the previous subdivision: More points are added in certain parts of the curve as necessary, but existing points are
never removed. It’s also easy to see that the subdivision is indeed adaptive, so the point density is highest in regions where the curve is strongly bent.
Figure 4.8 Adaptive subdivision of Bézier curves. The straightness tolerance T measures how much the curve segments are allowed to deviate from a straight line. Smaller tolerance produces finer subdivisions.
There is one important question we haven’t addressed yet: With this straightness test, can we be sure that the subdivision process always terminates, or are there any Bézier curves that can be subdivided endlessly, without ever being considered straight enough? Fortunately, Bézier curves are sufficiently
well-behaved that this cannot happen. Every time we split a Bézier curve into two smaller segments, the control points of the new curves move closer together (and closer to the curve itself) because they are computed by averaging the old control points; this effect can be easily observed in Fig. 4.7. For every fixed tolerance \(T\), the conditions in Eq. (4.6) must therefore be satisfied after a finite number of
iterations.
Exercises
\(\star \) Exercise 4.3.How do we prove that the two Bézier curves in Eq. (4.5) together form the original curve \(\vec {B}(t)\)? The key is to realize that the first half of the original curve can be written as \(\vec {B}(t/2)\) and the second half as \(\vec {B}(t/2 + 1/2)\). We then have to show that
Complete the proof by expanding both sides of these equations using Eq. (4.2) for \(\vec {B}(t)\) and Eq. (4.5) for \(\vec {B}_1(t)\) and \(\vec {B}_2(t)\).
Exercise 4.4.Modify de Casteljau’s algorithm to compute the approximate length of a Bézier curve.
