de Casteljau's algorithm

A Bézier curve $B$ (of degree $n$, with control points $\backslash beta\_0,\; \backslash ldots,\; \backslash beta\_n$) can be written in Bernstein form as follows

$$B(t)\; =\; \backslash sum\_\{i=0\}^\{n\}\backslash beta\_\{i\}b\_\{i,n\}(t),$$

where $b$ is a Bernstein basis polynomial

$$b\_\{i,n\}(t)\; =\; \{n\; \backslash choose\; i\}(1-t)^\{n-i\}t^i.$$

The curve at point $t\_0$ can be evaluated with the recurrence relation

$$\backslash begin\{align\}$$

\beta_i^{(0)} &:= \beta_i, && i=0,\ldots,n \\

\beta_i^{(j)} &:= \beta_i^{(j-1)} (1-t_0) + \beta_{i+1}^{(j-1)} t_0, && i = 0,\ldots,n-j,\ \ j= 1,\ldots,n

\end{align}

Then, the evaluation of $B$ at point $t\_0$ can be evaluated in $\backslash binom\{n\}\{2\}$ operations. The result $B(t\_0)$ is given by

$$B(t\_0)\; =\; \backslash beta\_0^\{(n)\}.$$

Moreover, the Bézier curve $B$ can be split at point $t\_0$ into two curves with respective control points:

$$\backslash begin\{align\}$$

&\beta_0^{(0)},\beta_0^{(1)},\ldots,\beta_0^{(n)} \\[1ex]

&\beta_0^{(n)},\beta_1^{(n-1)},\ldots,\beta_n^{(0)}

\end{align}

The geometric interpretation of De Casteljau's algorithm is straightforward.

• Consider a Bézier curve with control points $P\_0,\; \backslash dots,\; 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 fewer segment.
• Repeat the process until 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:

Image:DeCasteljau1.svg

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 $t$, but splits the curve into two pieces at $t$, 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 $\backslash mathbf\{R\}^n$, we may project the point into $\backslash mathbf\{R\}^\{n+1\}$; for example, a curve in three dimensions may have its control points $\backslash \{(x\_i,\; y\_i,\; z\_i)\backslash \}$ and weights $\backslash \{w\_i\backslash \}$ projected to the weighted control points $\backslash \{(w\_ix\_i,\; w\_iy\_i,\; w\_iz\_i,\; w\_i)\backslash \}$. The algorithm then proceeds as usual, interpolating in $\backslash mathbf\{R\}^4$. 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

\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)\; =\; \backslash sum\_\{i=0\}^n\; \backslash beta\_i^\{(0)\}\; b\_\{i,n\}(t),\; \backslash quad\; t\; \backslash in\; [0,1]$$

into

$$B\_1(t)\; =\; \backslash sum\_\{i=0\}^n\; \backslash beta\_0^\{(i)\}\; b\_\{i,n\}\backslash left(\backslash frac\{t\}\{t\_0\}\backslash right)\backslash !,\; \backslash quad\; t\; \backslash in\; [0,t\_0]$$

and

$$B\_2(t)\; =\; \backslash sum\_\{i=0\}^n\; \backslash beta\_i^\{(n-i)\}\; b\_\{i,n\}\backslash left(\backslash frac\{t-t\_0\}\{1-t\_0\}\backslash right)\backslash !,\; \backslash quad\; t\; \backslash in\; [t\_0,1].$$

File:Bézier 2 big.gif

File:Bezier cubic anim.gif

File:Bezier forth anim.gif

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

$$\backslash mathbf\{B\}(t)\; =\; \backslash sum\_\{i=0\}^\{n\}\; \backslash mathbf\{P\}\_i\; b\_\{i,n\}(t),\backslash \; t\; \backslash in\; [0,1]$$

with

$$\backslash mathbf\{P\}\_i\; :=\; \backslash begin\{pmatrix\}\; x\_i\; \backslash \backslash \; y\_i\; \backslash \backslash \; z\_i\; \backslash end\{pmatrix\},$$

we split the Bézier curve into three separate equations

$$\backslash begin\{align\}$$

B_1(t) &= \sum_{i=0}^{n} x_i b_{i,n}(t), & t \in [0,1] \\[1ex]

B_2(t) &= \sum_{i=0}^{n} y_i b_{i,n}(t), & t \in [0,1] \\[1ex]

B_3(t) &= \sum_{i=0}^{n} z_i b_{i,n}(t), & t \in [0,1]

\end{align}

which we evaluate individually using De Casteljau's algorithm.

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

$$\backslash begin\{align\}$$

\beta_0^{(0)} &= \beta_0 \\[1ex]

\beta_1^{(0)} &= \beta_1 \\[1ex]

\beta_2^{(0)} &= \beta_2

\end{align}

at the point t₀.

We start the recursion with

$$\backslash begin\{align\}$$

\beta_0^{(1)} &&=&& \beta_0^{(0)} (1-t_0) + \beta_1^{(0)}t_0 &&=&& \beta_0(1-t_0) + \beta_1 t_0 \\[1ex]

\beta_1^{(1)} &&=&& \beta_1^{(0)} (1-t_0) + \beta_2^{(0)}t_0 &&=&& \beta_1(1-t_0) + \beta_2 t_0

\end{align}

and with the second iteration the recursion stops with

$$\backslash begin\{align\}$$

\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{align}

which is the expected Bernstein polynomial of degree 2.

Here are example implementations of De Casteljau's algorithm in various programming languages.

deCasteljau :: Double -> [(Double, Double)] -> (Double, Double)

deCasteljau t [b] = b

deCasteljau t coefs = deCasteljau t reduced

where

reduced = zipWith (lerpP t) coefs (tail coefs)

lerpP t (x0, y0) (x1, y1) = (lerp t x0 x1, lerp t y0 y1)

lerp t a b = t * b + (1 - t) * a

def de_casteljau(t: float, coefs: list[float]) -> float:

"""De Casteljau's algorithm."""

beta = coefs.copy() # values in this list are overridden

n = len(beta)

for j in range(1, n):

for k in range(n - j):

beta[k] = beta[k] * (1 - t) + beta[k + 1] * t

return beta[0]

public double deCasteljau(double t, double[] coefficients) {

double[] beta = coefficients;

int n = beta.length;

for (int i = 1; i < n; i++) {

for (int j = 0; j < (n - i); j++) {

beta[j] = beta[j] * (1 - t) + beta[j + 1] * t;

}

}

return beta[0];

}

The following JavaScript function applies De Casteljau's algorithm to an array of control points or [https://www.sciencedirect.com/science/article/pii/S0167839624000128 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

function crlPtReduceDeCasteljau(points, t) {

let retArr = [ points.slice () ];

while (points.length > 1) {

let midpoints = [];

for (let i = 0; i+1 < points.length; ++i) {

let ax = points[i][0];

let ay = points[i][1];

let bx = points[i+1][0];

let by = points[i+1][1];

// a * (1-t) + b * t = a + (b - a) * t

midpoints.push([

ax + (bx - ax) * t,

ay + (by - ay) * t,

]);

}

retArr.push (midpoints)

points = midpoints;

}

return retArr;

}

For example,

var poles = [ [0, 128], [128, 0], [256, 0], [384, 128] ]

crlPtReduceDeCasteljau (poles, .5)

returns the array

[ [ [0, 128], [128, 0], [256, 0], [384, 128 ] ],

[ [64, 64], [192, 0], [320, 64] ],

[ [128, 32], [256, 32]],

[ [192, 32]],

]

which yields the points and segments plotted below:

File:Recursive Linear Interpolation.svg

• Bézier curves
• De Boor's algorithm
• Horner scheme to evaluate polynomials in monomial form
• Clenshaw algorithm to evaluate polynomials in Chebyshev form

{{Reflist}}

• {{ cite book | last1 = Farin | first1 = Gerald E. | last2 = Hansford | first2 = Dianne | author2-link = Dianne Hansford | title = The Essentials of CAGD |date = 2000 | publisher = A.K. Peters | isbn = 978-1-56881-123-9 | location = Natick, MA }}

• [http://hcklbrrfnn.wordpress.com/2012/08/20/piecewise-linear-approximation-of-bezier-curves/ Piecewise linear approximation of Bézier curves] – description of De Casteljau's algorithm, including a criterion to determine when to stop the recursion
• [http://jeremykun.com/2013/05/11/bezier-curves-and-picasso/ Bézier Curves and Picasso ] — Description and illustration of De Casteljau's algorithm applied to cubic Bézier curves.
• [https://pomax.github.io/bezierinfo/#decasteljau de Casteljau's algorithm] - Implementation help and interactive demonstration of the algorithm.

Category:Splines (mathematics)

Category:Numerical analysis

Category:Articles with example Haskell code