---

layout: default title: "Catmull-Clark Subdivision" parent: Global Operations grand_parent: "A2: MeshEdit" permalink: /meshedit/global/catmull/ usemathjax: true

---

Catmull-Clark Subdivision

For an in-practice example, see the User Guide.

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:

1. setting the new vertex position at each face $<span class="arithmatex"><span class="MathJax_Preview">f</span><script type="math/tex">f$ to the average of all its original vertices (exactly as in linear subdivision),
2. setting the new vertex position at each edge $<span class="arithmatex"><span class="MathJax_Preview">e</span><script type="math/tex">e$ to the average of the new adjacent face positions (from step 1) and the original edge endpoint positions, and
3. setting the new vertex position at each vertex $<span class="arithmatex"><span class="MathJax_Preview">v</span><script type="math/tex">v$ to the weighted sum

where $<span class="arithmatex"><span class="MathJax_Preview">n</span><script type="math/tex">n$ is the degree of vertex $<span class="arithmatex"><span class="MathJax_Preview">v</span><script type="math/tex">v$ (i.e., the number of faces containing $<span class="arithmatex"><span class="MathJax_Preview">v</span><script type="math/tex">v$), and

• $<span class="arithmatex"><span class="MathJax_Preview">Q</span><script type="math/tex">Q$ is the average of all new face position for faces containing $<span class="arithmatex"><span class="MathJax_Preview">v</span><script type="math/tex">v$,
• $<span class="arithmatex"><span class="MathJax_Preview">R</span><script type="math/tex">R$ is the average of all original edge midpoints for edges containing $<span class="arithmatex"><span class="MathJax_Preview">v</span><script type="math/tex">v$, and
• $<span class="arithmatex"><span class="MathJax_Preview">S</span><script type="math/tex">S$ is the original vertex position for vertex $<span class="arithmatex"><span class="MathJax_Preview">v</span><script type="math/tex">v$.

In other words, the new vertex positions are an "average of averages." (Note that you will need to divide by $<span class="arithmatex"><span class="MathJax_Preview">n</span><script type="math/tex">n$ both when computing $<span class="arithmatex"><span class="MathJax_Preview">Q</span><script type="math/tex">Q$ and $<span class="arithmatex"><span class="MathJax_Preview">R</span><script type="math/tex">R$, and when computing the final, weighted value---this is not a typo!)

Your implementation of linear and Catmull-Clark subdivision will be very similar - only differing on how to compute the vertices new positions at each edge and vertex.

This step should be implemented in the method HalfedgeMesh::catmullclark_subdivide_positions in student/meshedit.cpp.

This subdivision rule is not required to support meshes with boundary, unless the implementer wishes to go above and beyond.