On-Line Geometric Modeling Notes
REFINEMENT

Overview

Bézier curves, B-spline curves and subdivision curves are all based upon the input of a control polygon and the specification of an algorithmic method that contructs a curve from this sequence of points. Fundamental to these methods is the concept of a refinement. These refinement methods, as defined mathematically, can be quite complex. However, in practice they are quite simple and usually easy to implement.

In these notes, we discuss the mathematical notion of refinement.

For a pdf version of these notes look here.

What is a Refinement Scheme

A refinement process is a scheme which defines a sequence of control polygons

${\bf P} _0,\, {\bf P} _1,\, ...,\, {\bf P} _n$
${\bf P} _0^1,\, {\bf P} _1^1,\, ...,\, {\bf P} _{n_1}^1$
${\bf P} _0^2,\, {\bf P} _1^2,\, ...,\, {\bf P} _{n_2}^2$
$\vdots$
${\bf P} _0^k,\, {\bf P} _1^k,\, ...,\, {\bf P} _{n_k}^k$
$\vdots$

where for any $k>0$, each ${\bf P} _j^k$ can be written as

$${\bf P} _j^k \: = \: \sum_{i=0}^{n_{k-1}} \alpha_{i,j,k} {\bf P} _i^{k-1}$$

That is, any element ${\bf P} _j^k$ can be written as a linear combination of the control points $\left\{ {\bf P} _0^{k-1}, {\bf P} _1^{k-1}, ..., {\bf P} _{n_{k-1}}^{k-1} \right\}$ from the control polygon generated in the prior step. For each fixed $j$ and $k$ the sequence $\alpha_{i,j,k}$ is frequently called a mask.

This is a very general scheme, and quite complex to manage and analyze. It covers the cases where the number of control points in each successive polygon is allowed to increase (Chaikin's Curves and Doo-Sabin's subdivision surfaces are examples of this), or must decrease (de Casteljau's algorithm for generating Bézier Curves is an example of this).

It would be incredibly rare to use the entire set of control points from the $k-1$st sequence to calculate each new control point in the $k$th sequence as there may be thousands of points to consider - and so in general we assume that most of the $\alpha_{i,j,k}$s are zero. To simplify things further, we frequently limit this to a uniform scheme, where the $\alpha$s are independent of the level of refinement ($k$). This implies that the scheme is basically the same at each iteration of the refinement process. A further simplification, where the mask is the same for every point of a control polygon, is called a stationary scheme.

If all points that result from a refinement process lie on the lines joining the points of a control polygon, the process is typically called a ``corner cutting scheme''. An example of such a scheme is the Chaikin's Curve.

A Matrix Method for Refinement

The equation

$${\bf P} _j^k \: = \: \sum_{i=0}^{n_{k-1}} \alpha_{i,j,k} {\bf P} _i^{k-1}$$

can be written in matrix form as

$${\bf P} _j^k \: = \: \left[ \begin{array}{cccc} \alpha_{0,j,k} & ... ...{\bf P} _1^{k-1} \\ \vdots \\ {\bf P} _{n_k}^{k-1} \\ \end{array}\right]$$

and overall

$$\left[ \begin{array}{c} {\bf P} _0^k \\ {\bf P} _1^k \\ \vdot... ... P} _1^{k-1} \\ \vdots \\ {\bf P} _{n_{k-1}}^{k-1} \\ \end{array}\right]$$

where $S_k$ is the refinement matrix

$$S_k \: = \: \left[ \begin{array}{cccc} \alpha_{0,0,k} & \alpha_{1... ..._k,k} & \alpha_{1,n_k,k} & \cdots & \alpha_{n_{k-1},n_k,k} \end{array}\right]$$

and is an $(n_k+1) \times (n_{k-1}+1)$ matrix. In general it is best to think of this matrix as being sparse (i.e. most of the entries being zero) with non-zero entries clustered along the diagonal.

Example - A Stationary Uniform Refinement Scheme

Suppose we are given the control polygon $\left\{ {\bf P} _0, {\bf P} _1, ..., {\bf P} _n \right\}$. Define the refinement scheme by the following equation

$${\bf P} _j^k \: = \: \frac{1}{2} \left( {\bf P} _{j}^{k-1} + {\bf P} _{j+1}^{k-1} \right)$$

where $0 \leq j \leq n-k$ and $k = 0, 1, 2, ..., n-1$. In other words, each successive point in the refinement is taken to be the midpoint of the line segment joining the two corresponding points in the previous control polygon.

Note here that two of the $\alpha$s are $\frac{1}{2}$ and the remainder are zero.

In this case, the refinement process stops after $n-1$ steps - as the control polygon for each step of the refinement has one fewer points than does the control polygon in the previous step - the final control polygon having one point.

To represent this refinement process via matrices, the refinement matrix $S_k$ is

$$S_k \: = \: \left[ \begin{array}{cccccc} \frac{1}{2} & \frac{1}{2... ...ots & \vdots \\ 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \end{array}\right]$$

where the matrix is $k \times (k+1)$.

If this refinement is taken to completion, we have just calculated a point on the $n$th degree Bézier curve defined by this control polygon.

Example - A Non-Stationary Uniform Subdivision Scheme

Suppose we are given the control polygon $\left\{ {\bf P} _0, {\bf P} _1, ..., {\bf P} _n \right\}$. Define a refinement scheme by the following

$${\bf P} _{2j}^k \: = \: \frac{3}{4} {\bf P} _{j}^k + \frac{1}{4} {\bf P} _{j+1}^k$$

and

$${\bf P} _{2j+1}^k \: = \: \frac{1}{4} {\bf P} _{j}^k + \frac{3}{4} {\bf P} _{j+1}^k$$

for $j = 0, 1, 2, 3, ...$.

Notice that this gives us a new control polygon

$${\bf P} _0^1 = \frac{3}{4} {\bf P} _0 + \frac{1}{4} {\bf P} _1$$

$${\bf P} _1^1 = \frac{1}{4} {\bf P} _0 + \frac{3}{4} {\bf P} _1$$

$${\bf P} _2^1 = \frac{3}{4} {\bf P} _1 + \frac{1}{4} {\bf P} _2$$

$${\bf P} _3^1 = \frac{1}{4} {\bf P} _1 + \frac{3}{4} {\bf P} _2$$

$${\bf P} _4^1 = \frac{3}{4} {\bf P} _2 + \frac{1}{4} {\bf P} _3$$

$${\bf P} _5^1 = \frac{1}{4} {\bf P} _2 + \frac{3}{4} {\bf P} _3$$

$$\vdots$$

Applying this refinement process to a control polygon of length $n+1$ gives a new control polygon of length $2n$.

This is just Chaikin's Algorithm for curve generation. As the algorithm proceeds the number of control points gets arbitrarily large, but converges to a unique curve.

Refinement Schemes for Meshes

Similar methods (with much more notationally complex mathematics) exist for control meshes that result in surface generation algorithms. In general, the idea is the same - the refinement operation generates new control points from the control points of the previous mesh.

Summary

Refinement schemes generate an important class of curve and surface drawing algorithms that are useful in geometric modeling. The schemes generate a sequence of control polygons in the two-dimensional case, or control meshes in the three dimensional case that can be used for curve generation. The methods are useful in the case of Bézier curves and Bézier patches as well as in the generation of subdivision curves and surfaces.

Bibliography

1

DYN, N., GREGORY, J., AND LEVIN, D.
Analysis of uniform binary subdivision schemes for curve design.
Constructive Approximation 7, 2 (1991), 127-148.

2

DYN, N., AND LEVIN, D.
The subdivision experience.
In Curves and Surfaces II (1991), A. L. H. P.J. Laurent and L. Schumaker, Eds., pp. 1-17.

3

MICCHELLI, C. A., AND PRAUTZSCH, H.
Uniform refinement of curves.
Linear Algebra and Its Applications 114/115 (1989), 841-870.