Following the construction of a Bézier curve, the next important job is to find the point p(u) on the curve given a particular u. A simple way is expanding the Bézier curve definition into a conventional form f(u) = ( f(u), g(u), h(u) ) (see Exercise) and plugging a particular u into this equation to obtain f(u). While it works, this method is not numerically stable (i.e., numerical errors will be introduced during the course of evaluating the polynomials). De Casteljau's elegant algorithm is designed for this purpose.
In what follows, we shall only write down the number of control points. That is, the control points are 00 for p0, 01 for p1, ..., 0i for pi, ..., 0n for pn. The first 0 in these numbers means 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 choosing a point C in line segment AB such that the distance between A and C and the distance between A and B has a given ratio, say u. Let us find a way to determine point C.
The vector from A to B is B - A. Since u is a ratio in the range of 0 and 1, point C is located at u(B - A). Taking the position of A into consideration, point C is A + u(B - A) = (1 - u)A + uB. Therefore, given a u, (1 - u)A + uB is the point between A and B such that the distance between it and A and the distance between A and B has a ratio u.
The idea of de Casteljau's algorithm goes as follows. Suppose we want to find p(u), where u is in [0,1]. Starting with the first polyline, 00-01-02-03...-0n, on each leg (i.e. line segment) from 0i to 0(i+1), use the above formula to find a point 1i such that the distance between 0i and 1i and the distance between 0i and 0(i+1) is u. In this way, we will obtain n points. These new points are 10, 11, 12, ...., 1(n-1). They define a new polyline of n - 1 legs.
In the figure above, u is 0.4. 10 is in the leg of 00 and 01, 11 is in the leg of 01 and 02, ..., and 14 is in the leg of 04 and 05. All of these new points are in blue.
Now the new points are numbered as 1i. 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 will yield a single point n0. De Casteljau proved that this is the point p(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 such that the distance between 10 and 20 and the distance between 10 and 11 has a ratio u. Similarly, choose 21 on the leg of 11 and 12, 22 on the leg of 12, and 23 on the leg of 13 and 14. This will yield a third polyline defined by 20, 21, 22 and 23. This third polyline has n - 1 points and n - 2 legs. Keep doing this, we shall obtain a new polyline of three points 30, 31 and 32. Then, from this fourth polyline, we have the fifth one of two points 40 and 41. Do it once more, we have 50, the point p(0.4) on the curve.
This is the geometric interpretation of de Casteljau's algorithm, one of the most elegant result in curve design.
First, all given control points are arranged into a column, which is the left-most column in the figure. For each pair of adjacent control points, draw a south-east arrow and a north-east arrow and at their intersection write down a new point. For example, if the two adjacent points are ij and i(j+1), the new point is (i+1)j. The south-east (resp., north-east) arrow means multiplying 1 - u (resp., u) to the point at its tail, ij (resp., i(j+1)), and the new point is the sum.
Thus, from the initial column, column 0, one computes 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 above. It takes an array p of n+1 point and a u in the range of 0 and 1, and returns a point on the Bézier curve p(u).