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.

For a pdf version of these notes look here.

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

$$\left[ \begin{array}{l} {\bf V} ^1 \\ {\bf E} _0^1 \\ {\bf E}... ...t[ \begin{array}{l} {\bf V} \\ {\bf E} _0 \\ {\bf E} _1 \end{array}\right]$$

where $A$ is called the refinement matrix and is given by

$$A \: = \: \frac{1}{8} \left[ \begin{array}{rrr} 6 & 1 & 1 \\ 4 & 4 & 0 \\ 4 & 0 & 4 \end{array}\right]$$

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 $A$ again and obtain

$$\left[ \begin{array}{l} {\bf V} ^2 \\ {\bf E} _0^2 \\ {\bf E}... ...t[ \begin{array}{l} {\bf V} \\ {\bf E} _0 \\ {\bf E} _1 \end{array}\right]$$

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

We call call this point ${\bf V} ^{\infty}$ and note that it is equal to $\lim_{k \rightarrow \infty} {\bf V} ^k$.

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 $A$ by

$$A \: = \: R \Lambda L$$

where

$$R \: = \: \left[ \begin{array}{rrr} 1 & 0 & -1 \\ 1 & 1 & 2 \\ 1 & -1 & 2 \end{array}\right]$$

is the matrix whose columns are the right eigenvectors of $A$,

$$L \: = \: \left[ \begin{array}{rrr} \frac{2}{3} & \frac{1}{6} & \... ... -\frac{1}{2} \\ -\frac{1}{3} & \frac{1}{6} & \frac{1}{6} \end{array}\right]$$

is the matrix whose rows are the left eigenvectors of $A$, and $\Lambda$ is the matrix of eigenvalues

$$\Lambda \: = \: \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 0 & \frac{1}{2} & 0 \\ 0 & 0 & \frac{1}{4} \end{array}\right]$$

Since $R=L^{-1}$, this allows us to write

$$A^2 = (R \Lambda L)^2 = R \Lambda L R \Lambda L = R \Lambda \Lambda L = R \Lambda^2 L$$

(Noting that $R=L^{-1}$) or, in general

$$A^k \: = \: R \Lambda^k L$$

To calculate the limit, first consider applying $A$ $k$-times

$$\left[ \begin{array}{l} {\bf V} ^k \\ {\bf E} _0^k \\ {\bf E} _1^k \end{array}\right] = A^k \left[ \begin{array}{l} {\bf V} \\ {\bf E} _0 \\ {\bf E} _1 \end{array}\right]$$

$$= \left( R \Lambda L \right) ^k \left[ \begin{array}{l} {\bf V} \\ {\bf E} _0 \\ {\bf E} _1 \end{array}\right]$$

$$= R \Lambda^k L \left[ \begin{array}{l} {\bf V} \\ {\bf E} _0 \\ {\bf E} _1 \end{array}\right]$$

$$= R \left[ \begin{array}{ccc} (1)^k & 0 & 0 \\ 0 & \left( \fra... ...ay}{l} {\bf V} \\ {\bf E} _0 \\ {\bf E} _1 \end{array}\right]$$

Now as $k \rightarrow \infty$, this approaches

$$R \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 &... ...[ \begin{array}{l} {\bf V} \\ {\bf E} _0 \\ {\bf E} _1 \end{array}\right]$$

and by substituting for $R$ and $L$, this becomes

$$R \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0... ...ay}{l} {\bf V} \\ {\bf E} _0 \\ {\bf E} _1 \end{array}\right] = \left[ \begin{array}{rrr} 1 & 0 & -1 \\ 1 & 1 & 2 \\ 1 & -1... ...ay}{l} {\bf V} \\ {\bf E} _0 \\ {\bf E} _1 \end{array}\right]$$

$$= \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 0 &... ...ay}{l} {\bf V} \\ {\bf E} _0 \\ {\bf E} _1 \end{array}\right]$$

$$= \left[ \begin{array}{rrr} \frac{2}{3} & \frac{1}{6} & \frac{1... ...ay}{l} {\bf V} \\ {\bf E} _0 \\ {\bf E} _1 \end{array}\right]$$

$$= \frac{1}{6} \left[ \begin{array}{rrr} 4 & 1 & 1 \\ 4 & 1 & 1... ...ay}{l} {\bf V} \\ {\bf E} _0 \\ {\bf E} _1 \end{array}\right]$$

That is, the vertex and edge points all converge to the same value, which is just the dot product of the left eigenvector of $A$ that corresponds to the eigenvalue one, and the original vertex-edge vector of the refinement - obtaining the point $\frac{1}{6} ( 4 {\bf V} + {\bf E} _0 + {\bf E} _1 )$.

In short, given any vertex ${\bf V} _i$ with corresponding edge points ${\bf E} _i$ and ${\bf E} _{i+1}$, we can directly calculate points on the curve by dotting the left eigenvector that corresponds to the eigenvalue $1$ by the vertex-edge vector

$$\frac{1}{6} \left[ \begin{array}{rrr} 4 & 1 & 1 \end{array}\right... ...in{array}{l} {\bf V} _i \\ {\bf E} _i \\ {\bf E} _{i+1} \end{array}\right]$$

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 $\left\{ {\bf P} _0, {\bf P} _1, {\bf P} _2, {\bf P} _3\right\}$. This curve can be written as

$${\bf P} (t) \: = \: \left[ \begin{array}{cccc} 1 & t & t^2 & t^3... ...{\bf P} _0 \\ {\bf P} _1 \\ {\bf P} _2 \\ {\bf P} _3 \end{array}\right]$$

Consider the first step of the refinement using ${\bf P} _1$ as the vertex with ${\bf P} _0$ and ${\bf P} _2$ as the two respective edge points. The corresponding point on the curve can be calculated directly as

$$\frac{1}{6} \left[ \begin{array}{rrr} 4 & 1 & 1 \end{array}\right... ...ht] \: = \: \frac{1}{6} \left( {\bf P} _0 + 4 {\bf P} _1 + {\bf P} _2 \right)$$

which is exactly the point ${\bf P} (0)$ on the curve.

Similarly we can calculate a point on the curve using the vertex ${\bf P} _2$ with ${\bf P} _1$ and ${\bf P} _3$ as the two respective edge points. In this case, we find that this is exactly the point ${\bf P} (1)$ 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 ${\bf E} _1$ as the vertex point, with ${\bf V} _1$ and ${\bf V} _2$ as the respective edge points, we obtain the point on the curve

$$\left[ \begin{array}{rrr} \frac{2}{3} & \frac{1}{6} & \frac{1... ...{l} {\bf E} _1 \\ {\bf V} _1 \\ {\bf V} _2 \end{array}\right] = \left[ \begin{array}{rrr} \frac{2}{3} & \frac{1}{6} & \frac{1... ...bf P} _1 + 6 {\bf P} _2 + {\bf P} _3 \right) \end{array}\right]$$

$$= \frac{1}{48} \left( {\bf P} _0 + 23 {\bf P} _1 + 23 {\bf P} _2 + {\bf P} _3 \right)$$

which is exactly ${\bf P} (\frac{1}{2})$.

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.