Subdivision Surface Theory

Float Like a Butterfly...

The next scheme is known as the butterfly subdivision scheme, or, in its current form, the modified butterfly scheme. It shares some similarities with the polyhedral scheme, but has some differences, notably that it’s C¹ continuous and therefore actually produces a smooth surface.

The butterfly scheme has a fairly interesting history to it. In 1990, Dyn, Levin, and Gregory published a paper titled “A Butterfly Subdivision Scheme for Surface Interpolation with Tension Control” (see For Further Info at the end of this article). It described the first butterfly scheme. The title is derived from the stencil, or map of neighbors used during evaluation, which is shaped like a butterfly (Figure 7). The scheme is interpolating and triangular, so all it ever does is add vertices along the edges of existing triangles. The rules for adding those vertices are simple, and the support is compact. For each edge, sum up the vertices in the stencil-shaped area around that edge, weighting each one by a predetermined weight. The result is the new vertex. The weights used, corresponding to the vertex labelings in Figure 7, are these:

In this case, w is a tension parameter, which controls how “tightly” the limit surface is pulled towards the control net — note that if w equals –1/16, the scheme simply linearly interpolates the endpoints and the surface isn’t smooth.

Figure 7. The 8-point stencil for the original butterfly scheme.

One question that the scheme doesn’t answer, though, is what to do if the area around an edge doesn’t look like that butterfly stencil. Specifically, if either of the edges’ endpoints is of a valence less than 5, there isn’t sufficient information to use the scheme, leaving you with no choice but to choose w = –1/16 near that area, resulting in a surface that isn’t smooth near those extraordinary points. This means that while the surface is smooth almost everywhere, there will be isolated jagged points that really stand out visually and make the surface harder for an artist to craft.

Figure 8. The 10-point stencil from the modified butterfly scheme.

In 1993, Dyn and his colleagues extended the butterfly scheme to use a ten-point stencil, so that the default case was the one shown in Figure 8, similar to the eight-point case with the rear vertices added in. The new weights are:

Note that by adding w to the d points and subtracting it from the a points, the stencil’s total weighting still adds up to 1. Intuitively, this is important because it means that the new point will be in the neighborhood of the ones used to generate it. If the weights summed to, say, 2, then the point would be twice as far from the origin as the points used to generate it, which would be undesirable.

Figure 9. The stencil for an extraordinary vertex in the modified butterfly scheme.

This new scheme even reduces to the old scheme as a subset — choosing w = 0 results in the same rule set as the eight-point butterfly stencil. However, this extension didn’t address the smoothness problem at extraordinary vertices.

In 1996, Zorin, Schröder, and Sweldens published an extension of the butterfly scheme known as the modified butterfly scheme. The primary intent of their extension was to develop rules to use for extraordinary vertices, making the surface C¹ continuous everywhere.

If both of the endpoints of the edge are regular valence-6 vertices, the scheme uses the standard butterfly’s ten-point stencil with the same weights.

If only one of the endpoints is extraordinary, the new vertex is computed by the weighted sum of the extraordinary vertex and its neighbors (see the stencil in Figure 9). Note that you actually do not consider some of the neighbors of the regular vertex in doing this, which might seem a little odd. Given the extraordinary vertex’s valence of N, the weights used are:

The full justification for these weights is available in Zorin’s thesis (see For Further Info at the end of this aritcle).

If both endpoints of the edge are extraordinary, the vertex is computed by averaging the results produced by each of the endpoints. So, evaluate the vertex once for each endpoint using the appropriate weights from above, and average the resulting two candidates.

Those, then, are the rules for recursively evaluating the surface. Since the scheme is interpolating, you don’t need an evaluation mask, but it would be nice to have a tangent mask to explicitly find the tangents at vertices. Such a mask exists, although it’s fairly lengthy to write out, and not particularly enlightening. It can be found in Zorin’s thesis, and I’ll discuss it next month when implementing this scheme.

Figure 10 shows a tetrahedron control net in white with a red wireframe of the surface after a few subdivision steps of the modified butterfly scheme.

Figure 10. A tetrahedron control net (in white) and a polygonal surface approximation (in red) produced using the modified butterfly scheme.

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.

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).

Figure 11. Calculation of a new edge vertex in a Catmull-Clark surface. The new edge vertex is the average of the four points.

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:

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.

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.

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 t₀ and t₁.

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 [email protected].