Contents

The What and Why

Surfaces in Uniform

Float Like a Butterfly...

Catmull-Clark Surfaces

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