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. |
 |
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...