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

Overview

The binary subdivision of the uniform B-spline curves and surfaces motivate much of the work on subdivision curves and surfaces - where the word ``subdivision'' here is taken from the process that is used to subdivide a curve or surface into multiple components. In the uniform B-spline case a subdivided component shares many of its individual control points with other components, allowing us to define the totality of control points generated through subdivision as a refinement of the original control polygon. These new control points can be assembled into a new control polygon and refined again by the same methods. Successive refinements produce a sequence of control polygons that in the limit converge to a curve.

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 cubic uniform B-spline curve. The analysis is similar to that presented in the quadratic case however, the refinement algorithm can be specified in a different manner which eventually allows us to use eigenanalysis and directly calculate points on the curve.

For a pdf version of these notes look here.

The Matrix Equation for the Cubic Uniform B-Spline Curve

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

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

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

$$M \: = \: \frac{1}{6}\left[ \begin{array}{rrrr} 1 & 4 & 1 & 0 \\ -3 & 0 & 3 & 0 \\ 3 & -6 & 3 & 0 \\ -1 & 3 & -3 & 1 \end{array}\right]$$

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

Splitting and Refinement

We will begin by studying the binary subdivision of a cubic uniform B-spline curve ${\bf P} (t)$ defined by the four control points ${\bf P} _0$, ${\bf P} _1$, ${\bf P} _2$ and ${\bf P} _3$. Such a curve is shown in the following illustration.

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

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

$$S^R = \frac{1}{8} \left[ \begin{array}{rrrr} 1 & 6 & 1 & 0 \\ 0 & 4 & 4 & 0 \\ 0 & 1 & 6 & 1 \\ 0 & 0 & 4 & 4 \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 $5 \times 4$ matrix

$$\frac{1}{8} \left[ \begin{array}{cccc} 4 & 4 & 0 & 0 \\ 1 & 6 &... ...0\\ 0 & 4 & 4 & 0 \\ 0 & 1 & 6 & 1 \\ 0 & 0 & 4 & 4 \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 ... ... {\bf P} _0 \\ {\bf P} _1 \\ {\bf P} _2 \\ {\bf P} _3 \end{array}\right]$$

generating a new control polygon which serves as the refinement of the original. The five control points of this new control polygon specify the two subdivided halves of the curve - and therefore specify the curve itself.

The General Refinement Procedure

In the case of the quadratic curve we were able to state exactly a single procedure for the points of the refinement. In this case, it is not so easy. However, if we examine the rows of $5 \times 4$ matrix used in the refinement, we see that they have two distinct forms. This motivates us to classify the points of the refinement as vertex and edge points, which is exhibited in another section. This classification makes the description of the refinement process quite straightforward.

Summary

In the case of a uniform cubic B-spline curve we can define process that takes the defining control polygon and creates a sequence of control polygons by refinement. This sequence converges to the curve defined by the original control polygon. The procedure is similar to that given in the quadratic case as it is generated through the matrices for binary subdivision of the curve.

Bibliography

1

CATMULL, E., AND CLARK, J.
Recursively generated B-spline surfaces on arbitrary topological meshes.
Computer-Aided Design 10 (Sept. 1978), 350-355.