Catmull-Clark
Surfaces
The final scheme we’ll examine has some significant differences
from the modified butterfly. Notably, it’s quadrilateral and it’s
approximating, and so presents some new challenges. Its regular vertices
are of valence 4, since a regular quadrilateral surface is a rectangular
grid with vertices of valence 4.
 |
Figure 11.
Calculation of a new edge vertex in a Catmull-Clark surface. The
new edge vertex is the average of the four
points. |
Because this scheme is quadrilateral, it has to deal with things
like placing vertices in the centers of polygons, and the rules are
generally a bit more complex. Vertex addition is done in three steps. For
each face in the old control net, add a vertex in its center, where the
center is found by averaging its vertices. Then, for each edge in the old
control net, a new vertex is added equal to the average of the edge’s
endpoints and the new adjacent face points (see Figure 11 for an
illustration).
Finally, move the original vertices of the old control
net using neighboring points in the calculation. The stencil is shown in
Figure 12; the rules are as follows:

New edges are then formed by connecting each new face point to its
adjacent new edge points and connecting each new vertex point to its
adjacent new edge points. This defines the faces as well, and it brings up
an interesting point: consider what happens when you subdivide a surface
with a polygon that is not a quadrilateral. The resulting new face vertex
will be connected to k new edge vertices, and k will not be equal to four.
Therefore, the new face vertex is an extraordinary vertex. This is the
only one of the three schemes shown here where the scheme can actually
create an extraordinary vertex during subdivision.
|
Figure 12. The
points used to calculate the new position of a vertex in a
Catmull-Clark surface. The points used are in green; the new
vertex location is in red. |
This is not as bad as it may seem, though. After a single
subdivision step, all the faces in the control net are quadrilaterals.
Therefore, the scheme can only introduce new extraordinary vertices during
the first subdivision step. After a single subdivision step, the number of
extraordinary vertices is set and will not change.
The scheme also has evaluation and tangent masks for
evaluation at the vertices. The full discussion and proof of the
evaluation mask can be found in Halstead et al. and is fairly lengthy. The
mask itself is fairly simple, though. For a vertex of valence N, the mask is equal
to:

It’s interesting to note that this mask requires that we’ve
subdivided the net once, since it uses the face and edge vertices of the
same level as the corner vertices, and face and edge vertices are not
available in the original control net.
The tangent masks carry an equally lengthy discussion,
but their resulting formula is also fairly complicated. Because most of it
can be precomputed for each valence and stored in a lookup table, it’s not
computationally expensive, it’s just a large formula:

The surface normal is then the normalized cross product of
t0 and t1.
Figure 13 shows a tetrahedron control net in white with a red
wireframe of the surface after a few subdivision steps of the
Catmull-Clark scheme.
 |
Figure 13. A
tetrahedron control net (in white) and a polygonal surface
approximation (in red) produced using the Catmull-Clark
scheme. |
Catmull-Clark
Extended
Catmull-Clark surfaces hold the distinction of being the favored
surfaces for use in high-end rendering; they were the model employed by
Pixar in Geri’s Game. Their mathematical elegance and the amount of work
devoted to them make them a fairly attractive choice. For instance, work
has been done on generating Catmull-Clark surfaces that interpolate a set
of points, which, as an approximating scheme, they do not usually do.
Furthermore, Pixar extended them for Geri’s Game to allow for sharp and
semi-sharp creases in the surface.
Pixar’s scheme generating these creases is fairly
straightforward. It allows an artist to specify for an edge or vertex that
subdivision near that edge or vertex should be done sharply (using
polyhedral subdivision) for some number of steps, from 0 to infinity.
Intuitively, the more sharp steps that are used, the more creased the
surface will appear near that edge. If the number is finite, then the
surface will still be smooth, since eventually the surface will resume
using the normal Catmull-Clark subdivision rules. If the crease is
infinitely sharp, it isn’t smooth at all. Pixar put these to use on Geri’s
skin features, adding creases to various locations across his body like
between his skin and fingernails.
It’s worth noting that while this greatly extends the
application of the surfaces, it changes the properties of the scheme. The
scheme becomes both nonuniform, since different edges and vertices can be
of differing degrees of sharpness, and nonstationary, because a semi-sharp
crease is evaluated linearly for some number of steps and then smoothly
for the rest. Near the creases, the surface no longer reduces to the
B-spline surface, and it also invalidates the evaluation and tangent
masks.
Geri’s Game clearly demonstrates the benefit of
sharp and semi-sharp creases. However, for use in games, the evaluation
and tangent masks are fairly important, and so it’s difficult to say
whether the increased computational cost is worth the added
functionality.
Are You Dizzy Yet?
After this whirlwind tour of subdivision surfaces, you
might be feeling a little light-headed or dizzy. Hopefully though, you’ve
picked up the concepts behind subdivision surfaces and maybe even thought
of some good applications for them in projects you’re working on or
getting ready to start. Since there’s nowhere near enough space to discuss
implementation details for even just these three schemes, next month we’ll
bear down and focus on one of them, the modified butterfly scheme. I’ll
mention the reasons I think it’s a good choice for use in games, discuss
some of the benefits and detriments, and then present an example
implementation.
Until then, there’s certainly no dearth of information
on subdivision surfaces. Much of it is available online. The ACM Digital
Library is an excellent resource for this topic as much of the work in
subdivision surfaces has been published in the recent Siggraph
conferences. Furthermore, many of the papers, Siggraph or not, are
available directly from authors’ web sites.
Acknowledgements
Thanks to Pixar for graciously allowing us to use images from
their short animation, Geri’s Game. Thanks also to Denis Zorin for
his suggestions and references, Jos Stam at Alias|Wavefront for his help
and suggestions, and to Alias|Wavefront for allowing him to release his
precomputed eigenstructures. Thanks to Chris Goodman of 3dfx for
discussions, latté, and those hard-to-find papers, and to Adrian Perez of
Carnegie-Mellon University for suggesting the subdivision scheme I
eventually settled on.
For Further
Info
• Catmull, E., and J. Clark. “Recursively Generated B-Spline
Surfaces on Arbitrary Topological Meshes.” Computer Aided Design,
1978.
• DeRose, T., M. Kass, and T. Truong. “Subdivision
Surfaces in Character Animation.” Siggraph ‘98. pp.
85–94.
• Dyn, N., J. A. Gregory, and D. A. Levin. “Butterfly
Subdivision Scheme for Surface Interpolation with Tension Control.” ACM
Transactions on Graphics. Vol. 9, No. 2 (April 1990): pp.
160–169.
• Dyn, N., S. Hed, and D. Levin. “Subdivision Schemes
for Surface Interpolation.” Workshop in Computational Geometry (1993), A.
C. et al., Ed.,” World Scientific, pp. 97–118.
• Halstead, M., M. Kass, and T. DeRose. “Efficient,
Fair Interpolation Using Catmull-Clark Surfaces.” Siggraph ‘93. p.
35.
• Stollnitz, E., T. DeRose, and D. Salesin. Wavelets
for Computer Graphics. San Francisco: Morgan-Kaufman, 1996.
• Zorin, D. “Stationary Subdivision and Multiresolution
Surface Representations.” Ph.D. diss., California Institute of Technology,
1997. (Available at ftp://ftp.cs.caltech.edu/tr/cs-tr-97-32.ps.Z)
• Zorin, D., P. Schröder, and W. Sweldens.
“Interpolating Subdivision for Meshes with Arbitrary Topology.”
Siggraph ‘96. pp. 189–192.
ACM Digital Library
http://www.acm.org/dl
Joe Stam’s web site
http://reality.sgi.com/jstam_sea/index.html
Denis Zorin’s web site
http://www.mrl.nyu.edu/dzorin
Charles Loop’s web site
http://research.microsoft.com/~cloop
Siggraph ‘99 Subdivision Course Details, Notes,
Slides
http://www.mrl.nyu.edu/dzorin/sig99
Geometric Modeling
http://muldoon.cipic.ucdavis.edu/CAGDNotes
When he's not sleeping through meetings or plotting
to take over the world, Brian's busy furtively subdividing, hoping one day
to develop his own well-defined tangent plane. Critique his continuity at
mailoto:bsharp@acm.org.
________________________________________________________
[Back
to] The What and
Why