On-Line Geometric Modeling Notes
DEVELOPING A MATRIX EQUATION FOR REFINEMENT

Overview

The basic operation in the development of subdivision curves is the refinement procedure. In the cubic case, this can be written as

$$\left[ \begin{array}{l} {\bf P} _0^1 \\ {\bf P} _1^1 \\ {\bf ... ...{\bf P} _0 \\ {\bf P} _1 \\ {\bf P} _2 \\ {\bf P} _3 \end{array}\right]$$

where $\left\{ {\bf P} _0, {\bf P} _1, {\bf P} _2, {\bf P} _3 \right\}$ is the original control polygon and $\left\{ {\bf P} _0^1, {\bf P} _1^1, {\bf P} _2^1, {\bf P} _3^1, {\bf P} _4^1 \right\}$ is the result of the refinement.

In this case, we can also classify points of the refinement as vertex points and edge points, and this enables us to look at the problem from another point of view. Here we examine what happens to a particular control point (vertex point) under this refinement procedure. Examining this closely, we can develop an alternate matrix equation that can also be used to represent the refinement procedure.

For a pdf version of these notes look here

Refinement at a Vertex Point

The general idea in this development is to focus on a single vertex point of the control polygon and the two points immediately adjacent to this vertex. Call this vertex ${\bf V}$ and the two points ${\bf E} _0$ and ${\bf E} _1$ - as in the following figure.

In the refinement procedure, we note that vertex points and edge points alternate in the refined control polygon. We will use these three points to create a new vertex point ${\bf V} ^1$ and two new edge points ${\bf E} _0^1$ and ${\bf E} _1^1$.

We can write this in vector form (we note that the matrices are applied to vectors of points, and therefore the operations must be affine). Writing this in vector form

$$\left[ \begin{array}{l} {\bf V} \\ {\bf E} _0 \\ {\bf E} _1 \end{array}\right] \rm {is} \, \rm {refined} \, {\rm into} \left[ \begin{array}{l} {\bf V} ^1 \\ {\bf E} _0^1 \\ {\bf E} _1^1 \end{array}\right]$$

and we can calculate this refinement by using the equations to calculate the vertex and edge points - obtaining

$$\left[ \begin{array}{l} {\bf V} ^1 \\ {\bf E} _0^1 \\ {\bf E} _1^1 \end{array}\right] = \left[ \begin{array}{c} \frac{1}{4} \left( \frac{ {\bf V} + {... ...} _0}{2} \\ \frac{ {\bf V} + {\bf E} _1}{2} \end{array}\right]$$

$$= \left[ \begin{array}{c} \frac{1}{8} \left( {\bf E} _0 + 6 {\b... ...} _0}{2} \\ \frac{ {\bf V} + {\bf E} _1}{2} \end{array}\right]$$

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

and so this refinement process can be implemented as a matrix multiplication. We usually call the matrix

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

the refinement matrix.

So How Do You Do Refinement In General?

Given a control polygon $\left\{ {\bf P} _0, {\bf P} _1, ..., {\bf P} _n \right\}$, we utilize the vectors

$$\left[ \begin{array}{l} {\bf P} _1 \\ {\bf P} _0 \\ {\bf P} _... ...ray}{l} {\bf P} _{n-1} \\ {\bf P} _{n-2} \\ {\bf P} _n \end{array}\right]$$

and apply this refinement matrix to each vector, giving new vertex and edge points.

$$\left[ \begin{array}{l} {\bf V} _0 \\ {\bf E} _0 \\ {\bf E} _... ...{l} {\bf V} _{n-2} \\ {\bf E} _{n-2} \\ {\bf E} _{n-1} \end{array}\right]$$

These new points are then assembled into new control polygon

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

which forms the same refinement as with the subdivision method.

Summary

It is possible to write the refinement process for cubic subdivision curves in a matrix form which focuses on the action of the refinement on a single control point. In this case, we can calculate new vertex points and edges points just by applying the refinement matrix to the vertex-edge-point vector.

We note that this procedure does take more processor time than the refinement based upon binary subdivision. However, it will enable us to analyze the refinement operation further and generate a procedure to directly calculate a point on the curve without resulting to refinement.

Bibliography

1

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.