Catmull Clark Subdivision
The only difference between Catmull-Clark and linear subdivision is the choice of positions for new vertices. Whereas linear subdivision simply takes a uniform average of the old vertex positions, Catmull-Clark uses a very carefully-designed weighted average to ensure that the surface converges to a nice, round surface as the number of subdivision steps increases. The original scheme is described in the paper "Recursively generated B-spline surfaces on arbitrary topological meshes" by (Pixar co-founder) Ed Catmull and James Clark. Since then, the scheme has been thoroughly discussed, extended, and analyzed; more modern descriptions of the algorithm may be easier to read, including those from the Wikipedia and this webpage. In short, the new vertex positions can be calculated by:
- setting the new vertex position at each face f to the average of all its original vertices (exactly as in linear subdivision),
- setting the new vertex position at each edge e to the average of the new face positions (from step 1) and the original endpoint positions, and
- setting the new vertex position at each vertex v to the weighted sum
where n is the degree of vertex v (i.e., the number of faces containing v), and
- Q is the average of all new face position for faces containing v,
- R is the average of all edge midpoints for edges containing v, and
- S is the original vertex position for vertex v.
In other words, the new vertex positions are an "average of averages." (Note that you will need to divide by n both when computing Q and R, and when computing the final, weighted value---this is not a typo!)
Apart from changing the way vertex positions are computed, there should be no difference in your implementation of linear and Catmull-Clark subdivision.
This step should be implemented in the method