|
|
 |
 |
 | | | | |
 |
|||
 |
||||||
          |
 |
 |
||||
|
Divide and Conquer There is another way to calculate points on the curve known as subdivision. This form is come about by reparameterizing the curve into a left half and a right half. This generates two sets of control points, one for each half of the original curve. The endpoints of these new curves, which are represented in the new control points, are on the curve, so we will have new points on the curve. This process can be applied recursively to generate as many points on the curve as desired. The left half of the curve is developed below using the matrix formulation. The matrix form of the quadratic Bézier curve is shown below.
Reparameterizing this curve to go from 0 to ˝ becomes:
We can further manipulate this equation to generate a matrix that when multiplied by the geometry vector of the original control points will create new control points that define a Bézier curve for the first half of the original curve as follows:
After some matrix calculations, SL is found to be:
Similarly, the curve can be reparameterized to find the matrix that will generate the new control points for a Bézier curve that duplicates the right half of the original curve. When this is done, a SR is found to be:
There are several advantages to this approach. To generate new points, only the matrix multiplies are needed, t does not need to be used at all. The subdivision matrices involve only division by powers of two, which can be pretty efficient, particularly if fixed point representations are being used, since then it only involves a shift. A curve can be generated by recursively subdividing the control points and using the newly generated endpoints as points on the curve. It would also be possible to use the middle control point as a point on the curve, though technically it is not, but as the subdivision gets further and further refined, this point gets closer and closer to the curve. The subdivision can either be set to only go to a certain depth, or it can be designed to stop when the segment is deemed flat enough. Listing 2 uses recursive subdivision to draw a Bézier curve. A little speed can be gained if the code is recrafted to take advantage of the fact that the two new halves of the subdivided curve share the middle endpoint. |
|
|
Features
