A Quick Introduction to Subdivision Surfaces

Subdivision Surfaces

Subdivision surfaces are polygon mesh surfaces generated from a base mesh through an iterative process that smooths the mesh while increasing its density. Complex smooth surfaces can be derived in a reasonably predictable way from relatively simple meshes. An example, comparing the Doo-Sabin scheme and the Catmull-Clark scheme, shows how the basic process can proceed.

Step 0
The base mesh consists of a mere 69 polygons (31 in the A, 22 in the S, and 16 in the U). Each letter was designed by hand separately, then the three were merged into one file.

Step 1
After one application of the Doo-Sabin scheme (Left), the mesh has become 282 polygons. The sharpest points have been nicely rounded off. After one application of the Catmull-Clark scheme (Right), the mesh has become 278 polygons. The lengths of the letters have become smoother, but the tips have become slightly pointed.

Step 2
After one more iteration of subdivision, the Doo-Sabin surface now consists of 1,116 polygons. The surface is already noticably smooth. The Catmull-Clark surface now consists of 1,112 polygons. It has smoothed out the pointed tips, leaving them noticably more rounded than the Doo-Sabin's squared-off tips.

Step 3
One more iteration of Doo-Sabin generates the mesh on the left. This mesh contains 4,452 polygons. Notice the smoothly curved outlines of the letters, and compare them to the right angles of the original mesh. The matching Catmull-Clark mesh, on the right, contains 4,448 polygons. Notice the difference between the curves of the "S" in the two meshes.

Different Schemes

Many different schemes exist for the actual subdivision process. The first two were developed in 1978 by two different pairs of people. The Doo-Sabin scheme and the Catmull-Clark scheme are the most well-known, and are used in many high-end modeling and animation packages. An example is the MeshSmooth modifier in 3ds max 4 which, when in Classic mode, appears to use a variation of the Doo-Sabin scheme, producing three- and four-sided facets. It may be switched from Classic to Quad Output, and then generates something closer to the Catmull-Clark scheme. Both modes, and the third NURMS mode, have advanced parameters that affect how the algorithm is applied. A third popular scheme developed relatively recently, the Loop scheme, works only on triangle meshes.

The Doo-Sabin Scheme

Background
Malcolm Sabin is still active in subdivision surfaces. Donald Doo seems to have faded away.

The Scheme
New polygons are built from the old mesh in the following way. An edge point is formed from the midpoint of each edge A face point is formed as the centroid of each polygon of the mesh. Finally, each vertex in the new mesh is formed as the average of a vertex in the old mesh, a face point for a polygon that touches that old vertex, and the edge points for the two edges that belong to that polygon and touch that old vertex. As an example, a square in the old mesh will create a new, smaller square centered in the old square.

The new points then are connected. There will be two vertices along each side of each edge in the old mesh, by construction. These pairs are connected, forming quadrilaterals across the old edges. Within each old polygon, there will be as many new vertices as there were vertices in the polygon. These are connected to form a new, smaller, inset polygon. And finally, around each old vertex there is a new vertex in the adjoining corner of each old polygon. These are connected to form a new polygon with as many edges as there were polygons around the old vertex. The new mesh, therefore, will create quadrilaterals for each edge in the old mesh, will create a smaller n-sided polygon for each n-sided polygon in the old mesh, and will create an n-sided polygon for each n-valence vertex (Valence being the number of edges that touch the vertex). After one application of the scheme all vertices will have a valence of four, so subsequent applications will create quadrilaterals for the vertices. (The original n-sided polygons are retained, however, and shrink to extraordinary points where the mesh is not as smooth, as the scheme is repeatedly applied.)

Observe in the images below that the corners of the cube (With valence of three) have become triangle faces, the faces have become smaller squares, and the edges have become connecting quadrilaterals.

For a more exacting description of the process, with illustrations, see the links at the bottom of this page.

Cube, smoothed twice with repeated applications of the Doo-Sabin scheme

The Catmull-Clark Scheme

Background
Edwin Catmull became the vice president of the computer division of Lucasfilm, Ltd. in 1979, the year after he and Jim Clark published the Catmull-Clark scheme in Computer-Aided Design. When that division was purchased by Steve Jobs in 1986 he became one of the co-founders of the resulting new company, Pixar. He was chief technical officer until 2001, when he became the company's President. Jim Clark founded SGI, and later Netscape with Marc Andreessen. One of Pixar's Academy Award winning short films, Geri's Game, uses subdivision surfaces to great effect. Each hand, and the title character's head, is a single subdivision surface. Subdivision surfaces were also used as the modeling element of choice in Toy Story 2.

The Scheme
New polygons are built from the old mesh in the following way. A face point is created for each old polygon, defined as the average of every point in the polygon. An edge point is created for each old edge, defined as the average of the midpoint of the original edge and the midpoint of the two new face points for the polygons that adjoin the original edge. And finally, new vertex points are defined. For each old vertex, there are n polygons sharing it. The new vertex is (n - 3)/n) times the old vertex + (1/n) times the average of the face points for those adjoining polygons + (2/n) times the average of the midpoints of the edges that touch the old vertex. This gives a point close to, but usually not precisely at, the old vertex.

The new points then are connected. This is straightforward: each face point connects to an edge point, which connects to a new vertex point, which connects to the edge point of the adjoining edge, which returns to the face point. This is done for each such quadruple, fanning out quadrilaterals around the faces. The scheme only produces quadrilaterals, although they are not necessarily planar.

Observe in the images below that each face of the cube has been divided into four quadrilaterals. The vertex points, the corners of the cube, have been "pressed inward". The edge points are clearly derived from the midpoints of the original edges, but are "pressed in" as well.

For a more exacting description of the process, with illustrations, see the links at the bottom of this page.

Cube, smoothed twice with repeated applications of the Catmull-Clark scheme

The Loop Scheme

Background
Charles Loop invented the subdivision scheme that bears his name in his Master's thesis, Smooth Subdivision Surfaces Based on Triangles. He is currently a researcher for Microsoft.

The Scheme
The Loop scheme is defined for triangle meshes only, not general polygonal meshes. At each step of the scheme each triangle is split into four smaller triangles.

Edge points are constructed on each edge. These points are three eighths of the sum of the two end points of the edge plus one eighth of the sum of the two other points that form the two triangles that share the edge in question.

Vertex points are constructed for each old vertex. A given vertex has n neighbor vertices. The new vertex point is one minus n times s times the old vertex, plus s times the sum of the neighboring vertices, where s is a scaling factor. For n equal to three, s is three sixteenths. For n greater than three, s is 1/n (5/8 - (3/8 + 1/4 cos(2π / n))²)

Each old triangle will have three edge points, one for each edge, and three vertex points, one for each vertex. To form the new triangles these points are then connected, vertex-edge-edge, creating four triangles. One new triangle touches each old vertex, and the last new triangle sits in the center, connecting the three edge points.

Because Loop surfaces must start with a triangle mesh, the resulting surface cannot be directly compared to the above two schemes, which work with arbitrary polygons. The same sequence is demonstrated here on a tessellated version of the polygonal mesh used above.

Step 0
The base mesh has been tessellated into 140 triangles. Different tessellations would yield somewhat different resulting Loop surfaces.

Step 1
After one application of the Loop scheme we see similar results to the Catmull-Clark mesh. The ends of the "U" have become pointed. The new mesh consists of 560 triangles.

Step 2
After a second iteration of subdivision the mesh consists of 2,240 triangles.

Step 3
A final iteration of Loop gives a 8,960 triangle mesh. It consists of roughly twice as many triangles as the other surfaces had polygons, as we might expect. The other schemes generated primarily quadrilaterals, while a triangle-generating scheme will require two triangles for each quadrilateral.

Loop subdivision surfaces have extraordinary points for each vertex in the original mesh that had a valence other than six. It is impossible to form a closed surface entirely out of vertices of valency six, so Loop surfaces will always have extraordinary points.

Because the cube below has been broken into triangles with a vertex in the center of each original cube face, the effect of the smoothing is less dramatic than in the above example cubes. You should be able to see the four triangles that correspond to each triangle in the prior level of subdivision.

Tessellated cube, smoothed twice with repeated applications of the Loop scheme (Rendered without hidden lines to keep the image clean)

Other Schemes

There are quite a few other schemes, some of which are described in the resources below. The Butterfly scheme and a closely related scheme known as Modified Butterfly also use triangle meshes. Others include the Kobbelt Interpolation Quadrilateral scheme, the Local Surface Fitting scheme, and many variations on the themes of the above. The rules given for the above schemes are usually only suitable for closed surfaces. Surfaces with boundaries need special case rules to handle the boundary without unpleasant artifacts.

Interactive Examples

The OFF Tools page on this site has Java applications that I wrote for applying Catmull-Clark and Doo-Sabin subdivision to OFF files. My more advanced program MeshMan implements these two and Midpoint, Loop, Butterfly, Modified Butterfly, and Sqrt(3) as well, also on OFF files in an interactive OpenGL Windows application.

Download the Files

The zip file below contains the following files:

asu.off - The original wireframe version of the letters ASU.
asu_tri.off - The file asu.off, tessellated into triangles.
a.off - The A of ASU.
s.off - The S of ASU.
u.off - The U of ASU.
asuds1.off - The resulting mesh after applying the Doo-Sabin algorithm to asu.off once.
asuds2.off - The resulting mesh after applying the Doo-Sabin algorithm to asu.off twice.
asuds3.off - The resulting mesh after applying the Doo-Sabin algorithm to asu.off three times.
asucc1.off - The resulting mesh after applying the Catmull-Clark algorithm to asu.off once.
asucc2.off - The resulting mesh after applying the Catmull-Clark algorithm to asu.off twice.
asucc3.off - The resulting mesh after applying the Catmull-Clark algorithm to asu.off three times.
asuloop1.off - The resulting mesh after applying the Loop algorithm to asu_tri.off once.
asuloop2.off - The resulting mesh after applying the Loop algorithm to asu_tri.off twice.
asuloop3.off - The resulting mesh after applying the Loop algorithm to asu_tri.off three times.

subdivide.zip - 282KB.