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

where is the original control polygon and 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.

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 and the two points and - 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 and two new edge points and .

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

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

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

the refinement matrix.

So How Do You Do Refinement In General?

Given a control polygon , we utilize the vectors

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

These new points are then assembled into new control polygon

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.

Ken Joy
2000-11-28