Following the construction of a Bézier curve, the next important task is to find the point C(u) on the curve for a particular u. A simple way is to plug uinto every basis function, compute the product of each basis function and its corresponding control point, and finally add them together. While this works fine, it is not numerically stable (i.e., could introduce numerical errors during the course of evaluating the Bernstein polynomials).
In what follows, we shall only write down the control point numbers. That is, the control points are 00 for P0, 01 for P1, …, 0i for Pi, …, 0n for Pn. The 0s in these numbers indicate the initial or the 0-th iteration. Later on, it will be replaced with 1, 2, 3 and so on.
The fundamental concept of de Casteljau’s algorithm is to choose a point C in line segment AB such that C divides the line segment AB in a ratio of u:1-u(i.e., the ratio of the distance between A and C and the distance between A and B is u). Let us find a way to determine the point C.
The idea of de Casteljau’s algorithm goes as follows. Suppose we want to find C(u), where u is in [0,1]. Starting with the first polyline, 00-01-02-03…-0n, use the above formula to find a point 1i on the leg (i.e. line segment) from 0i to 0(i+1) that divides the line segment 0i and 0(i+1) in a ratio of u:1-u. In this way, we will obtain n points 10, 11, 12, …., 1(n-1). They define a new polyline of n – 1 legs.
The new points are numbered as 1i‘s. Apply the procedure to this new polyline and we shall get a second polyline of n – 1 points 20, 21, …, 2(n-2) and n– 2 legs. Starting with this polyline, we can construct a third one of n – 2 points 30, 31, …, 3(n-3) and n – 3 legs. Repeating this process n times yields a single point n0. De Casteljau proved that this is the point C(u) on the curve that corresponds to u.
Let us continue with the above figure. Let 20 be the point in the leg of 10 and 11 that divides the line segment 10 and 11 in a ratio of u:1-u. Similarly, choose 21 on the leg of 11 and 12, 22 on the leg of 12 and 13, and 23 on the leg of 13 and 14. This gives a third polyline defined by 20, 21, 22 and 23. This third polyline has 4 points and 3 legs. Keep doing this and we shall obtain a new polyline of three points 30, 31 and 32. From this fourth polyline, we have the fifth one of two points 40 and 41. Do it once more, and we have 50, the point C(0.4) on the curve.
This is the geometric interpretation of de Casteljau’s algorithm, one of the most elegant result in curve design.
Given the above geometric interpretation of de Casteljau’s algorithm, we shall present a computation method, which is shown in the following figure.
Thus, from the initial column, column 0, we compute column 1; from column 1 we obtain column 2 and so on. Eventually, after n applications we shall arrive at a single point n0 and this is the point on the curve. The following algorithm summarizes what we have discussed. It takes an array P of n+1 points and au in the range of 0 and 1, and returns a point on the Bézier curve C(u).
Input: array P[0:n] of n+1 points and real number u in [0,1]
Output: point on curve, C(u)
Working: point array Q[0:n]
for i := 0 to n do
Q[i] := P[i]; // save input
for k := 1 to n do
for i := 0 to n – k do
Q[i] := (1 – u)Q[i] + u Q[i + 1];
A Recurrence Relation
The above computation can be expressed recursively. Initially, let P0,j be Pj for j = 0, 1, …, n. That is, P0,j is the j-th entry on column 0. The computation of entry j on column i is the following:
if i = 0 then
return (1-u)* deCasteljau(i-1,j) + u* deCasteljau(i-1,j+1)
This procedure looks simple and short; however, it is extremely inefficient. Here is why. We start with a call to deCasteljau(n,0) for computing Pn,0. Theelse part splits this call into two more calls, deCasteljau(n-1,0) for computing Pn-1,0 and deCasteljau(n-1,1) for computing Pn-1,1.
if n = 0 or n = 1 then
return Fibonacci (n-1) + Fibonacci (n-2)
This program takes an exponential number of function calls (an exercise) to compute Fibonacci(n). Therefore, the above recursive version of de Casteljau’s algorithm is not suitable for direct implementation, although it looks simple and elegant!
An Interesting Observation
The triangular computation scheme of de Casteljau’s algorithm offers an interesting observation. Take a look at the following computation on a Bézier curve of degree 7 defined by 8 control points 00, 01, …, 07. Let us consider a set of consecutive points on the same column as the control points of a Bézier curve. Then, given a u in [0,1], how do we compute the corresponding point on this Bézier curve? If de Casteljau’s algorithm is applied to these control points, the point on the curve is the opposite vertex of the equilateral’s base formed by the selected points!
By the same reason, 70 is the point on the Bézier curve defined by control points 60 and 61. It is also the point on the curve defined by 50, 51 and 52, and on the curve defined by 40, 41, 42 and 43. In general, if we select a point and draw an equilateral as shown above, the base of this equilateral consists of the control points from which the selected point is computed.