We can define subdivision abstractly as the process of taking a coarse shape and refining it to produce another shape that is more visually attractive (usually smooth). Subdivision schemes are typically of the form take a shape and perform some operation on it to produce another shape. This output shape is then fed back into the subdivision scheme again and again until the desired level of detail is achieved. In the limit, this process should converge to some shape.

In order to demonstrate this, we will provide an example of a simple subdivision scheme that operates on a 2D curve. This scheme is essentially two passes over the shape: linear subdivision, and averaging.

Our curve will be defined to consist of vertices and edges between those vertices. Linear subdivision basically puts vertices in the middle of each of the edges of the curve. You can see an example of linear subdivision on a square below.

Averaging

To perform the averaging pass on the curve we find the centroid of all of the edges. In other words, we average the vertices connected to each end of the edge. Then, for each edge that touches a vertex, we take the average of all of the centroids of those edges. If this operation alone is repeated, then the curve will shrink down to a point. An example is shown below.

Figure 2. Averaging pass on a square

Now to perform subdivision we essentially combine the two passes. First, we linearly subdivide the curve. Second, we perform averaging on the output of the linear subdivision pass. We'll call this combined pass subdivision. An example of this is shown below. Notice how the curve is linearly subdivided first, then averaged.

Figure 3. Linear subidivision followed by averaging on a square

Extending this to surfaces

If you wanted to extend this to surfaces, you just have to perform the analagous operations on quadrilaterals. Linear subdivision consists of putting new vertices on the edges of the face as well as in the center of the face and connecting them to form four new quads. Smoothing would be taking the centroid of the four vertices of the quad (averaging them together). Then, for each quad touching a vertex, average all of the centroids of those quads together.

An Example

Below is a program that will let you try out these operations on curves. The green boxes are the vertices of the curve. You can drag the boxes around in the area to produce different curves. To start over, just press the appropriate shape button. The button labeled "subdivide" combines both linear subdivision and averaging into one operation.

A browser that supports Java is required to view this example.