previous article "Subdivision
Surface Theory", I explained what subdivision surfaces were
and why game developers should be interested in them. I also covered
a couple different kinds of subdivision surfaces in their mathematical
forms and briefly discussed their benefits and detriments. Most everything
was in English, and the rest was expressed using equations. There were
no code listings last month, not even a hint of C++, but I promised
to discuss an implementation, and so that's the goal of this article.
I'll cover a sample implementation of the modified butterfly scheme
as discussed in last month's article, complete with a shiny, new demo.
Surface Theory" , I wrote about a number of schemes and those
were only the tip of the iceberg, so it's worth spending some time justifying
the choice I've made for this implementation. Why use the modified butterfly?
To explain my reasoning, it helps to look at more general characteristics
of schemes and their advantages and disadvantages. The major differences
tend to hinge on whether a scheme is approximating or interpolating.
schemes have a number of benefits. The surfaces they produce are generally
very fair, and they are generally the favored schemes for use in high-end
animation. For instance, Pixar uses Catmull-Clark surfaces for their
character animation. The downside of approximating schemes are substantial,
though. The major one is that because the scheme doesn't interpolate
its control net, the shape of the limit surface can be difficult to
envision from looking at the control net. The caveat is that as the
net becomes denser, the surface will generally be closer to the net.
But for games, the net itself won't be tens of thousands of polygons,
so the surface can differ substantially from the net.
schemes are a different story. They can exhibit problems with fairness,
with ripples and undulations over the surface, especially near tight
joint areas. Also, they aren't used in high-end rendering quite as much,
which can mean that they're the focus of less research. But their major
benefit is that the surface is substantially easier to envision by looking
at the net. Since the surface passes through all the net vertices, it
won't "pull away" from the net. The fairness issues are the
price to pay for this, though. Approximating schemes are fair because
the surface isn't constrained to pass through the net vertices, but
interpolating schemes sacrifice the fairness for their interpolation.
I feel that the fairness issues present less of a challenge to intuition
than an approximating surface does. For example, in many cases, existing
artwork can be used with interpolating schemes with some minor adjustments
to smooth out rippling, whereas adapting existing polygonal art to be
a control net for an approximating scheme is a much more difficult task.
interpolating schemes, the butterfly scheme has a number of things going
for it. It's one of the better-researched schemes. It's also computationally
fairly inexpensive. Finally, the results of subdivision tend to look
good and conform fairly well to what intuition would expect. Therefore,
it's my model of choice.
1. The stencil used
for the regular case of the modified butterfly scheme.
haven't already, you probably should read my article from last month's
issue for the deeper explanation of the modified butterfly scheme. But
in case you haven't, I'll summarize it here. Given a triangular mesh,
the control net, we want to subdivide it one step. We first add a vertex
along each edge according to specific rules. If the endpoints of the
edge are both of valence 6, then we use the stencil in Figure 1, with
endpoint is of valence 6 and the other is extraordinary (not of valence
6) then we use a special stencil that takes into account just the extraordinary
vertex, shown in Figure 2. The weights are computed as follows:
2. The stencil used for the extraordinary case of the modified
endpoints are extraordinary, we average the results of using the above
extraordinary stencil on each of them. Again, if this seems a bit too
terse, refer to last month's article where I discuss the scheme in substantially
as the butterfly scheme's characteristics, it's interpolating because
points in a control net also lie on the limit surface - the subdivision
process doesn't move existing vertices. It's also triangular as it operates
on triangular control nets. It's stationary as it uses the same set
of rules every time it subdivides the net, and uniform because every
section of the net is subdivided with the same set of rules.
3. The stencil used for the tangent mask of a regular vertex.
of the scheme that I mentioned last month but didn't define was the
tangent mask of the butterfly scheme. This is the mask used to compute
the tangent vectors explicitly at a vertex, which we use to find the
vertex normals. The mask is large and therefore may look intimidating,
but it's just a bunch of numbers, and a few multiplications and additions
later, we've got the answer.
vertices, the process involves the 1- and 2-neighborhood of the vertex
(so it uses vertices that are one and two steps away.) Between both
neighborhoods, there are 18 vertices, and so the scalars, corresponding
to the indexing shown in Figure 3, are:
the vertices by l0 and l1 gives us two different tangent vectors, the
normalized cross product of which is our normal. For extraordinary vertices
the normal is actually easier to find, as it depends only on the 1-neighborhood
of the vertex. The two tangent vectors in this case can be found as:
t0 and t1 are the tangents, N is the vertex valence, and ei is the ith
neighbor point of the vertex in question, where e0 can be any of the
points (it doesn't matter where you start) and the points wind counterclockwise.
Crossing the two resulting vectors and normalizing the result produces
the vertex normal.