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