On-Line Geometric Modeling Notes
SPLITTING A QUADRATIC UNIFORM B-SPLINE CURVE

Overview

Splitting a uniform B-spline curve involves creating two new curves, one that represents the first half of the original curve, and one that represents the second half. These techniques motivate much of the work on subdivision curves and provide methods that can be applied to splitting B-spline surfaces. In the uniform B-spline case the subdivided components share many of their control points, allowing us to define a ``refinement'' of the curve by the union of all control points obtained through splitting the various segments of the curve.

In these notes we develop the methods for splitting a quadratic uniform B-spline curve and show how these splitting methods can be used to define a refinement procedure on the control polygons that converges to the original curve.

For a pdf version of these notes look here.

The Matrix Equation for the Quadratic Uniform B-Spline Curve

Given a control polygon $\left\{ {\bf P} _0, {\bf P} _1 ..., {\bf P} _n \right\}$, 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} _k(t) \: = \: \left[ \begin{array}{ccc} 1 & t & t^2 \end... ...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}{ccc} 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.

The curve is defined by the union of the segments ${\bf P} _0(t)$ ${\bf P} _1(t)$ $...$, ${\bf P} _{n-2}(t)$. In our case, we will assume that $n=2$ which will imply that the curve is defined by only one segment. The methods presented for one segment can be easily expanded to a general curve.

Splitting - The First Half of the Curve

Suppose we are given 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\}$.

To perform a binary subdivision of the curve, we will produce two curves ${\bf P}_{[0,\frac{1}{2}]} (t)$ and ${\bf P}_{[\frac{1}{2},1]} (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}_{[0,\frac{1}{2}]}$: By parameterization, we can write ${\bf P}_{[0,\frac{1}{2}]} (t)$ as ${\bf P} (\frac{t}{2})$ and so

$$\begin{aligned}{\bf P}_{[0,\frac{1}{2}]} (t) & = {\bf P} ( \f... ...\\ {\bf Q} _1 \\ {\bf Q} _2 \end{array} \right] \end{aligned}$$

where

$$\left[ \begin{array}{c} {\bf Q} _0 \\ {\bf Q} _1 \\ {\bf Q} _... ...begin{array}{c} {\bf P} _0 \\ {\bf P} _1 \\ {\bf P} _2 \end{array} \right]$$

and

$$S_{[0,\frac{1}{2}]} \: = \: M^{-1} \left[ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & \frac{1}{2} & 0 \\ 0 & 0 & \frac{1}{4} \end{array} \right] M$$

The matrix $S_{[0,\frac{1}{2}]}$ is commonly called a ``splitting matrix'' and is given by

$$\begin{aligned}S_{[0,\frac{1}{2}]} & = \frac{1}{2} \left[ \be... ...0 \\ 1 & 3 & 0 \\ 0 & 3 & 1 \end{array} \right] \end{aligned}$$

Carrying out the algebra, we have that

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

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

i.e. at one-quarter and three-quarters of the distance along the first line segment, and one-quarter of the distance along the second.

We note that since the curve has been written as

$${\bf P}_{[0,\frac{1}{2}]} (t) \: = \: \left[ \begin{array}{ccc} ... ...begin{array}{c} {\bf Q} _0 \\ {\bf Q} _1 \\ {\bf Q} _2 \end{array} \right]$$

and so ${\bf P}_{[0,\frac{1}{2}]} (t)$ is a uniform quadratic B-spline curve as was required.

Splitting - The Second Half of the Curve

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

$$\begin{aligned}{\bf P}_{[\frac{1}{2},1]} (t) & = {\bf P} ( \f... ...\\ {\bf R} _1 \\ {\bf R} _2 \end{array} \right] \end{aligned}$$

where

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

and $S_{[\frac{1}{2},1]}$ is given by

$$\begin{aligned}S_{[\frac{1}{2},1]} & = \frac{1}{2} \left[ \be... ...0 \\ 0 & 3 & 1 \\ 0 & 1 & 3 \end{array} \right] \end{aligned}$$

By carrying out the algebra, we have that

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

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

i.e. at three-quarters of the distance along the first line segment, and one-quarter and three-quarters along the second.

We note that since the curve has been written as

$${\bf P}_{[\frac{1}{2},1]} (t) \: = \: \left[ \begin{array}{ccc} ... ...begin{array}{c} {\bf R} _0 \\ {\bf R} _1 \\ {\bf R} _2 \end{array} \right]$$

and so ${\bf P}_{[\frac{1}{2},1]} (t)$ is again a uniform quadratic B-spline curve as required.

A Refinement Procedure

In the above calculation, we have split the original curve into two portions, each of which is specified by a set of three control points. Four of the six control points are unique (two are duplicates) - ${\bf Q} _1 = {\bf R} _0$ and ${\bf Q} _2 = {\bf R} _1$ - and so the four unique control points ${\bf Q} _0$, ${\bf Q} _1$, ${\bf R} _1$ and ${\bf R} _2$ fully represent the two subdivided halves of the curve - and therefore represent the curve itself. The control polygon consisting of these four points is called a refinement of the original control polygon. Using the following figure, which lists the original vertices and the points of the refinement, it can be seen that this method develops exactly the same points as Chaikin's method

The general refinement procedure can be then described as follows: 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. These constructed points can be assembled into a new control polygon which can then be used as input, for example, to another refinement operation. The following illustration shown the second refinement from the case above.

Summary

Given a control polygon specifying a quadratic uniform B-spline curve, we can specify a simple process based on the application of one of two splitting matrices that can be used to divide the curve into two components. In the uniform B-spline case, the control polygons representing the two halves of the curve share many control points. The union of these points can be used to construct a new control polygon which serves as a refinement of the original.

Bibliography

1

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