Catmull Clark

2 min read•1 page

In 1978, Ed Catmull (founder of Pixar) and Jim Clark needed a way to render perfectly smooth 3D characters without forcing artists to manage millions of polygons. They invented a way to mathematically "smooth" a blocky, low-poly cage into a perfect curve.

Corner Cutting:

1. The foundation of 3D subdivision actually comes from 1D lines (Chaikin's Algorithm). 2. Imagine a jagged zigzag line. 3. If you "chop off" every sharp corner by creating new points at the 25% and 75% marks of every segment... 4. ...and you repeat this process 3 or 4 times, the jagged line turns into a perfectly smooth bezier curve! 5. Pixar realized they could apply this exact same "corner cutting" math to 3D polygons.

python

1# Chaikin's Curve Algorithm (1D Subdivision)
2def subdivide_line(points):
3    """Cut off the corners to make it smooth."""
4    
5    new_points = []
6    
7    for i in range(len(points) - 1):
8        p1 = points[i]
9        p2 = points[i+1]
10        
11        # Instead of 1 line, make 2 new points at 25% and 75%
12        q = p1 * 0.75 + p2 * 0.25
13        r = p1 * 0.25 + p2 * 0.75
14        
15        new_points.extend([q, r])
16        
17    return new_points

Iterations

0.00

2 min read•1 page

To subdivide a 3D mesh, the Catmull-Clark algorithm runs exactly 4 steps. The very first step is to find the absolute center of every single polygon face in the object.

Centroid Averaging:

1. Look at a single polygon face (e.g., a Quad with 4 corners). 2. Calculate the average of those 4 corner positions. 3. Place a brand new "Face Point" exactly at that average coordinate. 4. Do this for every face on the entire model. 5. Notice that if the face is completely flat, the Face Point is perfectly flush. If the face is bent (non-planar), the Face Point hovers in the middle of the bend.

python

1# Step 1: The Face Point
2def calculate_face_points(mesh):
3    """The average of all vertices making up the face."""
4    
5    face_points = []
6    
7    for face in mesh.faces:
8        
9        # Add up all the X, Y, Z coordinates
10        total_x = sum([v.x for v in face.vertices])
11        total_y = sum([v.y for v in face.vertices])
12        total_z = sum([v.z for v in face.vertices])
13        
14        # Divide by how many vertices there are (usually 4 for a Quad)
15        count = len(face.vertices)
16        
17        face_point = Point(total_x/count, total_y/count, total_z/count)
18        face_points.append(face_point)
19        
20    return face_points

Action (Original / Face Point)

0.00

2 min read•1 page

Step 2 of the Catmull-Clark algorithm creates a new point in the middle of every single Edge. But it doesn't just split the edge blindly; it uses the Face Points we just calculated to ensure the surface curves smoothly.

The 4-Point Average:

1. Look at a single edge shared by two polygons. 2. Take the two vertices that make up that edge. 3. Take the two newly created Face Points from the polygons sharing that edge. 4. Add all 4 points together and divide by 4. 5. This mathematically "pulls" the new Edge Point slightly inward toward the center of the polygons, which creates the beautiful curving effect!

python

1# Step 2: The Edge Point
2def calculate_edge_points(edge, connected_faces):
3    """Averages the edge itself AND the faces touching it."""
4    
5    # 1. The two vertices making up the original edge
6    v1 = edge.vertex_A
7    v2 = edge.vertex_B
8    
9    # 2. The Face Points of the two polygons sharing this edge
10    f1 = connected_faces[0].face_point
11    f2 = connected_faces[1].face_point
12    
13    # 3. The Edge Point is the average of all 4!
14    total_x = v1.x + v2.x + f1.x + f2.x
15    total_y = v1.y + v2.y + f1.y + f2.y
16    total_z = v1.z + v2.z + f1.z + f2.z
17    
18    edge_point = Point(total_x/4, total_y/4, total_z/4)
19    return edge_point

Action (Original / Midpoint / Edge Point)

0.00

2 min read•1 page

Step 3 is the most important step in the entire algorithm. We have created new points on the Faces and Edges, but we must also move the original vertices. If we leave the original sharp corners where they are, the mesh won't actually become smooth!

The Barycentric Formula:

1. Look at an original corner vertex. Let's assume 4 faces meet at this corner (n=4). 2. Calculate F: The average of the 4 Face Points surrounding it. 3. Calculate R: The average of the midpoints of the 4 edges touching it. 4. We combine them using a special weighted average formula. 5. This mathematically "drags" the sharp corner inward toward the center of the mesh. The sharper the corner, the further it gets dragged!

python

1# Step 3: Moving the Original Vertices
2def update_vertex_point(vertex, connected_faces, connected_edges):
3    """The math that physically shrinks and smooths the mesh."""
4    
5    n = len(connected_faces) # e.g., 4 faces meet at this vertex
6    
7    # Average of the Face Points touching this vertex
8    F = average(connected_faces)
9    
10    # Average of the Edge Midpoints touching this vertex
11    R = average_midpoints(connected_edges)
12    
13    # The original Vertex position
14    P = vertex.position
15    
16    # The Catmull-Clark Barycentric Formula:
17    # (F + 2R + (n - 3)P) / n
18    new_x = (F.x + 2*R.x + (n-3)*P.x) / n
19    
20    return Point(new_x, new_y, new_z)

Update (Original / Averages / Moved)

0.00

2 min read•1 page

We now have a cloud of new points (Face Points, Edge Points) and our original points have been moved. The final step of the algorithm is to draw new lines connecting them all together!

Quad Topology:

1. Every single Face Point connects outward to the Edge Points surrounding it. 2. Every single Edge Point connects inward to the Face Point, and outward to the moved Original Vertices. 3. This means that a single, original Quad polygon gets sliced perfectly into 4 smaller Quads. 4. Even if you feed the algorithm a Triangle or an N-gon, it will always output pure Quads! This is why 3D artists love Catmull-Clark.

python

1# Step 4: Connecting the New Dots
2def split_quad(face, face_point, edge_points, new_vertices):
3    """1 Quad becomes 4 smaller Quads."""
4    
5    new_quads = []
6    
7    # We loop through all 4 corners of the original Quad
8    for i in range(4):
9        
10        # We build a new Quad using:
11        # 1. The moved Original Vertex
12        # 2. The new Edge Point on one side
13        # 3. The new Face Point in the middle
14        # 4. The new Edge Point on the other side
15        
16        v1 = new_vertices[i]
17        v2 = edge_points[i]
18        v3 = face_point
19        v4 = edge_points[(i - 1) % 4]
20        
21        new_quads.append(Quad(v1, v2, v3, v4))
22        
23    return new_quads

Split (Original / Points / New Quads)

0.00

2 min read•1 page

If you run Catmull-Clark 1 time, you get a smoother mesh. If you run it 100 times, you get an incredibly smooth mesh, but your computer will run out of RAM because you just generated 10 billion polygons.

Skipping to Infinity:

1. Mathematicians studied the Catmull-Clark equations and realized something amazing. 2. They found a formula that calculates exactly where a point would end up if you ran the algorithm an infinite number of times. 3. This infinite result is called the Limit Surface. 4. Modern game engines (like Unreal Engine) don't actually subdivide polygons 100 times. They just plug the vertices directly into the Limit Formula and use the GPU to render a perfectly smooth mathematical patch (Hardware Tessellation).

python

1# Infinite Smoothing (The Limit Surface)
2def get_limit_position(vertex, connected_faces, connected_edges):
3    """Where does the point end up after infinite subdivisions?"""
4    
5    n = len(connected_faces)
6    
7    # Calculate the same F and R averages as before
8    F = average(connected_faces)
9    R = average_midpoints(connected_edges)
10    P = vertex.position
11    
12    # The Limit Formula (Notice the slightly different weights!)
13    # (F + 2R + (n^2 - 3)P) / (n^2)
14    limit_x = (F.x + 2*R.x + (n*n - 3)*P.x) / (n*n)
15    
16    return Point(limit_x, limit_y, limit_z)

Projection (Start / Step 1 / Limit)

0.00

2 min read•1 page

When we run the 4 steps of Catmull-Clark on a standard cube, the sharp 90-degree corners get pulled inward, and the flat faces bulge outward slightly.

Subdivision Levels:

1. Level 0: A standard cube with 6 faces (6 Quads). 2. Level 1: The cube is split into 24 Quads. It looks like a lumpy, rounded box. 3. Level 2: The box is split into 96 Quads. It is starting to look like a sphere. 4. Level 3: 384 Quads. It is now a perfectly smooth sphere! 5. Pixar characters are typically modeled at Level 0 by the artists, and automatically subdivided to Level 3 or 4 by the computer during rendering.

python

1# The Full Pipeline
2def catmull_clark_subdivision(mesh, iterations):
3    """How Pixar smooths Woody and Buzz."""
4    
5    current_mesh = mesh
6    
7    for i in range(iterations):
8        # 1. Calculate Face Points
9        f_pts = calculate_face_points(current_mesh)
10        
11        # 2. Calculate Edge Points
12        e_pts = calculate_edge_points(current_mesh, f_pts)
13        
14        # 3. Update Original Vertices
15        new_v = update_vertex_points(current_mesh, f_pts, e_pts)
16        
17        # 4. Split Quads and reconnect
18        current_mesh = split_all_quads(current_mesh, f_pts, e_pts, new_v)
19        
20    return current_mesh

Subdivision Level

0.00