http://www.gamasutra.com/view/feature/3177/subdivision_surface_theory.php
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.
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 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.
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.
|
progressive mesh.pdf
