On-Line Geometric Modeling Notes
Overview
Subdivision methods for curve generation are based upon a procedure which successively refines a control polygon into into a sequence of control polygons that, in the limit, converges to a curve. The curves are commonly called subdivision curves as the refinement methods are based upon the binary subdivision of uniform B-spline curves.
The uniform B-spline curves, surfaces and solids have been extensively studied in the literature and subdivision methods for these objects are well known. We develop here the refinement method for a quadratic uniform B-spline curve and show that the refinement is exactly that specified by Chaikin's Algorithm [1].
For a postscript version of these notes look here.
The Matrix Equation for the Quadratic Uniform B-Spline Curve
Given a set of control points
the quadratic uniform B-spline curve
defined by these control points can be defined in
segments by the n-1 equations
for k = 0, 1, ..., n-2, and 
, and where
The matrix M, when multiplied by
defines the quadratic uniform B-spline blending functions.
Splitting and Refinement
We will begin by studying the binary subdivision of a quadratic
uniform B-spline curve 
defined by the control polygon
, containing only three
points, and then extend this to control polygons containing larger
numbers of points.
We can perform
a binary subdivision of the curve, by applying one of two splitting
matrices
to the control polygon. (When applied to the control polygon 
gives
the first half of the curve, and 
gives the second half.)
As it turns out, several of the control points for the two subdivided
components are the same.
Thus, we can combine these matrices, creating a 
matrix
and apply it to a control polygon as follows:
and so the refined curve has control points that are positioned as
in the following illustration:
i.e. at 
and 
along each of the lines of the
control polygon. These are the
same points as are developed in Chaikin's method
The General Refinement Procedure
The general procedure is -
given a control polygon,
we can generate a refinement of this set of points
by constructing
new points along each edge of the original polygon at a distance of
and 
between the endpoints of the edge.
The general idea behind subdivision
curves is to assemble these points into a new control polygon which
can then be used as input to another refinement
operation, generating a new set of points and another control polygon
- and then continue this process until a refinement is reached
that accurately represents the curve to a desired resolution. The
following illustration shown the second refinement in the case above.
Since this general refinement procedure is developed from the binary subdivision of a uniform B-spline curve, and the control points of the refined polygon are unions of those of the subdivided curves, we then have that the control points of the refined polygons must converge to the curve. That is, in the limit, the sequence of control polygons generated by the refinement procedure converges to a quadratic uniform B-spline curve. This shows that Chaikin's curve is really a quadratic uniform B-spline curve.
Summary
Given a control polygon we can specify a simple process that can be used to generate successive refinements of the control polygon and, in the limit, converges to the uniform B-spline curve defined by the original control polygon. This scheme is the basis for the development of the Doo-Sabin subdivision scheme which generalizes Chaikin's algorithm to surfaces.
|
This document maintained by
Ken Joy
All contents copyright (c) 1996, 1997 |
|
