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 halfpixel
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 halfpixel 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, upandcoming 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 nextgeneration game engines. The
spread between highend and lowend 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 lowend 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 Bspline 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 easeofuse
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 C^{n} continuity, where n determines
how many derivatives are continuous. So if a surface is C^{0}
continuous, it means that no derivatives are continuous, that the surface
itself doesn’t have open holes. If a surface is C^{1} 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 C^{1} continuity everywhere. Some
have C^{2} continuity in some places, but the majority have areas
where the best they can claim is C^{1}. 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 nsided
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 v^{i}.
The vertex’s valence is N. The
neighboring vertices of the vertex are e_{j}
where j is in the range [0,N–1]. Again, if the level of recursion
matters, that level i is a superscript,
so e^{i}_{j}
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 welldefined 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 welldefined
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.
