TOPICS
Search

de Casteljau Algorithm


The de Casteljau algorithm evaluates a polynomial in Bernstein form by repeatedly interpolating between adjacent coefficients. Given

 p(t)=sum_(i=0)^nb_iB_(i,n)(t),
(1)

where B_(i,n)(t) is a Bernstein polynomial, set b_i^((0))=b_i and compute

 b_i^((r))=(1-t)b_i^((r-1))+tb_(i+1)^((r-1))
(2)

for r=1, ..., n and i=0, ..., n-r. Then

 p(t)=b_0^((n)).
(3)

Expanding the recursion gives the Bernstein weights (n; i)(1-t)^(n-i)t^i.

With vector control points in place of scalar coefficients, the construction evaluates a Bézier curve. At a fixed parameter 0<t<1, the first point of each successive level, in level order, gives the control points of the portion from 0 to t. The last point of each level, in reverse level order, gives the control points of the portion from t to 1. Each portion is parametrized over [0,1] using its new control points (Farin 1993).


See also

Bernstein Polynomial, Bézier Curve

Explore with Wolfram|Alpha

References

Farin, G. "The de Casteljau Algorithm." Ch. 5 in Curves and Surfaces for Computer Aided Geometric Design, 3rd ed. San Diego, CA: Academic Press, pp. 29-40, 1993. https://doi.org/10.1016/B978-0-12-249052-1.50008-8.

Cite this as:

Weisstein, Eric W. "de Casteljau Algorithm." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/deCasteljauAlgorithm.html

Subject classifications