CatmullClark Subdivision
The CatmullClark 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 CatmullClark (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 “CatmullClark Algorithm” in their implementation.
StepbyStep 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 rundown 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 ) we need to calculate a new weighted vertex. This new vertex point (we’ll call this one ) is calculated thus:
a. Calculate vertex : this is the average of the facepoints from all faces surrounding .
b. Calculate vertex : this is the average of the edge midpoints from all edges containing .
c. Determine : this is simply the valence of , i.e. the number of faces containing the vertex .
d. Calculate vertex point : the weighted barycentre of , , and – which is done using the equation…
2. For each face that contains the original vertex , calculate it’s facepoint and the edgepoints of the two edges in that face that contain the original vertex.
3. For each of these faces, create a new face based on the four vertices. These are the newly created vertex, the facepoint of the face, and the edgepoints of the two edges in the face that contains the 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…






When completed on a 3D mesh (a quadbased 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 CatmullClark algorithm applied to a 3D unit cube are shown below.



Source Code:
You can download the source code for my 3D implementation of the CatmullClark 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.