On-Line Geometric Modeling Notes
QUADRATIC UNIFORM B-SPLINE CURVE REFINEMENT

Overview

Subdivision methods for curve generation are based upon a procedure which successively refines a control polygon into into a sequence of control polygons that, in the limit, converges to a curve. The curves are commonly called subdivision curves as the refinement methods are based upon the binary subdivision of uniform B-spline curves.

The uniform B-spline curves, surfaces and solids have been extensively studied in the literature and subdivision methods for these objects are well known. We develop here the refinement method for a quadratic uniform B-spline curve and show that the refinement is exactly that specified by Chaikin's Algorithm [1].

For a pdf version of these notes look here.

The Matrix Equation for the Quadratic Uniform B-Spline Curve

Given a set of control points ${\bf P} _0, {\bf P} _1 ..., {\bf P} _n$ the quadratic uniform B-spline curve ${\bf P} (t)$ defined by these control points can be defined in segments by the $n-1$ equations

$${\bf P} (t) \: = \: \left[ \begin{array}{ccc} 1 & t & t^2 \end{ar... ...{array}{c} {\bf P} _k \\ {\bf P} _{k+1} \\ {\bf P} _{k+2} \end{array}\right]$$

for $k = 0, 1, ..., n-2$, and $0 \leq t \leq 1$, and where

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

The matrix $M$, when multiplied by $\left[ \begin{array}{ccc} 1 & t & t^2 \end{array} \right]$ defines the quadratic uniform B-spline blending functions.

Splitting and Refinement

We will begin by studying the binary subdivision of a quadratic uniform B-spline curve ${\bf P} (t)$ defined by the control polygon $\left\{ {\bf P} _0, {\bf P} _1, {\bf P} _2 \right\}$, containing only three points, and then extend this to control polygons containing larger numbers of points.

We can perform a binary subdivision of the curve, by applying one of two splitting matrices

$$S^L = \frac{1}{4} \left[ \begin{array}{rrr} 3 & 1 & 0 \\ 1 & 3 & 0 \\ 0 & 3 & 1 \end{array}\right]$$

$$S^R = \frac{1}{4} \left[ \begin{array}{rrr} 1 & 3 & 0 \\ 0 & 3 & 1 \\ 0 & 1 & 3 \end{array}\right]$$

to the control polygon. (When applied to the control polygon $S^L$ gives the first half of the curve, and $S^R$ gives the second half.)

As it turns out, several of the control points for the two subdivided components are the same. Thus, we can combine these matrices, creating a $4 \times 3$ matrix

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

and apply it to a control polygon as follows:

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

and so the refined curve has control points that are positioned as in the following illustration:

i.e. at $\frac{1}{4}$ and $\frac{3}{4}$ along each of the lines of the control polygon. These are the same points as are developed in Chaikin's method

The General Refinement Procedure

The general procedure is - given a control polygon, we can generate a refinement of this set of points by constructing new points along each edge of the original polygon at a distance of $\frac{1}{4}$ and $\frac{3}{4}$ between the endpoints of the edge. The general idea behind subdivision curves is to assemble these points into a new control polygon which can then be used as input to another refinement operation, generating a new set of points and another control polygon - and then continue this process until a refinement is reached that accurately represents the curve to a desired resolution. The following illustration shown the second refinement in the case above.

Since this general refinement procedure is developed from the binary subdivision of a uniform B-spline curve, and the control points of the refined polygon are unions of those of the subdivided curves, we then have that the control points of the refined polygons must converge to the curve. That is, in the limit, the sequence of control polygons generated by the refinement procedure converges to a quadratic uniform B-spline curve. This shows that Chaikin's curve is really a quadratic uniform B-spline curve.

Summary

Given a control polygon we can specify a simple process that can be used to generate successive refinements of the control polygon and, in the limit, converges to the uniform B-spline curve defined by the original control polygon. This scheme is the basis for the development of the Doo-Sabin subdivision scheme which generalizes Chaikin's algorithm to surfaces.

Bibliography

1

CHAIKIN, G.
An algorithm for high speed curve generation.
Computer Graphics and Image Processing 3 (1974), 346-349.

2

RIESENFELD, R.
On Chaikin's algorithm.
IEEE Computer Graphics and Applications 4, 3 (1975), 304-310.