De Casteljau algorithm

The de Casteljau algorithm enables efficient calculation of an arbitrarily accurate approximation representation of Bezier curves by a polygon . The algorithm was developed by Paul de Faget de Casteljau at Citroën in the early 1960s .

idea

De Casteljau's algorithm is based on the fact that a Bézier curve can be divided and represented by two adjacent Bézier curves. This subdivision can be continued recursively . The control polygon of the composite Bézier curve approaches the original curve. After a sufficient number of refinement steps, the resulting polygon can be used as an approximation for the original curve. A refinement step, which splits the control polygon of a starting curve into a control polygon of a composite curve, consists of just a few simple divisions of polygon edges.

In addition, the algorithm enables the rapid determination of every single point on the Bézier curve through its parametric representation.

The algorithm is expanded in Blossoming as well as in de Casteljau's focal algorithm.

algorithm

The control points of the output curve are given . ${\displaystyle P_{0},\ P_{1},\ \dots ,\ P_{n}}$ ${\displaystyle C(t)=\sum _{i=0}^{n}B_{i,n}(t)P_{i}}$ ${\displaystyle t\in [0,1]}$

Of the control points of the initial curve, only and generally lie on the curve. In the first step, the algorithm calculates another point on the curve. You can choose freely. The curve is further divided at this point . It is therefore advisable to choose , because this ensures an even distribution and thus a quick approximation of the control polygon to the starting curve. ${\displaystyle C(t)}$ ${\displaystyle P_{0}}$ ${\displaystyle P_{n}}$ ${\displaystyle C(t_{0})}$ ${\displaystyle t_{0}\in {]0,1[}}$ ${\displaystyle C(t_{0})}$ ${\displaystyle t_{0}={\frac {1}{2}}}$

Formation of partial relationships

Construction of the first sequence of auxiliary points Pi (1) from the starting points Pi (0).

Instead of directly inserting into the equation of the curve , the calculation of takes place via the construction of points from the given control points . The construction starts with the starting points . From these, new points are constructed in proportion by dividing the connecting lines . The point is calculated using the intuitive formula: ${\displaystyle t_{0}}$ ${\displaystyle C(t)}$ ${\displaystyle C(t_{0})}$ ${\displaystyle P_{i}^{(k)}}$ ${\displaystyle P_{0},\ \dots \ P_{n}}$ ${\displaystyle P_{i}^{(0)}=P_{i}}$ ${\displaystyle {\overline {P_{i}^{(k)}P_{i+1}^{(k)}}}}$ ${\displaystyle t_{0}\ :\ 1-t_{0}}$ ${\displaystyle P_{i}^{(k+1)}}$ ${\displaystyle P_{i}^{(k+1)}}$

${\displaystyle P_{i}^{(k+1)}=(1-t_{0})\cdot P_{i}^{(k)}+t_{0}\cdot P_{i+1}^{(k)}}$

In the figure opposite, the points that have emerged from the starting points are shown in red. By continuing the calculation rule, points are determined in the same way . To calculate , the blue dashed connecting lines of the points calculated in the first step are divided in the same ratio, etc. ${\displaystyle P_{i}^{(1)}}$ ${\displaystyle P_{i}^{(0)}=P_{i}}$ ${\displaystyle P_{i}^{(2)},\ P_{i}^{(3)},\ \dots ,\ P_{i}^{(n)}}$ ${\displaystyle P_{i}^{(2)}}$ ${\displaystyle {\overline {P_{i}^{(1)}P_{i+1}^{(1)}}}}$

Construction of a curve point

The following statement applies (see proof of the point construction ):

${\displaystyle C(t_{0})=P_{0}^{(n)}}$

Complete construction of P0 (3) for n = 3

This means that the point which is constructed in the tenth iteration by continued segmentation is a point on the curve. The division ratio determines its position on the curve. ${\displaystyle P_{0}^{(n)}}$ ${\displaystyle n}$ ${\displaystyle t_{0}}$

In the illustration opposite, the construction is completely carried out. The point that has arisen from the starting points by applying the division rule three times lies on the curve sought. ${\displaystyle n=3}$ ${\displaystyle P_{0}^{(3)}}$ ${\displaystyle P_{0},\ \dots ,\ P_{3}}$

By far the more interesting statement is that this point divides the curve into two Bézier curves and and that the points form the control polygon of and the points form the control polygon of . ${\displaystyle P_{0}^{(n)}}$ ${\displaystyle C(t)}$ ${\displaystyle C_{1}(t)}$ ${\displaystyle C_{2}(t)}$ ${\displaystyle P_{0}^{(i)}\ (i=0\dots n)}$ ${\displaystyle C_{1}(t)}$ ${\displaystyle P_{i}^{(n-i)}\ (i=0\dots n)}$ ${\displaystyle C_{2}(t)}$

Divide into two Bézier curves

Decomposition of C (t) into C1 (t) and C2 (t)

The illustration on the right shows the breakdown of in and for . The points are , , and the control polygon of and according to the points , , and the control polygon of . ${\displaystyle C(t)}$ ${\displaystyle C_{1}(t)}$ ${\displaystyle C_{2}(t)}$ ${\displaystyle n=3}$ ${\displaystyle P_{0}^{(0)}}$ ${\displaystyle P_{0}^{(1)}}$ ${\displaystyle P_{0}^{(2)}}$ ${\displaystyle P_{0}^{(3)}}$ ${\displaystyle C_{1}(t)}$ ${\displaystyle P_{0}^{(3)}}$ ${\displaystyle P_{1}^{(2)}}$ ${\displaystyle P_{2}^{(1)}}$ ${\displaystyle P_{3}^{(0)}}$ ${\displaystyle C_{2}(t)}$

The figure also shows why a division ratio of is usually used. Since a division ratio smaller than ½ was used in this example, the curve is divided into a short curve and a long curve in an unequal ratio . The shorter part approximates its control polygon much better than the longer one. If you want to achieve a uniform approximation (with approximately the same length of the exit control polygon), the division ratio is suitable . ${\displaystyle t_{0}={\frac {1}{2}}}$ ${\displaystyle C(t)}$ ${\displaystyle C_{1}(t)}$ ${\displaystyle C_{2}(t)}$ ${\displaystyle t_{0}={\frac {1}{2}}}$

The subdivision of the curves is continued until they are approximated with sufficient accuracy by their control polygons.

Pseudocode

At the beginning, the points of the control polygon are in a field . Given the parameter , the point is calculated as follows: ${\displaystyle P_{i},\ i=0\ldots n}$ ${\displaystyle t_{0}}$ ${\displaystyle C(t_{0})}$

BEGIN
    FOR i:=0..n
         ${\displaystyle P_{i}^{(0)}:=P_{i}}$

    FOR j:=1..n
        FOR i:=0..(n-j)
            // Unterteilung mit Faktor t
             ${\displaystyle P_{i}^{(j)}=(1-t_{0})\cdot P_{i}^{(j-1)}+t_{0}\cdot P_{i+1}^{(j-1)}}$ 

    RETURN  ${\displaystyle P_{0}^{(n)}}$
END

The above algorithm is incomplete in that only the point is determined, but no continued subdivision of is performed. The algorithm is not memory efficient because new memory spaces are used for all of them. ${\displaystyle C(t_{0})}$ ${\displaystyle C(t)}$ ${\displaystyle P_{i}^{(j)}}$

Proof of the point construction

The statement that a further point of the curve can be constructed over -fold continued segmentation can be proven by solving the recursion that defines. ${\displaystyle n}$ ${\displaystyle P_{i}^{(j)}}$

Recursion equation

The recursion equation defines the points depending on the points calculated in the last iteration . The recursion starts with the following points : ${\displaystyle P_{i}^{(k)}}$ ${\displaystyle P_{i}^{(k-1)}}$ ${\displaystyle P_{i}}$

${\displaystyle P_{i}^{(0)}=P_{i}}$

${\displaystyle P_{i}^{(k)}=(1-t_{0})\cdot P_{i}^{(k-1)}+t_{0}\cdot P_{i+1}^{(k-1)}}$

Statement to be proven

The statement that the point is a point on the curve at the point has to be proven : ${\displaystyle P_{0}^{(n)}}$ ${\displaystyle t_{0}}$

${\displaystyle P_{0}^{(n)}=C(t_{0})}$

Generalization of the statement

In order to find a solution to the recursion for the special point , a closed form is sought for all points of the recursion and it is shown that this provides in particular for the result sought. The proof for is given via complete induction with the following induction hypothesis: ${\displaystyle P_{0}^{(n)}}$ ${\displaystyle P_{i}^{(k)}}$ ${\displaystyle P_{0}^{(n)}}$ ${\displaystyle P_{i}^{(k)}}$

${\displaystyle P_{i}^{(k)}=\sum _{m=0}^{k}P_{i+m}{k \choose m}t_{0}^{m}(1-t_{0})^{k-m}}$.

The induction step is then a straight-line calculation, in which statements about binomial coefficients are used.

application

With the help of de Casteljau's algorithm, it is possible to approximate Bézier curves using straight lines. This allows a Bézier curve to be drawn efficiently with the computer.

Web links

• De Casteljau polygons and Bezier curve (applet)
• De Casteljau Bezier curve (applet, English)
• Kaspar Fischer: Piecewise Linear Approximation of Bézier Curves. (PDF, English)