On-Line Geometric Modeling Notes
DIRECT CALCULATION OF THE TANGENT VECTOR
ON CUBIC SUBDIVISION CURVES

Overview

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 a uniform B-spline curve. We can specify a procedure, based upon eigenanalysis of the refinement matrix, that allows us to exactly calculate a point on the limit curve.

We show in these notes, that by applying the eigenanalysis further we can also calculate directly the tangent vectors on the limit curve. In this case it is the eigenvector corresponding to the eigenvalue $\frac{1}{2}$ that plays the primary role.

For a pdf version of these notes look here

Direct Calculation of Points on the Curve

Select a control point ${\bf V} _i$ and let ${\bf E} _i$ and ${\bf E} _{i+1}$ be the adjacent control points (thought of as edge points of the refinement). Given the refinement matrix

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

we can show that repeatedly applying $A$ to the vector

$$\left[ \begin{array}{l} {\bf V} _i \\ {\bf E} _i \\ {\bf E} _{i+1} \end{array}\right]$$

gives us a point $V^{\infty}$ on the curve. This point can be directly calculated as 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 )$.

Tangent Vectors to the Curve

We can also use this analysis to address the tangent vectors on the curve. Given a vertex point ${\bf V}$ and the two adjacent edge points ${\bf E} _0$ and ${\bf E} _1$ respectively, we wish to look at the unit vectors

$$\lim_{k \leftarrow \infty} \frac{ {\bf E} _0^k - {\bf V} ^\infty}{\vert\vert {\bf E} _0^k - {\bf V} ^\infty \vert\vert}$$

which is the limit of unit vectors formed from the limit point on the curve to the converging edge points - this should converge to the unit tangent vector at the point ${\bf V} ^{\infty}$.

To calculate this quantity, we will use the diagonalization of the matrix $A$ which states that

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

Now, let ${\vec l }_1$, ${\vec l }_2$ and ${\vec l }_3$ be the left eigenvectors of the refinement matrix $A$, and ${\vec r }_1$, ${\vec r }_2$ and ${\vec r }_3$ be the row vectors of the matrix of right eigenvalues of the refinement matrix $A$. Then to calculate ${\bf E} _0^k$ we have

$${\bf E} _0^k = {\vec r }_2 \cdot \left[ \Lambda^k L {\vec {\bf P}} \right]$$

$$= {\vec r }_2 \cdot \left( \Lambda^k \left[ \begin{array}{c} {\... ...\\ {\vec l }_3 \cdot {\vec {\bf P}} \end{array}\right] \right)$$

$$= {\vec r }_2 \cdot \left[ \begin{array}{c} {\vec l }_1 \cdot {... ...} \right)^k {\vec l }_3 \cdot {\vec {\bf P}} \end{array}\right]$$

$$= {\vec l }_1 \cdot {\vec {\bf P}} + \left( \frac{1}{2} \right)^k {... ...\vec {\bf P}} + 2 \left( \frac{1}{4} \right)^k {\vec l }_3 \cdot {\vec {\bf P}}$$

where we have used ${\vec r }_2 = (1,1,2)$. Since

$${\bf V} ^\infty \: = \: {\vec l }_1 \cdot {\vec {\bf P}}$$

we have

$$\lim_{k \rightarrow \infty} \frac{ {\bf E} _0^k - {\bf V} ^{\infty}}{\vert\vert {\bf E} _0^k - {\bf V} ^\infty \vert\vert } = \lim_{k \rightarrow \infty} \left( {\left( \frac{1}{2} \right)^k ... ...eft( \frac{1}{4} \right)^k {\vec l }_3 \cdot {\vec {\bf P}} \vert\vert} \right)$$

$$= \lim_{k \rightarrow \infty} \left( { {\vec l }_2 \cdot {\vec {\bf... ...eft( \frac{1}{2} \right)^k {\vec l }_3 \cdot {\vec {\bf P}} \vert\vert} \right)$$

$$= { {\vec l }_2 \cdot {\vec {\bf P}} } \over {\vert\vert {\vec l }_2 \cdot {\vec {\bf P}} \vert\vert}$$

$$= { {\bf E} _0 - {\bf E} _1} \over {\vert\vert {\bf E} _0 - {\bf E} _1\vert\vert}$$

(note the division by $\left( \frac{1}{2} \right)^k$ in the second step).

Therefore, it is the left eigenvector of $A$ corresponding to the eigenvalue $\frac{1}{2}$ which determines the tangent vector to the curve, and given any vertex ${\bf V}$ with corresponding edge points ${\bf E} _0$ and ${\bf E} _1$, we can directly calculate the tangent vector at the limit point ${\bf V} ^\infty$ dotting the left eigenvector that corresponds to the eigenvalue $\frac{1}{2}$ by the vertex-edge vector

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

i.e. by subtracting ${\bf E} _{i+1}- {\bf E} _i$

Summary

It is possible, using eigenanalysis, to formulate simple procedures that calculate directly a point on the limit curve, and the tangent vector on the curve at this point. This makes this refinement procedure quite simple to use.

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.