In computer modeling, artists need to create all kinds of shapes. Shapes with straight edges are easy to make, but sometimes creating curves can be difficult. Subdivision is an algorithm to make the creation of curves easier on the artist, by allowing the artist to specify only a minimal number of points, and having the computer generate a curve based on the artist's input.
The algorithm works by taking the original points from the artist, and adding new points to it. The original points may be kept, moved, or even discarded; but after each iteration of the algorithm, the model has more points than it did before. At the same time, the line segments between the points get shorter, and the angles between those line segments get less and less sharp.
To help you picture this, consider this sequence of regular polygons:
Each polygon has more points than the one before, each polygon's sides are shorter than the previous polygons, and the angle between adjacent sides gets closer and closer to 180 degrees as the sequence progresses. The last polygon is virtually indistinguishable from a circle. The goal of subdivision is the same: generate points such that the many short straight lines make a shape that is indistinguishable from an actual curve.
There are three types of subdivision algorithms. (1) Interpolating algorithms keep the original points that the artist creates (called control points or the control polygon), and adds new points to the shape. (2) Approximating algorithms add new points to the shape, and then move the control points. (3) Corner-Cutting algorithms that add new points to the shape, and then remove the control points. We'll look at examples of each of these.
Interpolating subdivision is when the computer adds new points to the control polygon, and leaves the original points as they are.
A popular interpolating subdivision algorithm was developed by Leif Kobbelt. His algorithm takes a weighted average of four consecutive points in the control polygon and uses that for the new point to add to the control polygon. The weights are -1/16, 9/16, 9/16, and -1/16 respectively.
This animation shows two iterations of Kobbelt's subdivision algorithm on a square:
Approximating subdivision is when new points are added to the control points, and the control points are moved from their original positions.
Edwin Catmull and Jim Clark developed a straightforward approximating subdivision algorithm. First, they iterate through the edges, adding a subdivision point to the midpoint of each edge. Next, they iterate through the control points and adjusting them with a weighted average of its left neighbor, itself, and its right neighbor. The weights are 1/8, 3/4, and 1/8 respectively. If the vertex has only one neighbor (i.e. an end point in an open polygon), the the vertex is not adjusted.
This animation shows two iterations of Catmull-Clark subdivision on a square:
Corner-Cutting subdivision is when a pair of points are added for each edge in the control polygon. Then the corners are "cut" by removing the original points.
George Chaikin came up with a simple corner-cutting subdivision algorithm. For each edge, the two subdivision points are weighted averages of the edges endpoints. The weights for the first point are: 3/4 and 1/4, and the weights for the second point are: 1/4 and 3/4.
This animation shows two iterations of the Chaikin subdivision algorithm on a square:
Want more? Read about Subdivision Surfaces on Wikipedia.
Or experiment with 2D subdivision yourself using Jag's applet!