De Casteljau's algorithm

From Wikipedia, the free encyclopedia

The correct title of this article is de Casteljau's algorithm. The initial letter is shown capitalized due to technical restrictions.

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.

Although the algorithm is slower for most architectures when compared with the direct approach it is numerically more stable.

1 Definition
2 Notes
3 Example
4 Bézier curve
5 Geometrical interpretation
6 References
7 See also

[edit] 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₀ 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)}$ .

[edit] 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) \qquad \mbox{ , } \in [0,1]$

into

$B_1(t) = \sum_{i=0}^n \beta_0^{(i)} b_{i,n}\left(\frac{t}{t_0}\right) \qquad \mbox{ , } \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) \qquad \mbox{ , } \in [t_0,1]$

[edit] 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.

[edit] 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.

[edit] Geometrical 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: