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 pdf 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
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
and , where
. Substituting these into the equation, 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
, then we can
rewrite the above equations with these face points substituted on the
right-hand side, and 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
are called ``vertex points''. These points, as can be seen above, are somewhat complex, but after some reduction it can be seen that
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:
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.
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.