defined by the
array of control points
where
where M is the
matrix
The control point mesh for such a patch is shown in the figure below.
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.
Ed Catmull and Jim Clark, while still graduate students at the University of Utah, sought to extend Doo and Sabin's algorithm to bicubic surfaces. Since the methods of Doo-Sabin is based upon the binary subdivision of the uniform bi-quadratic B-spline patches, Catmull and Clark believed that study of the cubic case would lead to a better subdivision surface generation scheme.
For a postscript version of these notes look here.
A Matrix Equation for the Bicubic Uniform Spline Surfaces
Consider the bicubic uniform B-spline surface defined by the
array of control points
where
where M is the matrix
The control point mesh for such a patch is shown in the figure below.
Subdividing the Bicubic Patch
The bicubic uniform B-spline patch
can be subdivided into four subpatches, which can be
generated from 25 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 25 points
produced by subdividing into four subpatches. We have outlined the
initial subpatch that we consider below. It should be noted that the
nine ``interior'' control points are utilized by each of the four
subpatch components of the subdivision.
This subpatch can be generated by reparameterizing the surface by
the variables u' and v', where 
and
. Substituting these into the equation, we obtain
where 
and
Through this process, we have written the surface 
as
for some 
control point array P'. This implies that
is a uniform bicubic B-spline patch. The matrix S
is typically called the ``splitting matrix'', and is straightforward
to calculate. It is given by
By carrying out the algebra, we can calculate the control point array
P' by
and we obtain
Each of these points can be classified into three categories - face
points, edge points and vertex points - depending on each points
relationship to the original control point mesh.
The points
,
,
and
, which are shown in the figure below
are called ``face'' points, and are calculated as
the average of the four points that bound the respective face. If we
define the face point 
to be the average of the points
,
,
and
, then we can
rewrite the above equations with these face points substituted on the
right-hand side, and obtain
Simplifying these equations, we obtain
In examining these equations, we see that the points
,
,
,
,
,
,
and
,
which are called ``edge'' points,
are given as the average of four points - the two points that define
the original edge and the two
two new face points of the faces sharing the edge. This is shown in
the following figure.
These edge points 
can be calculated either as
or
depending on which side of the edge point the two faces lie.
If we replace these edge points on the right-hand side of the
equations above, we obtain
The remaining four points,
,
,
and
,
as shown in the figure below
are called ``vertex points''. These points, as can be seen above, are
somewhat complex, but after some reduction it can be seen that
where 
is the average of the face points of the faces adjacent to
the vertex point, 
is the average of the midpoints of the
edges adjacent to the vertex point and 
is the corresponding vertex
from the original mesh. For example, if we consider the
point 
, then
All sixteen points of the subdivision have now been characterized in terms of face points, edge points and vertex points, and a geometric method has been developed to calculate these points.
Extending this Subdivision Procedure to the Entire Patch
We note that all 25 of the points can actually be calculated in this
manner, as for example 
is a face point and can be
calculated as the average of the four points bounding the face. In
general, we call the mesh generated by the 25 points as a
refinement
of the original mesh. In this case, we can state the
following rules to generate
the points for the refinement of the surface:
, 
and 
, where 
is the average of the new face
points of all faces adjacent to the original vertex point, 
is the
average of the midpoints of all original edges incident on the
original vertex point, and 
is the original vertex point.
The process generated from these rules actually extends to arbitrary rectangular meshes, so we can perform this process again on our refined mesh of 25 elements, producing a second refinement of the original mesh. In this case, we know that this represents yet another subdivision and that eventually, if we keep refining, this ``limit mesh'' will converge to the original uniform B-spline surface.
Thus, this process gives us a sequence of meshes, each of which is a refinement of the mesh directly above, and which converges to the surface in the limit. For the purposes of rendering such a surface we can simply let the refinement process go until we have a mesh that is ``sufficiently close'' to the actual surface and then utilize the mesh for rendering purposes.
Summary
The subdivision of the bicubic uniform B-spline surface produces a simple procedure based upon face points, edge points and vertex points, and can be extended to be a refinement procedure for an extended mesh based upon a rectangular topology. Catmull and Clark were able to take this procedure and produce a refinement strategy that works on a mesh of arbitrary topology.
|
This document maintained by
Ken Joy
All contents copyright (c) 1996, 1997 |
|
