On-Line Geometric Modeling Notes
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 postscript version of these notes look here.
What is a Refinement Scheme
A refinement process is a scheme which defines a sequence of control polygons
where for any k>0, each 
can be written as
That is, any element 
can be written as a
linear combination
of the control points
from the control polygon generated in the prior step.
For each fixed j and k the sequence 
is frequently
called a mask.
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 k-1st sequence to calculate each new control point in the
kth 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 (k). 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
can be written in matrix form as
and overall
where 
is the refinement matrix
and is an 
matrix. In general it is best to think
of this matrix as being sparse (i.e. most of the entries being zero)
with non-zero entries clustered along the diagonal.
Example - A Stationary Uniform Refinement Scheme
Suppose we are given the control polygon 
.
Define the refinement scheme by the following equation
where 
and k = 0, 1, 2, ..., n-1.
In other words, each successive point in the refinement is taken to be
the midpoint of the line segment joining the two corresponding points
in the previous control polygon.
Note here that
two of the 
s are 
and the remainder are zero.
In this case, the refinement process stops after n-1 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
where the matrix is 
.
If this refinement is taken to completion, we have just calculated a point on the nth 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
and
for j = 0, 1, 2, 3, ....
Notice that this gives us a new control polygon
Applying this refinement process to a control polygon of length n+1
gives a new control polygon of length 2n.
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.
|
This document maintained by
Ken Joy
All contents copyright (c) 1996, 1997 |
|
