Catmull-Clark Subdivision

The Catmull-Clark subdivision algorithm is a geometric method used to create increasingly smooth surfaces from arbitrary mesh topologies. It was devised by Edwin Catmull and Jim Clark in 1978 at the University of California, Berkeley. This is my attempted explanation and implementation of their algorithm.

Uses:

Subdivision algorithms, such as Catmull-Clark (and SQRT[3]), are regularly used in computer animation software (such as those used in the development of video games & animated movies) to produce smoother meshes at closer draw distances. Since Catmull and Clarks’s  paper in 1978, a variety of improvements, optimisations & general tweaks have been proposed. This leads to slightly differing results across programs that list the “Catmull-Clark Algorithm” in their implementation.

Step-by-Step Breakdown:

I’ve hashed out a simple breakdown of the algorithm here with some [very] simple example figures. For simplicity’s sake, I’ll start with a brief run-down followed by some 2D examples (I won’t be using boundary faces here). I’m also making the assumption that any edge in the mesh will be winged by only two faces. I’ll add some screen captures from my 3D implementation of the algorithm towards the end of this post. First, some definitions from Catmull and Clark’s paper…

Facepoint – this is the resulting vertex when you average all the vertices in a particular face.
Edge Midpoint – this is simply the average of an edge’s start & end vertices.
Edgepoint – this is the resulting vertex when you average the midpoint of an edge & the face points of its two winging faces.

1.  For every vertex in the original mesh (let’s call this vertex P) we need to calculate a new weighted vertex. This new vertex point (we’ll call this one S) is calculated thus:

a. Calculate vertex F: this is the average of the facepoints from all faces surrounding P.
b.  Calculate vertex R: this is the average of the edge midpoints from all edges containing P.
c.  Determine n: this is simply the valence of P, i.e. the number of faces containing the vertex P.
d.  Calculate vertex point S: the weighted barycentre of P, F, and R – which is done using the equation…

    \[S = \frac{F + 2R + (n - 3)P}{n}\]

2.  For each face that contains the original vertex P, calculate it’s facepoint and the edgepoints of the two edges in that face that contain the original P vertex.
3.  For each of these faces, create a new face based on the four vertices. These are the newly created S vertex, the facepoint of the face, and the edgepoints of the two edges in the face that contains the P vertex (see below).

The newly created mesh will consist only of quadrilateral polygons, which may not be planar in all three dimensions. The new mesh will generally look smoother and more refined than the original mesh. To put the above steps into perspective, running the algorithm on a 2D mesh would go a little like this…

Let's start with a simple 2D mesh consisting of four triangles in a diamond pattern.

Let’s start with a simple 2D mesh consisting of four triangles in a diamond pattern.

Next we calculate the facepoint for each face (shown here in red).

Next we calculate the facepoint for each face (shown here in red).

Then we calculate the edge midpoints for each edge (shown in green).

Then we calculate the edge midpoints for each edge (shown in green).

Next we calculate the vertex point for the central vertex (shown in yellow here). Note that this doesn't always like over the original vertex.

Next we calculate the vertex point for the central vertex (shown in yellow here). Note that this doesn’t always lie over the original vertex.

For each face containing the original vertex, we connect the new vertex point, edge midpoints & the facepoints (one new face is shown here in blue).

For each face containing the original vertex, we connect the new vertex point, edge midpoints & the facepoints (one new face is shown here in blue).

Running the algorithm on the central point alone results in the creation of four new quadrilateral faces (as shown here).

Running the algorithm on the central point alone resulting in the creation of four new quadrilateral faces (as shown here).

When completed on a 3D mesh (a quad-based unit cube in this instance), the new weighted vertex points are pulled towards the centre of the object, smoothing the mesh. The result of the first two iterations of the Catmull-Clark algorithm applied to a 3D unit cube are shown below.

Unit cube before any iterations.

Unit cube after one iteration of the CC Algorithm.

Unit cube after two iterations of the CC Algorithm.

Source Code:

You can download the source code for my 3D implementation of the Catmull-Clark Algorithm as part of my larger ‘Liopleurodon’ library by cloning one of my GitHub repositories located here. The Liopleurodon library is a collection of Maven projects, utilities, and R&D snippets. If you have Maven setup correctly, simply run the ‘mvn install clean’ command from one of the project directories to build that project.


Image courtesy of tanakawho via Flickr.