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.^{[citation needed]}

Definition

A Bézier curve ${\displaystyle B}$ (of degree ${\displaystyle n}$, with control points ${\displaystyle \beta _{0},\ldots ,\beta _{n}}$) can be written in Bernstein form as follows

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

where ${\displaystyle b}$ is a Bernstein basis polynomial

${\displaystyle b_{i,n}(t)={n \choose i}(1-t)^{n-i}t^{i}.}$

The curve at point ${\displaystyle t_{0}}$ can be evaluated with the recurrence relation

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

${\displaystyle \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}$

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

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

Moreover, the Bézier curve ${\displaystyle B}$ can be split at point ${\displaystyle t_{0}}$ into two curves with respective control points:

${\displaystyle \beta _{0}^{(0)},\beta _{0}^{(1)},\ldots ,\beta _{0}^{(n)}}$

${\displaystyle \beta _{0}^{(n)},\beta _{1}^{(n-1)},\ldots ,\beta _{n}^{(0)}}$

Geometric interpretation

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

• Consider a Bézier curve with control points ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle t}$.

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 ${\displaystyle t}$, but splits the curve into two pieces at ${\displaystyle 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 ${\displaystyle \mathbf {R} ^{n}}$, we may project the point into ${\displaystyle \mathbf {R} ^{n+1}}$; for example, a curve in three dimensions may have its control points ${\displaystyle \{(x_{i},y_{i},z_{i})\}}$ and weights ${\displaystyle \{w_{i}\}}$ projected to the weighted control points ${\displaystyle \{(w_{i}x_{i},w_{i}y_{i},w_{i}z_{i},w_{i})\}}$. The algorithm then proceeds as usual, interpolating in ${\displaystyle \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.

Notation

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

${\displaystyle {\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

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

into

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

and

${\displaystyle B_{2}(t)=\sum _{i=0}^{n}\beta _{i}^{(n-i)}b_{i,n}\left({\frac {t-t_{0}}{1-t_{0}}}\right)\!,\quad t\in [t_{0},1].}$

Bézier curve

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

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

with

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

we split the Bézier curve into three separate equations

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

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

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

which we evaluate individually using De Casteljau's algorithm.

Example

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

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

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

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

at the point t₀.

We start the recursion with

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

${\displaystyle \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

${\displaystyle {\begin{aligned}\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{aligned}}}$

which is the expected Bernstein polynomial of degree 2.

Implementations

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

Haskell

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

Python

def de_casteljau(t: float, coefs: float) -> float:
    """De Casteljau's algorithm."""
    beta = [c for c in coefs]  # 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]

Java

public double deCasteljau(double t, double[] coefficients) {
    double[] beta = coefficients;
    int n = beta.length;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < (n - i); j++) {
            beta[j] = beta[j] * (1 - t) + beta[j + 1] * t;
        }
    }
    return beta[0];
}

JavaScript

The following function applies De Casteljau's algorithm to an array of points, resolving the final midpoint with the additional properties in and out (for the midpoint's "in" and "out" tangents, respectively).

function deCasteljau(points, position = 0.5) {
	let a, b, midpoints = [];
	while (points.length > 1) {
		const num = points.length - 1;
		for (let i = 0; i < num; ++i) {
			a = points[i];
			b = points[i+1];
			midpoints.push([
				a[0] + ((b[0] - a[0]) * position),
				a[1] + ((b[1] - a[1]) * position),
			]);
		}
		points = midpoints;
		midpoints = [];
	}
	return Object.assign(points[0], {in: a, out: b});
}

The following example calls this function with the green points below, exactly halfway along the curve. The resulting coordinates should equal ${\displaystyle (192,32)}$, or the position of the centremost red point.

{
	/* Definition of deCasteljau() function omitted for brevity */
	const nodes = window.document.querySelectorAll("circle.n0-point");
	const points = Array.from(nodes).map(({cx, cy}) => [cx.baseVal.value, cy.baseVal.value]);
	deCasteljau(points); // Result: [192, 32]
}

See also

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

References

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

External links

• Piecewise linear approximation of Bézier curves – description of De Casteljau's algorithm, including a criterion to determine when to stop the recursion
• Bezier Curves and Picasso — Description and illustration of De Casteljau's algorithm applied to cubic Bézier curves.
• de Casteljau's algorithm - Implementation help and interactive demonstration of the algorithm.