De Casteljau's algorithm


In the mathematical field of numerical analysis, De Casteljau's algorithm is a recursive method to evaluate polynomials in Bernstein form or Bézier curves, named after its inventor Paul de Casteljau. De Casteljau's algorithm can also be used to split a single Bézier curve into two Bézier curves at an arbitrary parameter value.
Although the algorithm is slower for most architectures when compared with the direct approach, it is more numerically stable.

Definition

A Bézier curve B can be written in Bernstein form as follows
where b is a Bernstein basis polynomial
The curve at point t0 can be evaluated with the recurrence relation
Then, the evaluation of at point can be evaluated in operations. The result is given by:
Moreover, the Bézier curve can be split at point into two curves with respective control points:

Example implementation

Here is an example implementation of De Casteljau's algorithm in Haskell:

deCasteljau :: Double -> ->
deCasteljau t = b
deCasteljau t coefs = deCasteljau t reduced
where
reduced = zipWith coefs
lerpP t =
lerp t a b = t * b + * a

Example

We want to evaluate the Bernstein polynomial of degree 2 with the Bernstein coefficients
at the point t0.
We start the recursion with
and with the second iteration the recursion stops with
which is the expected Bernstein polynomial of degree 2.

Bézier curve

When evaluating a Bézier curve of degree n in 3-dimensional space with n+1 control points Pi
with
we split the Bézier curve into three separate equations
which we evaluate individually using De Casteljau's algorithm.

Geometric interpretation

The geometric interpretation of De Casteljau's algorithm is straightforward.
The following picture shows this process for a cubic Bézier curve:
Note that the intermediate points that were constructed are in fact the control points for two new Bézier curves, both exactly coincident with the old one. This algorithm not only evaluates the curve at, but splits the curve into two pieces at, and provides the equations of the two sub-curves in Bézier form.
The interpretation given above is valid for a nonrational Bézier curve. To evaluate a rational Bézier curve in, we may project the point into ; for example, a curve in three dimensions may have its control points and weights projected to the weighted control points. The algorithm then proceeds as usual, interpolating in. The resulting four-dimensional points may be projected back into three-space with a perspective divide.
In general, operations on a rational curve are equivalent to operations on a nonrational curve in a projective space. This representation as the "weighted control points" and weights is often convenient when evaluating rational curves.