Graphics Links at Holmes3D.net

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.

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.

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

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

**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*))^{2})

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)**

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.

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.

http://eros.cagd.eas.asu.edu/~farin/classes/cse477/cse477.html

Homepage for ASU's Introduction to Computer Aided Geometric Design course,
CSE 477. Subdivision surfaces are a covered topic in this course, and this
page has some extra notes on them at the bottom, in PostScript form.

http://graphics.cs.ucdavis.edu/CAGDNotes/Subdivision-Surfaces/Subdivision-Surfaces.html

Subdivision surfaces section of the on-line computer graphics notes pages
from the University of California, Davis. Excellent walk-through of Doo-Sabin
and Catmull-Clark, with pictures.

http://symbolcraft.com/pjl/graphics/subdivision/

A straightforward description of the Catmull-Clark scheme, with pictures
showing how the subdivision progresses.

http://www.scg.uwaterloo.ca/~hqle/subdivision/index.html

A nice page comparing Doo-Sabin, Catmull-Clark, and Loop surfaces, with
implementations as Maple routines.

http://www.ke.ics.saitama-u.ac.jp/xuz/mid-subdivision.html

A nice time-line of subdivision surface developments, somewhat outdated.

http://www.usc.edu/isd/pubarchives/networker/97-98/Sep_Oct_97/innerview-catmull.html

A fascinating interview with Edwin Catmull. If you are interested in the
history of computer animation, be sure to read this.

http://mrl.nyu.edu/projects/subdivision/

The New York University's Media Research Lab page on subdivision surfaces.
Subdivision surfaces are an active area of research at the lab. Many
interesting papers on the topic and source code for a VRML subdivision
implementation are available here.

http://www.multires.caltech.edu/teaching/courses/subdivision/

The 1998 SIGGRAPH course on Subdivision for Modeling and Animation. Lots of
material. The applets page has a few Java applets that demonstrate
fundamental ideas of subdivision surfaces.

http://mrl.nyu.edu/~dzorin/sig99/

The 1999 SIGGRAPH course on Subdivision for Modeling and Animation. Lots
of interesting material. Be sure to look through the
Subdivision Zoo by Denis Zorin. The presentation compares
different subidvision schemes. Includes Loop, Catmull-Clark, Butterfly,
Kobbelt, Doo-Sabin, and Midedge, and mentions limitations and extensions.

http://mrl.nyu.edu/publications/subdiv-course2000/

The 2000 SIGGRAPH course on Subdivision for Modeling and Animation. This
page contains primarily a 30MB PDF of course notes. One of the many papers
in this file is the description of how Pixar added subdivision surface support to
their RenderMan software.

http://www.gamasutra.com/features/20000411/sharp_pfv.htm

A Gamasutra.Com article, Subdivision Surface Theory. A nice article
that dives deeper into the theory of subdivision surfaces.

http://www.gamasutra.com/features/20000425/sharp_pfv.htm

A second Gamasutra.Com artical, Implementing Subdivision Surface Theory.
Follow-up to the above article, discussing implementation details for
Butterfly subdivision.

http://www.subdivision.org/subdivision/index.jsp

Resource collection for research into subdivision surfaces. Excellent Java
applets illustrate basic subdivision ideas, and the Links page lists
prominent researchers in the field.

http://www.intel.com/technology/systems/3d/subdiv.htm

A brief overview with example application areas, and two papers from Intel
researchers.

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.

Graphics Links at Holmes3D.net

Page contents copyright Ryan Holmes