Subdivision Surfaces

Subdivision surfaces are a method of representing a smooth curve using a finite number of points. Similar to bezier surfaces and NURBS, these surfaces have the property that each point is associated with a neighborhood region of the curve, and the neighborhood region on the curve is drawn toward its associated point. This property is valuable because it allows artists to sculpt the resultant curve simply by moving the associated points around. There is a big difference, though: the points are arranged in a mesh, and therefore form edges and faces.

So, how is the curve related to the associated mesh? Well, a “subdivision” process is applied to the mesh in order to create a second, higher fidelity, mesh. This process is then applied to the second mesh to create an even higher fidelity mesh. Repeating this process ad infinitum will result in an infinitely detailed mesh, which converges on the resulting surface.

There are many different examples of the aforementioned process. I’ll only be concerned with Catmull-Clark Subdivion Surfaces [1], which are characterized by a particular subdivision process. This process is the following:

1. Create a point in the center of each face of the mesh
2. Create a point in the center of each edge of the mesh
3. Connect the adjacent new edge points and new face points with new edges
4. Move all the original vertices “inward” by a certain amount, where “inward” means “toward the average of nearby vertices”
5. Connect adjacent edges and faces

Let’s talk about computing the surface given particular input points. One obvious way to do it is to simply perform the subdivision process a bunch of times until the faces are adequately small, and then represent the curve as the geodesic formed by each of the faces. However, that process is time-consuming.

It turns out that, in some cases, it is possible to compute the limit surface directly. Catmull and Clark actually do this in their original 1978 paper. They consider a small area of a larger mesh that consists of 16 vertices, arranged in a 4x4 grid. They propose a formula for the limit surface of that small region, and then show that, after a single subdivision step, the formula of the new mesh is the same as the original. In particular, they represent the limit surface as a B-spline surface.

That’s pretty cool, but it’s only useful when considering a neighborhood that consists of a 4x4 grid of vertices. There are plenty of other topological cases that are not covered by this original paper. However, we can gain insight into these cases by considering the concept of “extraordinary vertices.”

In a mesh, an extraordinary vertex is on that has a valence (neighbor-count) that is not equal to 4. You can imagine that a mesh which contains no extraordinary vertices is isomorphic to just a single plane. (Note that the limit surface of such a mesh can be computed directly via the method described earlier). However, all manifolds must contain at least one extraordinary vertex.

Note that an iteration of the Catmull-Clark subdivision process does not introduce any new extraordinary vertices. On the other hand, it doesn’t remove extraordinary vertices either. This means that the number of extraordinary vertices does not change from the original mesh. In contrast, the total number of vertices increases. This means that the area of the mesh that is incident to an extraordinary vertex shrinks as you perform more and more subdivisons.

This is an important result because it means that the more we subdivide, the more of the mesh fits the form of which we can directly compute the limit surface.

It turns out that it is possible to directly compute the limit surface even in the vicinity of extraordinary vertices [2]. This is pretty cool, however it requires transforming the mesh into eigenspace, which is expensive and can potentially produce cracks between different areas of the mesh. A better idea is to directly model the parts that you can, and perform subdivision on the neighborhoods of extraordinary vertices [3]. If you do this a few times, you will have most of the surface covered by the direct limit surface, and the remainder will be close enough to the limit surface. This approach is valuable because, if the limit surface is represented as a B-spline, you can tesselate it to any degree at runtime using the hardware tessellation unit in modern graphics cards. (The benefit of this over performing the subdivision steps at runtime is that the neighborhood search is avoided).

[1] http://www.cs.berkeley.edu/~sequin/CS284/PAPERS/CatmullClark_SDSurf.pdf

[2] http://www.dgp.toronto.edu/people/stam/reality/Research/pdf/cc.pdf

[3] http://graphics.stanford.edu/~niessner/papers/2012/3feature/niessner2012feature.pdf