On-Line Geometric Modeling Notes
GENERATING A CUBIC SUBDIVISION CURVE

Overview

Given an arbitrary control polygon we can use a simple refinement process that generates a sequence of control polygons from the original. This sequence converges in the limit to a curve.

In the cubic case, the procedure is straightforward to define, and it is this procedure that we review in these notes.

For a pdf version of these notes look here.

The Refinement of the Control Polygon

Given a control polygon ${\cal P} = \left\{ {\bf P} _0, {\bf P} _1, ..., {\bf P} _n \right\}$ we generate a refinement of ${\cal P}$ by generating a new control polygon

$$\left\{ {\bf E} _0, {\bf V} _0, {\bf E} _1, {\bf V} _1, {\bf E} _2, ..., {\bf E} _{n-2}, {\bf V} _{n-2}, {\bf E} _{n-1} \right\}$$

where the ${\bf E} _i$, the edge points, lie on the edges of the original control polygon, and the ${\bf V} _i$, the vertex points, correspond to the original vertices of the control polygon. The new control polygon has $2n-1$ control points (the original has $n+1$) - and thus each refinement step increases the number of points in the control polygon.

The rules to calculate the vertex and edge points come from the subdivision process for a uniform B-spline curve. In short,

$${\bf E} _i \: = \: \frac{ {\bf P} _i + {\bf P} _{i+1}}{2}$$

and

$${\bf V} _i \: = \: \frac{ {\bf E} _i + 2 {\bf P} _i + {\bf E} _{i+1}}{4}$$

It is easy to see these how these rules work if we consider the following example. Consider the set of control points as shown in the example below.

We calculate the edge points as the midpoints of the line segments forming the control polygon

$${\bf E} _i \: = \: \frac{ {\bf P} _i + {\bf P} _{i+1}}{2}$$

and vertex points as the average of twice the control point and the two edge points adjacent to the control point

$${\bf V} _i \: = \: \frac{ {\bf E} _i + 2 {\bf P} _i + {\bf E} _{i+1}}{4}$$

We note that since ${\bf V} _i$ can be written

$${\bf V} _i = \frac{\frac{ {\bf E} _i + {\bf P} _i}{2} + \frac{ {\bf P} _i + {\bf E} _{i+1}}{2}}{2}$$

then ${\bf V} _i$ is the midpoint of the line segment whose endpoints are the midpoints of the line segments $\overline{ {\bf E} _i {\bf P} _i}$ and $\overline{ {\bf P} _i {\bf E} _{i+1}}$.

Connecting the edges and vertex points generated by the refinement gives us the new control polygon.

Generating the Subdivision Curve

The new set of edge points and vertex points now becomes the new control polygon, and can be further refined - in our example generating

One can see the curve actually taking shape now, and it is easy to see that if we continue this process, choosing a new refinement by generating the edge points and vertex points, we will get closer and closer to the curve.

Summary

The refinement process for cubic subdivision curves is quite straightforward. In general this process is an infinite process and in the limit converges to a uniform cubic B-spline curve. If we wish to draw the curve, it is easy to define a process where the original control polygon is refined several times and the resulting control polygon is then drawn (by connecting the points of the control polygon with straight line segments) to represent the curve. With some further analysis it is also possible to directly calculate points on the limit curve knowing only the vertex and edges points of the refinement.

Bibliography

1

CATMULL, E., AND CLARK, J.
Recursively generated B-spline surfaces on arbitrary topological meshes.
Computer-Aided Design 10 (Sept. 1978), 350-355.