de Casteljau's algorithm

In the mathematical subfield of numerical analysis the de Casteljau's algorithm, named after its inventor Paul de Casteljau, is a recursive method to evaluate polynomials in Bernstein form or Bézier curves. The 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 numerically more stable.

Definition

Given a polynomial B in Bernstein form of degree n

B(t)=\sum _{i=0}^{n}\beta _{i}b_{i,n}(t),

where b is a Bernstein basis polynomial, the polynomial at point t<in>0</in> can be evaluated with the recurrence relation

\beta _{i}^{(0)}:=\beta _{i}{\mbox{ , }}i=0,\ldots ,n

\beta _{i}^{(j)}:=\beta _{i}^{(j-1)}(1-t_{0})+\beta _{i+1}^{(j-1)}t_{0}{\mbox{ , }}i=0,\ldots ,n-j{\mbox{ , }}j=1,\ldots n

with

B(t_{0})=\beta _{0}^{(n)}

.

Notes

When doing the calculation by hand it is useful to write down the coefficients in a triangle scheme as

{\begin{matrix}\beta _{0}&=\beta _{0}^{(0)}&&&\\&&\beta _{0}^{(1)}&&\\\beta _{1}&=\beta _{1}^{(0)}&&&\\&&&\ddots &\\\vdots &&\vdots &&\beta _{0}^{(n)}\\&&&&\\\beta _{n-1}&=\beta _{n-1}^{(0)}&&&\\&&\beta _{n-1}^{(1)}&&\\\beta _{n}&=\beta _{n}^{(0)}&&&\\\end{matrix}}

When choosing a point t₀ to evaluate a Bernstein polynomial we can use the two diagonals of the triangle scheme to construct a division of the polynomial

B(t)=\sum _{i=0}^{n}\beta _{i}^{(0)}b_{i,n}(t){\mbox{ , }}\qquad t\in [0,1]

into

B_{1}(t)=\sum _{i=0}^{n}\beta _{0}^{(i)}b_{i,n}\left({\frac {t}{t_{0}}}\right){\mbox{ , }}\qquad t\in [0,t_{0}]

and

B_{2}(t)=\sum _{i=0}^{n}\beta _{n-i}^{(i)}b_{i,n}\left({\frac {t-t_{0}}{1-t_{0}}}\right){\mbox{ , }}\qquad t\in [t_{0},1]

Example

We want to evaluate the Bernstein polynomial of degree 2 with the Bernstein coefficients

\beta _{0}^{(0)}=\beta _{0}

\beta _{1}^{(0)}=\beta _{1}

\beta _{2}^{(0)}=\beta _{2}

at the point t₀.

We start the recursion with

\beta _{0}^{(1)}=\beta _{0}^{(0)}(1-t_{0})+\beta _{1}^{(0)}t_{0}=\beta _{0}(1-t_{0})+\beta _{1}t_{0}

\beta _{1}^{(1)}=\beta _{1}^{(0)}(1-t_{0})+\beta _{2}^{(0)}t_{0}=\beta _{1}(1-t_{0})+\beta _{2}t_{0}

and with the second iteration the recursion stops with

{\begin{matrix}\beta _{0}^{(2)}&=&\beta _{0}^{(1)}(1-t_{0})+\beta _{1}^{(1)}t_{0}\\\ &=&\beta _{0}(1-t_{0})(1-t_{0})+\beta _{1}t_{0}(1-t_{0})+\beta _{1}(1-t_{0})t_{0}+\beta _{2}t_{0}t_{0}\\\ &=&\beta _{0}(1-t_{0})^{2}+\beta _{1}2t_{0}(1-t_{0})+\beta _{2}t_{0}^{2}\\\end{matrix}}

which is the expected Bernstein polynomial of degree n.

Bézier curve

When evaluating a Bézier curve of degree n in 3 dimensional space with n+1 control points P_i

\mathbf {B} (t)=\sum _{i=0}^{n}\mathbf {P} _{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]

with

\mathbf {P} _{i}:={\begin{pmatrix}x_{i}\\y_{i}\\z_{i}\end{pmatrix}}

.

we split the Bézier curve into three separate equations

B_{1}(t)=\sum _{i=0}^{n}x_{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]

B_{2}(t)=\sum _{i=0}^{n}y_{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]

B_{3}(t)=\sum _{i=0}^{n}z_{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]

which we evaluate individually using de Casteljau's algorithm.

Geometric interpretation

The geometric interpretation of de Casteljau algorithm is straightforward.

Consider a Bézier curve with control points $P_{0},...,P_{n}$ . Connecting the consecutive points we create the control polygon of the curve.
Subdivide now each line segment of this polygon with the ratio t:1-t and connect the points you get. This way you arrive at the new polygon having one less segment.
Repeat the process till you arrive at the single point - this is the point of the curve corresponding to the parameter $t$ .

The following picture shows this process for a cubic Bézier curve:

References

Farin, Gerald & Hansford, Dianne (2000). The Essentials of CAGD. Natic, MA: A K Peters, Ltd. ISBN 1-56881-123-3