Surfaces in Uniform
Contents

The What and Why

Surfaces in Uniform

Float Like a Butterfly...

Catmull-Clark Surfaces

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.

Figure 6. A tetrahedron
control net (in white) and
a polygonal surface approximation (in red) produced using 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.

________________________________________________________

Float Like a Butterfly...