Overview
Bézier curves, B-spline curves and subdivision curves are all based upon the input of a control polygon and the specification of an algorithmic method that contructs a curve from this sequence of points. Fundamental to these methods is the concept of a refinement. These refinement methods, as defined mathematically, can be quite complex. However, in practice they are quite simple and usually easy to implement.
In these notes, we discuss the mathematical notion of refinement.
For a pdf version of these notes look here.
What is a Refinement Scheme
A refinement process is a scheme which defines a sequence of control polygons
This is a very general scheme, and quite complex to manage and analyze. It covers the cases where the number of control points in each successive polygon is allowed to increase (Chaikin's Curves and Doo-Sabin's subdivision surfaces are examples of this), or must decrease (de Casteljau's algorithm for generating Bézier Curves is an example of this).
It would be incredibly rare to use the entire set of control points from the st sequence to calculate each new control point in the th sequence as there may be thousands of points to consider - and so in general we assume that most of the s are zero. To simplify things further, we frequently limit this to a uniform scheme, where the s are independent of the level of refinement (). This implies that the scheme is basically the same at each iteration of the refinement process. A further simplification, where the mask is the same for every point of a control polygon, is called a stationary scheme.
If all points that result from a refinement process lie on the lines joining the points of a control polygon, the process is typically called a ``corner cutting scheme''. An example of such a scheme is the Chaikin's Curve.
A Matrix Method for Refinement
The equation
Example - A Stationary Uniform Refinement Scheme
Suppose we are given the control polygon . Define the refinement scheme by the following equation
Note here that two of the s are and the remainder are zero.
In this case, the refinement process stops after steps - as the control polygon for each step of the refinement has one fewer points than does the control polygon in the previous step - the final control polygon having one point.
To represent this refinement process via matrices, the refinement matrix is
If this refinement is taken to completion, we have just calculated a point on the th degree Bézier curve defined by this control polygon.
Example - A Non-Stationary Uniform Subdivision Scheme
Suppose we are given the control polygon . Define a refinement scheme by the following
Notice that this gives us a new control polygon
This is just Chaikin's Algorithm for curve generation. As the algorithm proceeds the number of control points gets arbitrarily large, but converges to a unique curve.
Refinement Schemes for Meshes
Similar methods (with much more notationally complex mathematics) exist for control meshes that result in surface generation algorithms. In general, the idea is the same - the refinement operation generates new control points from the control points of the previous mesh.
Summary
Refinement schemes generate an important class of curve and surface drawing algorithms that are useful in geometric modeling. The schemes generate a sequence of control polygons in the two-dimensional case, or control meshes in the three dimensional case that can be used for curve generation. The methods are useful in the case of Bézier curves and Bézier patches as well as in the generation of subdivision curves and surfaces.