De Casteljau's algorithm

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

• 4.1 recurrence equation
• 4.2 to be proved statement
• 4.3 Generalization of the statement

Idea

The algorithm of de Casteljau based on the fact that a Bezier curve can be divided and represented by two adjacent Bezier curves set. This division may be continued recursively. The control polygon of the composite Bezier curve comes closer to the original curve. After a sufficient number of refinement steps, the resulting polyline can be used as an approximation of the original curve. A refinement step that separates the control polygon of an output curve in a control polygon of a composite curve consists only of a few simple divisions of polygon edges.

Moreover, the algorithm allows the rapid determination of each point on the Bezier curve by its parametric representation.

Extensions is the algorithm Blossoming as well as in focal algorithm of de Casteljau.

Algorithm

Where are the control points of the original curve.

Of the control points of the output curve, and are generally only on the curve. The algorithm calculates in a first step a further point of the curve. It can be chosen freely. , The curve is divided at this point in the following. It therefore offers the choice of location, because that ensures a uniform distribution and thus a fast approximation of the control polygon to the output curve.

Forming part ratios

Instead of by directly inserting into the equation of the curve, the calculation is in excess of the design of dots of the given control point. The construction starts with the starting points. From these, the connecting lines are constructed new points in the ratio by dividing. The point is calculated using the intuitive insightful formula:

In this diagram are the points that have emerged from the starting points, shown in red. By continuing the calculation regulation points are determined in the same manner. For the calculation of the blue dashed lines connecting the calculated points in the first step in the same proportion to be shared, etc.

Construction of a curve point

It is the following statement (see proof of point construction ):

That is, that the point, which is constructed in the iteration by continued path parts, a point of the curve. The split ratio determines its position on the curve.

In the adjacent figure, the construction is performed for fully. The point that is the result of three times the application of the procedure of division of the output points, is located on this curve.

The more interesting by far the statement is, however, that this point, the curve is divided into two Bezier curves and and that the points form the control polygon and the points of the control polygon of.

Parts in two Bézier curves

The figure shows the decomposition of in and for. Here are the points, and the control polygon of and according to the points, and the control polygon of.

In the figure it can be seen also why a split ratio is used by the rule. As a division ratio smaller ½ was used in this example, the curve is divided into an unequal relationship in a short curve and a long curve. The shorter part is much better to be approximated control polygon than the longer one. If you want ( at about the same long stretches of the initial control polygon ) achieve a uniform approximation, this is the division ratio.

The subdivision of the curves will continue until they are sufficiently accurately approximated by their control polygons.

Pseudocode

Its initial points of the control polygon ago in a field. For a given parameter of the point is calculated as follows:

BEGIN      FOR i: = 0 n.               FOR j: = 1 n.          FOR i: = 0 (n- j).              / / Dividing by a factor of t                    RETURN END The above algorithm is incomplete in that only the determined point, but no continued subdivision is performed. The algorithm is not memory efficient because it uses for all new locations.

Proof of point construction

The statement that over -fold continued division into sections is another point on the curve can be constructed, can be proved about solving the recurrence that defines.

Recurrence equation

The recurrence equation defines the points in response to the value calculated in the final iteration points. The start of recurrence are the points:

For demonstrative statement

To prove the statement that the point is a point on the curve at the point:

Generalization of the statement

To find a solution to the recurrence for the special point is a closed form for all points of recurrence searched and shown that this provides in particular for the desired result. The proof is done via induction using the following induction hypothesis:

The induction step is then a straightforward calculation, are used in the statements about binomial coefficients.

Application

Using the algorithm of the de Casteljau it is possible to calculate approximations of Bezier curves with straight lines. Thus, a Bezier curve be drawn efficiently with the computer.