defined by
the 
array of control points
On-Line Geometric Modeling Notes
Overview
Subdivision surfaces are based upon the binary subdivision of the uniform B-spline surface. In general, they are defined by a initial polygonal mesh, along with a subdivision (or refinement) operation which, given a polygonal mesh, will generate a new mesh that has a greater number of polygonal elements, and is hopefully ``closer'' to some resulting surface. By repetitively applying the subdivision procedure to the initial mesh, we generate a sequence of meshes that (hopefully) converges to a resulting surface.
As it turns out, this is a well known process when the mesh has a ``rectangular'' structure and the subdivision procedure is an extension of binary subdivision for uniform B-spline surfaces. In these notes we present a study of the quadratic uniform B-spline case, and develop the refinement rules that can be generalized into the Doo-Sabin subdivision method.
For a postscript version of these notes look here.
The Matrix Equation for a Uniform Biquadratic Spline Surface
Consider the biquadratic
uniform B-spline surface defined by
the array of control points
and the following equation (in matrix form)
where M is the 
matrix
The matrix M defines the quadratic uniform B-spline blending
functions when multiplied by
.
Subdividing the Surface
This patch can be subdivided into four subpatches, which can be
generated from 16 unique sub-control points. We focus on the
subdivision scheme for only one of the four (the subpatch
corresponding to 
), as the others will
follow by symmetry. The following figure illustrates the 16 points
produced by subdividing into four subpatches. We have outlined the
initial subpatch that we consider below. It should be noted that the
four ``interior'' control points are utilized by each of the four
subpatch components of the subdivision.
To subdivide the surface, we consider the
reparameterization of the surface by 
and
and define this new surface as 
.
Substituting these into the equation, we obtain
where 
and
Through this process, we have written the surface 
as
for some 
control point array S. This implies that
is a uniform biquadratic B-spline patch. The matrix S
is typically called the ``splitting matrix'', and is given by
and so the control point mesh P' corresponding to the subdivided patch is
related to the original control points mesh by
By carrying out the algebra, we have that
where the 
can be written as
These equations can be looked at in two ways:
utilizes the four points
on a certain face of the rectangular mesh, and calculates a new point
by weighing the four points in the ratio of 9-3-3-1. Thus, this
algorithm can be specified by using subdivision masks, which
specify the ratios of the points on a face to generate the new points.
In this case, the subdivision masks are as follows
Generating the Refinement Procedure
To generate the subdivision surface, we consider all 16 of the possible points generated through the binary subdivision of the quadratic patch. It is easily seen that each of these points can be generated through considering other subdivisions of the patch P(u,v) and can be defined by the same subdivision masks
Summary
The extension of Chaikin's Curve to surfaces is quite straightforward. The analysis has produced a simple mask that can be utilized to define the new points on each face (one per vertex). Connecting up these vertices into a new mesh is straightforward.
The interesting extension of this algorithm is when the control point mesh does not have a rectangular topological structure. In this case, we can still utilize the same paradigm and this was accomplished by Donald Doo and Malcolm Sabin in their Doo-Sabin surfaces
|
This document maintained by
Ken Joy
All contents copyright (c) 1996, 1997 |
|
