On-Line Geometric Modeling Notes
DIRECT CALCULATION OF POINTS
ON CUBIC SUBDIVISION CURVES

Given an initial control polygon we can define a refinement process that generates a sequence of control polygons from the original. In the limit, this sequence converges to the uniform B-spline curve specified by the original control polygon. By examining this refinement process from a different angle, we can specify a procedure that allows us to directly calculate points on the curve.

Direct Calculation of Points on the Curve

In the cubic case, we define the general refinement procedure by classifying the points of a refinement as either vertex'' or edge'' points. Using this classification we can cleverly write this refinement process in a matrix form. This form takes a control point and its two adjacent control points of a refinement and applies a refinement matrix as follows

where is called the refinement matrix and is given by

Here we have denoted the control points as vertex and edge points. This procedure creates two new edge points and a vertex point which are part of a new control polygon that represents the curve. We can apply again and obtain

where . In general, we can generate points on the th refinement by applying -times. In the limit, as approaches infinity, we obtain a point on the curve.

We call call this point and note that it is equal to .

Calculating the Limit Point

The suprising thing is that we can actually calculate this limit. We utilize the fact that the refinement matrix can be diagonalized, which defines the matrix by

where

is the matrix whose columns are the right eigenvectors of ,

is the matrix whose rows are the left eigenvectors of , and is the matrix of eigenvalues

Since , this allows us to write

(Noting that ) or, in general

To calculate the limit, first consider applying -times

Now as , this approaches

and by substituting for and , this becomes

That is, the vertex and edge points all converge to the same value, which is just the dot product of the left eigenvector of that corresponds to the eigenvalue one, and the original vertex-edge vector of the refinement - obtaining the point .

In short, given any vertex with corresponding edge points and , we can directly calculate points on the curve by dotting the left eigenvector that corresponds to the eigenvalue by the vertex-edge vector

This says that any vertex point on any refinement directly corresponds to a point on the curve.

Examples

Consider a cubic uniform B-spline curve with control polygon . This curve can be written as

Consider the first step of the refinement using as the vertex with and as the two respective edge points. The corresponding point on the curve can be calculated directly as

which is exactly the point on the curve.

Similarly we can calculate a point on the curve using the vertex with and as the two respective edge points. In this case, we find that this is exactly the point on the curve.

Carrying this one step further, suppose we generate one full refinement of the curve, generating new edge and vertex points.

These new points become the input to the refinement process, and if we consider as the vertex point, with and as the respective edge points, we obtain the point on the curve

which is exactly .

Summary

It is possible, using eigenanalysis, to formulate simple procedures that calculate directly a point on the limit curve. This, in many cases, can be used to replace the overall refinement process.

The tangent vector on the curve at this limit point can also be directly calculated, by much the same procedure.

## Bibliography

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

2
HALSTEAD, M., KASS, M., AND DEROSE, T.
Efficient, fair interpolation using Catmull-Clark surfaces.
In Computer Graphics (SIGGRAPH '93 Proceedings) (Aug. 1993), J. T. Kajiya, Ed., vol. 27, pp. 35-44.

Ken Joy
2000-11-28