On-Line Geometric Modeling Notes
SPLITTING THE CUBIC UNIFORM B-SPLINE CURVE

Overview

Splitting a uniform B-spline curve implies creating two new curves, one that represents the first half of the original curve, and one that represents the second half. These ``subdivision'' methods motivate much of the work on subdivision curves and provide methods that can be applied to recursive subdivision of B-spline surfaces. In the uniform B-spline case the subdivided components share many of their 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.

In these notes we develop the methods for splitting a uniform cubic B-spline curve and develop a refinement process based upon these splitting algorithms.

For a pdf version of these notes look here.

The Matrix Equation for the Cubic Uniform B-Spline Curve

Given a 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

$$\left[ \begin{array}{cccc} 1 & t & t^2 & t^3 \end{array} \right] ... ... {\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$, where

$$\left[ \begin{array}{cccc} 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.

The curve is made up from the union of the segments $P_0(t)$, $P_1(t)$, $...$, $P_{n-3}(t)$. In these notes we will assume that $n=3$, so that the curve is made up from only one segment.

Splitting - The First Half of the Curve

Suppose we are given a cubic uniform B-spline curve ${\bf P} (t)$ defined by the control polygon $\left\{ {\bf P} _0, {\bf P} _1, {\bf P} _2, {\bf P} _3 \right\}$.

To perform a binary subdivision of the curve, we will produce two curves ${\bf P} ^L(t)$ and ${\bf P} ^R(t)$ which, as $t$ ranges between 0 and $1$, sweep out the curve ${\bf P} (t)$ as $t$ ranges from 0 to $\frac{1}{2}$ and from $\frac{1}{2}$ to $1$ respectively. Concentrating first on ${\bf P} ^L$, we can write $P^L(t)$ as $P(\frac{t}{2})$ and so

$$\begin{aligned}{\bf P} ^L(t) & = {\bf P} ( \frac{t}{2} ) \\ ... ...{\bf P} _2^L \\ {\bf P} _3^L \end{array} \right] \end{aligned}$$

where

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

and

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

The matrix $S^L$ is commonly called a ``splitting matrix'' and is given by

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

Carrying out the algebra, we have that

$$\begin{aligned}\left[ \begin{array}{c} {\bf P} _0^L \\ {\bf ... ...+ 6 {\bf P} _{2} + {\bf P} _3 \end{array} \right] \end{aligned}$$

and so the subdivided curve ${\bf P} ^L(t)$ has a control polygon that is positioned as in the following illustration:

i.e. at the midpoints of the first two line segments, and near the second and third vertices ${\bf P} _1$ and ${\bf P} _2$.

We note that since the subdivided curve has been written as

$${\bf P} ^L(t) \: = \: \left[ \begin{array}{cccc} 1 & t & t^2 & t... ...0^L \\ {\bf P} _1^L \\ {\bf P} _2^L \\ {\bf P} _3^L \end{array} \right]$$

and so ${\bf P} ^L(t)$ is a uniform cubic B-spline curve as was required.

Splitting - The Second Half of the Curve

To subdivide ${\bf P} (t)$ and produce the second portion ${\bf P} ^R(t)$ of the curve - i.e. the portion that is swept out as $t$ ranges from $\frac{1}{2}$ to $1$, we write ${\bf P} ^R(t) = {\bf P} (\frac{1}{2} + \frac{t}{2})$ and calculate

$$\begin{aligned}{\bf P} ^R(t) & = {\bf P} ( \frac{1}{2} + \fra... ...{\bf P} _2^R \\ {\bf P} _3^R \end{array} \right] \end{aligned}$$

where

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

$S^R$ is commonly called a splitting matrix, and is given by

$$\begin{aligned}S^R & = M^{-1} \left[ \begin{array}{cccc} 1 & ... ...& 1 & 6 & 1 \\ 0 & 0 & 4 & 4 \end{array} \right] \end{aligned}$$

By carrying out the algebra, we have that

$$\begin{aligned}\left[ \begin{array}{c} {\bf P} _0^R \\ {\bf ... ...{\bf P} _{2} + 4 {\bf P} _{3} \end{array} \right] \end{aligned}$$

and so the subdivided curve ${\bf P} ^R(t)$ has a control polygon that is positioned as in the following illustration:

i.e. at the midpoints of the second and third line segments and near the second and third vertices.

We note that since the subdivided curve has been written as

$${\bf P} ^R(t) \: = \: \left[ \begin{array}{cccc} 1 & t & t^2 & t... ..._0^R \\ {\bf P} _1^R \\ {\bf P} _2^R \\ {\bf P} _3^R \end{array} \right]$$

and so ${\bf P} ^R(t)$ is again a uniform cubic B-spline curve as required.

Specifying the Refinement Procedure

We note that several of the control points for the two subdivided components are the same. In particular ${\bf P} _1^L = {\bf P} _0^R$, ${\bf P} _2^L = {\bf P} _1^R$ and ${\bf P} _3^L = {\bf P} _2^R$ - and so the five unique control points ${\bf P} _0^L$, ${\bf P} _1^L$, ${\bf P} _2^L$, ${\bf P} _2^R$ and ${\bf P} _3^R$ fully represent the two subdivided halves of the curve - and therefore represent the curve itself. The control polygon consisting of these five points is a refinement of the original control polygon $\left\{ {\bf P} _0, {\bf P} _1, {\bf P} _2, {\bf P} _3 \right\}$. The following figure illustrates both the original vertices and the points of the refinement.

Summary

In the case of a cubic uniform B-spline curve we can define a simple procedure based upon two splitting matrices that allows the binary subdivision of the curve. In this case, many of the control points of the subdivided control polygons are shared and we can define a refined control polygon that is the union of the control points of the respective control polygons of the subdivision.

Bibliography

1

YAMAGUCHI, F.
Curves and Surfaces in Computer Aided Geometric Design.
Springer, 1988.