De Casteljau's algorithm

The de Casteljau's algorithm is a method invented by Paul de Casteljau that uses recursive linear interpolation to find Bézier curves. It is considerably more numerically stable than the formulation using the naïve parametric formulation of the Bézier curves.

The algorithm can be expressed by the recurrence relation

for i = 1, 2, ..., n and j = 0, 1, ..., n-i where P_0,j for j = 0, 1, ..., n are the initial control points.

Example

With three control points

we would have

and

which is the expected quadratic Bézier curve.

Pseudocode example

Here is a pseudo-code example that recursively draws a curve from point P1 to P4, tending towards points P2 and P3. The level parameter is the limiting factor of the recursion. The procedure calls itself recursively with an incremented level parameter. When level reaches the max_level global value, a line is drawn between P1 and P4 at that level. The function midpoint takes two points, and returns the middle point of a line segment between those two points.

   global max_level = 5
   procedure draw_curve(P1, P2, P3, P4, level)
       if (level > max_level)
           draw_line(P1, P4)
       else
           L1 = P1
           L2 = midpoint(P1, P2)
           H  = midpoint(P2, P3)
           R3 = midpoint(P3, P4)
           R4 = P4
           L3 = midpoint(L2, H)
           R2 = midpoint(R3, H)
           L4 = midpoint(L3, R2)
           R1 = L4
           draw_curve(L1, L2, L3, L4, level + 1)
           draw_curve(R1, R2, R3, R4, level + 1)
   end procedure draw_curve