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.
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.
|
Figure 1. Two schemes
subdivide a tetrahedron. The left scheme is approximating, and the
right is interpolating. |
________________________________________________________
Surfaces
in
Uniform