|
 Features
Subdivision
Surface Theory
At Siggraph
'98, Pixar unveiled a short animated film. Christened Geri’s Game, it was, to quote
its Academy Award press release, the “endearing tale of an aging codger
who likes to play chess in the park against himself.” Not only was it
artistically stunning, but it was also a technological powerhouse. The
short served as a vehicle to demonstrate Pixar’s latest addition to its
production environment, a surface scheme known as subdivision surfaces.
Subdivision
surfaces are a way to describe a surface using a polygonal model. Like
the polygonal model, the surface can be of any shape or size — it’s not
limited to a rectangular patch. Unlike that polygonal model, the surface
itself is perfectly smooth. Subdivision surface schemes allow you to take
the original polygonal model and produce an approximation of the surface
by adding vertices and subdividing existing polygons. The approximation
can be as coarse or as detailed as your needs allow. Because Pixar’s rendering
system requires everything to be broken into polygons that are a half-pixel
across, subdivision surfaces allowed them to tessellate automatically
to that level everywhere. As such, the artists didn’t need to worry about
how close Geri was to the camera. While your game probably can’t quite
deal with half-pixel polygons, whatever size you do choose, your models
can scale up and down in polygon count with the speed of the machine and
their distance from the camera.
The
technology itself is, for the most part, not new, but its application
up until recently has been fairly limited. Indeed, Geri’s Game
is still one of the only compelling demonstrations of subdivision surfaces.
Nonetheless, it brought attention to subdivision surfaces as a relatively
new, up-and-coming technique for implementing scalable geometry.
Along
with Pixar’s work, quite a few researchers are actively tackling issues
in the area of subdivision surfaces, and several Siggraph papers each
year advance them academically and put them to use in solving problems.
By now, they are a fairly mature technology, and a compelling contender
among scalability solutions.
The
game development community realizes that scalable geometry techniques
are an important part of developing next-generation game engines. The
spread between high-end and low-end hardware seems to get bigger each
year (thanks to current and forthcoming geometry accelerators such as
Nvidia’s GeForce 256 and S3’s Savage2000), forcing game developers to
find ways to cater to the masses that use low-end machines while building
in features that make the most of hardcore gamers’ advanced hardware.
As a result, on the low end our engines should still be capable of using
fewer than 10,000 polygons per scene, but on the high end, the sky’s the
limit: even hundreds of thousands of polygons per scene can cruise along
at 60 frames per second. Scalable geometry techniques such as subdivision
surfaces are therefore necessary to accommodate this variation in hardware
capabilities.
In
this article, a number of different kinds of subdivision surfaces will
be discussed. As a preliminary warning, this article is entirely theory.
Next month, we’ll look at an example implementation of one of the schemes,
the modified butterfly, which I’ll discuss here. Keep in mind as you read
this article that not every concept described here will be practical for
use in your engine. Indeed, some subdivision surface models may not be
feasible for use in games at all. But knowing the strengths and weaknesses
of the various models will help you make the right decision for your next
game.
The
What and the Why
First,
what is a subdivision surface? The obvious answer is that it’s a surface
generated through subdivision. To elaborate, every subdivision surface
starts with an original polygonal surface, called a control net. Then
the surface is subdivided into additional polygons and all the vertices
are moved according to some set of rules. The rules for moving the vertices
are different from scheme to scheme, and it is these rules that determine
the properties of the surface. The rules of most schemes (including all
the ones discussed here) involve keeping the old vertices around, optionally
moving them, and introducing new vertices. There are schemes that remove
the old vertices at each step, but they’re in the definite minority.
The
one thing the control net and the eventual surface (called the limit surface)
have in common is that they are topologically the same. Topology is a
way of describing the structure of a surface that isn’t changed by an
elastic deformation, that is, a stretching or twisting. A good example
and common joke is that to a topologist, a coffee cup and a donut are
identical. The donut hole corresponds to the hole in the handle of the
coffee mug. On the other hand, a sphere and coffee mug are not topologically
equivalent, since no amount of stretching and twisting can punch a hole
in that sphere.
Topology
is one reason that subdivision surfaces are worth a look. With Bézier
or B-spline patches, modeling complex surfaces amounts to trying to cover
them with pieces of rectangular cloth. It’s not easy, and often not possible
if you don’t make some of the patch edges degenerate (yielding triangular
patches). Furthermore, trying to animate that object can make continuity
very difficult, and if you’re not very careful, your model will show creases
and artifacts near patch seams.
That’s
where subdivision surfaces come in. You can make a subdivision surface
out of any arbitrary (preferably closed) mesh, which means that subdivision
surfaces can consist of arbitrary topology. On top of that, since the
mesh produces a single surface, you can animate the control net without
worrying about seams or other continuity issues.
As
far as actual uses in games, I believe that subdivision surfaces are an
ideal solution for character modeling. Environments and other parts of
a game generally don’t have the fine detail or strange topology that would
require subdivision surfaces, but characters can have joint areas that
are particularly hard to model with patches, and characters are in constant
animation, which makes maintaining continuity conditions very important.
The
basics. Before we start discussing individual schemes, let’s look
at the basic characteristics of subdivision surfaces in general. This
gives us a framework for classifying and comparing the schemes as we come
across them. Most of these characteristics carry notable implications
with them, whether they are implied computational costs or implied ease-of-use
considerations, or anything else. These will usually be the criteria on
which you might choose one scheme above another.
Continuity:
the holy grail. The first characteristic of a scheme is its continuity.
Schemes are referred to as having Cn continuity, where n determines
how many derivatives are continuous. So if a surface is C0
continuous, it means that no derivatives are continuous, that the surface
itself doesn’t have open holes. If a surface is C1 continuous,
it means that the surface is closed and that its tangents are continuous
(so there aren’t any sharp seams).
This
probably won’t be a major selling point of one scheme above another, since
just about every scheme has C1 continuity everywhere. Some
have C2 continuity in some places, but the majority have areas
where the best they can claim is C1. So most schemes are alike
in this regard.
However,
continuity is most certainly worth mentioning because it’s one of the
major reasons to think about using subdivision surfaces in the first place.
After all, Pixar could have modeled Geri using as many polygons as they
wanted, since they’re not running their movies in real time. But no matter
how many polygons they used, you could get close enough that Geri’s skin
would look faceted from the polygons. The point of using a subdivision
model is that you have that ideal limit surface at which you can always
throw more and more polygons as you get closer and closer to, no matter
how high the display resolution or how close the model is to the screen.
Only a very small portion of the real world is flat with sharp edges.
For everything else, there’s subdivision surfaces.
To
Interpolate or not to Interpolate...
While
the degree of continuity is generally the same for all subdivision schemes,
there are a number of characteristics that vary notably between schemes.
One important aspect of a scheme is whether it is an approximating scheme
or an interpolating scheme. If it’s an approximating scheme, it means
that the vertices of the control net don’t lie on the surface itself.
So, at each step of subdivision, the existing vertices in the control
net are moved closer to the limit surface. The benefit of an approximating
scheme is that the resulting surface tends to be very fair, having few
undulations and ripples. Even if the control net is of very high frequency
with sharp points, the scheme will tend to smooth it out, as the sharpest
points move the furthest onto the limit surface. On the other hand, this
can be to the approximating scheme’s detriment, too. It can be difficult
to work with, as it’s harder to envision the end result while building
a control net, and it may be hard to craft more undulating, rippling surfaces
as the scheme fights to smooth them out.
 |
|
Figure
1. Two schemes subdivide a
tetrahedron. The left scheme is
approximating, and the right is interpolating.
|
If
it’s an interpolating scheme, it means that the vertices of the control
net actually lie on the limit surface. This means that at each recursive
step, the existing vertices of the control net are not moved. The benefit
of this is that it can be much more obvious from a control net what the
limit surface will look like, since the control net vertices are all on
the surface. However, it can sometimes be deceptively difficult to get
an interpolating surface to look just the way you want, as the surface
can develop unsightly bulges in areas where it strains to interpolate
the vertices and still maintain its continuity. Nonetheless, this is usually
not a tremendous problem.
Figure
1 shows examples of an approximating scheme (on the left) and an interpolating
scheme (on the right). The white outline is the control net, and the red
wireframe is the resulting surface after a few subdivision steps. You
can see the difference quite clearly: the approximating surface seems
to pull away from the net, while the interpolating surface flows through
the vertices of the net.
Surfaces
in Uniform
Another
set of characteristics of a scheme brings in four more terms. A scheme
can be either uniform or nonuniform, and it can be either stationary or
nonstationary. These terms describe how the rules of the scheme are applied
to the surface. If the scheme is uniform, it means that all areas of a
control net are subdivided using the same set of rules, whereas a nonuniform
scheme might subdivide one edge one way and another edge another way.
If a scheme is stationary, it means that the same set of rules is used
to subdivide the net at each step. A nonstationary scheme, on the other
hand, might first subdivide the net one way, and then the next time around
use a different set of rules.
All
the schemes we’ll talk about here are fundamentally both uniform and stationary.
There are some extensions to these schemes that make them nonstationary
or nonuniform, but there aren’t many subdivision schemes that are fundamentally
nonstationary or nonuniform. One of the main reasons for this is that
most of the mathematical tools we have for analyzing schemes are unable
to deal with dynamically changing rules sets.
Subdivision
Shape
Another
characteristic of a scheme, albeit less significant than the prior ones,
is whether it is triangular or quadrilateral. As the names would imply,
a triangular scheme operates on triangular control nets, and a quadrilateral
scheme operates on quadrilateral nets. Clearly, it would be inconvenient
if you had to restrict yourself to these primitives when building models.
Therefore, most quadrilateral schemes (including the one discussed here)
have rules for subdividing n-sided
polygons. For triangular schemes, you generally need to split the polygons
into triangles before handing them over to be subdivided. This is easy
enough to do, but one downside is that for some schemes, the way you break
your polygons into triangles can change the limit surface. The changes
are usually minor, though, so you simply need to be consistent: if you
randomly choose which diagonal of a quadrilateral to split on every frame,
you’ll end up with popping artifacts.
Figure
2 shows examples of a triangular subdivision scheme as compared to a quadrilateral
scheme. Notice that the triangular scheme only adds new vertices along
the edges, whereas the quadrilateral scheme needs to add a vertex in the
center of each face. This is one reason why triangular schemes tend to
be somewhat easier to understand: their rules have that one fewer step
in them.
 |
|
Figure
2. The differences between the tessellation used by a triangular
scheme (top) and a quadrilateral scheme (bottom).
|
Extraordinary
Vertices
The
preferred vertex valence is another property of subdivision schemes. The
valence of a vertex is the number of edges coming out of it. Most every
vertex a scheme produces during subdivision has the same valence. Vertices
of that valence are the regular vertices of a scheme. Vertices of any
other valence are known as extraordinary vertices. Their effect depends
on the subdivision scheme, but historically there have been problems analyzing
the limit surface near extraordinary vertices. As we look at various schemes,
we’ll see the effect that extraordinary vertices have on each one.
Most
schemes don’t ever produce extraordinary vertices during subdivision,
so the number of extraordinary vertices is set by the original control
net and never changes. Figure 3 is an example of two steps of a triangular
scheme with an extraordinary vertex in the center. Notice how it remains
the only extraordinary vertex after a step of subdivision. Also note that
the valence of the regular vertices is 6. This is common for triangular
schemes, as they all tend to split the triangles in the same way — by
adding new vertices along the edges and breaking each triangle into four
smaller triangles.
 |
|
Figure
3. A triangular net (left) and after one subdivision step (right).
The red vertex is extraordinary.
|
Surface
Evaluation
Surface
evaluation is the process of taking a control net, adding vertices, and
breaking faces into more, smaller faces to find a better polygonal approximation
of the limit surface. There are a number of ways to evaluate a subdivision
surface. All subdivision schemes can be evaluated recursively. Furthermore,
most (including all the ones discussed here) can be explicitly evaluated
at the vertex points of the control net. For interpolating schemes, this
means that you can explicitly calculate the surface normals at the vertices
using what are called tangent masks. For approximating schemes it means
you can also explicitly calculate the vertex’s limit position, using what
are called evaluation masks. In this context, a mask isn’t the same kind
of mask that you might use during binary arithmetic. Our masks are more
analogous to the masks worn at a masquerade. They are like stencil cutouts,
shapes that can be “placed” on the control net, and their shape determines
which of the surrounding vertices are taken into account (and how much
effect each has) in determining the end result, be it the vertex location
or its tangent vectors. Figure 4 shows a visual example of applying a
mask to a surface at a vertex.
 |
|
Figure
4. A hypothetical mask. Here, the white region is a mask used to
dictate which vertices are used in a computation involving the
red vertex.
|
An
important aspect of evaluation is the scheme’s support. The support refers
to the size of the region considered during evaluation. A scheme is said
to have compact support if it doesn’t have to look very far from the evaluation
point. Compact support is generally desirable because it means that changes
to a surface are local — they don’t affect the surface farther away.
A
Note on Notation
Since
the original authors of many subdivision schemes weren’t operating in
concert with one another, the notation used between schemes tends to vary
fairly wildly. Here, I’ve tried to stick with a fairly consistent notation.
When talking about a specific vertex, it is v. If it matters what level of recursion
it’s at, that level i is indicated
as a superscript, so the vertex is vi.
The vertex’s valence is N. The
neighboring vertices of the vertex are ej
where j is in the range [0,N–1]. Again, if the level of recursion
matters, that level i is a superscript,
so eij
is the jth edge vertex at level
i. I try to use this notation everywhere,
but there are a few places where it’s much clearer to use a different
notation.
The
one problem with a standard notation is that if you access some of the
references at the end of this article, they will very likely use their
own, different notation. As long as the concepts make sense, though, it
shouldn’t be difficult to figure out someone else’s naming convention.
The
Polyhedral Scheme
The
polyhedral scheme is about the simplest subdivision scheme of all, which
makes it a good didactic tool but not the kind of scheme you’d ever actually
want to use. It’s a triangular scheme where you subdivide by adding new
vertices along the midpoints of each edge, and then break each existing
triangle into four triangles using the new edge vertices. A simple example
is shown in Figure 5. The problem with this, of course, is that it doesn’t
produce smooth surfaces. It doesn’t even change the shape of the control
net at all. But it serves to demonstrate some concepts fairly well.
 |
|
Figure
5. Two steps of subdividing a
triangle with the polyhedral scheme.
|
The
scheme is clearly interpolating since it doesn’t move the vertices once
they’re created. It’s also triangular, since it operates on a triangular
mesh. Furthermore, the scheme is uniform since the edge’s location doesn’t
affect the rules used to subdivide it, and stationary since the same midpoint
subdivision is used over and over. The surface is only C0 continuous,
since along the edges of polygons it doesn’t have a well-defined tangent
plane. The regular vertices of this scheme are of valence 6, as that’s
the valence of new vertices created by the scheme. However, this scheme
is simple enough that it doesn’t suffer because of its extraordinary vertices.
The
evaluation of the scheme isn’t hard at all. You can evaluate it recursively
using the subdivision rules. As far as evaluation and tangent masks go,
it’s clear that we don’t need an evaluation mask, since the points are
already on the limit surface. Tangent masks don’t really make any sense,
since our surface isn’t smooth and therefore doesn’t have well-defined
tangents everywhere.
Figure
6 shows a tetrahedron control net in white with a red wireframe of the
surface after a few subdivision steps of the polyhedral scheme.
 |
|
Figure
6. A tetrahedron
control net (in white) and
a polygonal surface approximation (in red) produced using the
polyhedral scheme.
|
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.
 |
|
Figure
7. The 8-point stencil for the
original butterfly scheme.
|
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.
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 bsharp@acm.org.
|
|
|
|
|
