1.6.3. De Casteljau Algorithm
With the de Casteljau algorithm it is possible to construct a Bézier
curve or to find a particular point on the Bézier curve.
In this chapter we won't go into detail of the numeric calculation of the de
Casteljau algorithm. We only want to illustrate figuratively the steps that are
to be fulfilled to construct a Bézier curve or to find a point on the Bézier
curve. If you are interested in the mathematical calculation have a look at the
pages 121-125 of (HOSCHEK et al. 1992).
Construction of a Bézier Curve
To construct a Bézier curve we
have to find several points through which the curve will go. These points depend
on a parameter t "element" 0,1. After we have found all points we are able to
approximate the Bézier curve by connecting these points. It is obvious that the
more points we have, the better is the approximation of the Bézier curve.
We can for example first look for the center of the
curve and afterwards look for the quarter points of the curve and then connect
these four points.
Exemplary Computation of One Point of the Curve
We are looking
for the center (t=1/2) of the curve.
For each segment of
the control polygon the points t=1/2 are calculated. Afterards the points of two
consecutive segments are connected to each other. In the next step the points
t=1/2 of these new segments have to be determined. These steps have to be
repeated as many times as the degree of the Bézier curve is; e.g. a cubic Bézier
curve is of degree 3 therefore you have to execute the steps three times. By
doing so, you get the center (t=1/2) of the Bézier curve.
De Casteljau Algotirhm in pictures
The following control polygon is given. The point with the parameter t= 1/2 ought to be calculated.
Now occurs the fragmentation of the polygon segments. The proportion of the fragmentation is defined through the parameter t. Each polygon segment is now divided in the ratio of t (as it is shown in the previous and the next image) . By doing so we reach the next polygon level:
With the red polygon is dealt in the same manner as above. Each segment between the new points is divided in the ratio of t.
Also the last resulted segment is divided in the ratio of t and we get the final point marked in orange.
If this algorithm is proceeded for many values of t, we finally get the grey marked curve.
The solution for the point t=1/4 looks as following:
Experience the deCasteljau algorithm in the following interaction part by moving the red dots.
De Casteljau Algorithm (Pila Information Educative)Finding a Point on a Bézier Curve
The same algorithm is used for
determining points on a Bézier curve. In this case the curve already exists. A
possible task may look like this:
Find the center (t=1/2)
of the mapped Bézier curve!
By applying the "De Casteljau algorithm", you will find the center of the curve.
Have a look to see the solution! (Click here for more information)
Update: 26.1.2012 (eLML) - Contact - Print (PDF) - © CartouCHe 2004-2007 (Creative Commons)
- layout based on YAML