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.
The algorithm is numerically stable[1] when compared to direct evaluation of polynomials.
The computational complexity of this algorithm is
) can be written in Bernstein form as follows
is a Bernstein basis polynomial
can be evaluated with the recurrence relation
into two curves with respective control points:
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
; for example, a curve in three dimensions may have its control points
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 (or surface) 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.
When doing the calculation by hand it is useful to write down the coefficients in a triangle scheme as
When choosing a point t0 to evaluate a Bernstein polynomial we can use the two diagonals of the triangle scheme to construct a division of the polynomial
When evaluating a Bézier curve of degree n in 3-dimensional space with n + 1 control points Pi
we split the Bézier curve into three separate equations
which we evaluate individually using De Casteljau's algorithm.
which is the expected Bernstein polynomial of degree 2.
Here are example implementations of De Casteljau's algorithm in various programming languages.
The following JavaScript function applies De Casteljau's algorithm to an array of control points or poles as originally named by De Casteljau to reduce them one by one until reaching a point in the curve for a given t between 0 for the first point of the curve and 1 for the last one For example, returns the array which yields the points and segments plotted below:
