3-Dimensional Smoothing: Catmull-Clark Subdivision
Articles —> 3-Dimensional Smoothing: Catmull-Clark Subdivision
Catmull-Clark subdivision is a method to smooth a 3-dimensional polygon mesh surface by dividing the surface's polygons into smaller polygons, repositioning the previous vertices based upon adjacent vertices. The method takes each primitive polygon contained in the mesh and divides the polygon into quadrilaterals, constructing new vertices based upon the averages and adjusting the previous vertices of the original polygon based upon the surrounding environment.
The Catmull Clark algorithm is fast and effective, and even capable of smoothing a cube down to a sphere (see below). Named in part after Edwin Catmull, currently the president of Pixar, the subdivision technique has been used in animations such as A Bug's Life, Finding Nemo, and The Incredibles1. Thus, the application of the algorithm can be useful in all sorts of rendering scenarios, from science to games to animated movies.
The technique for Catmull Clark starts with a list - or mesh - of input polygons. For each polygon - or face - P with vertices V in the mesh:
Calculate the Face Point - the average of all vertices of the polygon face. For 3-dimensions, this is simply averaging the x/y/z values of each vertex.
For each edge, calculate the edge points - an edge point is the average of both the end point vertices and the face points of the faces sharing said edge.
For each vertex v of the polygon P, adjust its 3-dimensional coordinates by using the weighted average of the a) edge points R of the edges containing the vertex v and b) the face points F of the polygon/faces containing v and c) the previous values of the vertex v. The weighted average abides by the formula:
Where n is the number of face points (should be equal to the number of edge points).
- Construct the new mesh subdivision quadrangles by connecting the newly created edge and face points together with the old, repositioned vertex.
- It should be noted that other properties of a vertex - for instance the vertex surface normal - can be calculated in a similar manner.
The newly created primitives together will generally look smoother than the previous mesh, and recursive/iterative application results in further smoothing of the overall mesh shape.
To see Catmull Clark in action I implemented the algorithm in java2, using OpenGL via JOGL for visualization. The algorithm itself is fairly straightforward - given the polygons I was dealing with I was forced to use a series of hash tables (HashMap) to keep track of vertices and their shared edges/polygons. As a test case for proper algorithm implementation, I used the classic demonstration of Catmull Clark: begin with a cube and visualize each iteration of the smoothing, the results of which should smooth the cube down to nearly a sphere. Its impressive to see the subdivision in action - after only 2 iterations the cube corners were smoothed to nearly a sphere (see top right image below), a few more iterations of Catmull Clark results in a shape approximate to a sphere (see bottom image below). Of course, the more iterations one uses the more vertices one must deal with: in the bottom case below (six iterations) there is nearly 100,000 quads to render: a bit overkill but a lesson in how the algorithm subdivides.
 |
 |
 |
Demonstration of Catmull Clark subdivision smoothing. The initial cube shown in the top left and the first 2 iterations of the algorithm are shown top right. The final iteration 6 shown on bottom.
A more complex example is shown below. This example shows the surface of a protein reconstructed from 3-dimensional crystal structure coordinates using marching cubes, in which colors indicate positive and negative charges. In this example, three iterations of Catmull Clark were performed on the initial triangle mesh resulting in 131,520 quadrangles.
Protein surface, constructed using Marching Cubes, with (right) and without (left) Catmull Clark smoothing.
- Nvidia: Adaptive Tessellation and Subdivision
- Java source code available upon request.
- Wikipedia - Catmull Clark Subdivision Surface
Comments
- addison dophy - July, 12, 2020
This 3-d Dimensional Smoothing is unbelievably good