CAGD-banner.gif
On-Line Geometric Modeling Notes
CONTROL POLYGONS FOR CUBIC CURVES


Overview

B-Spline curves are piecewise Bézier curves. To develop B-splines, and to do so in a continuous smooth way, we must discover the conditions on which two Bézier curves can be pieced together. To examine this process, we will first consider a single cubic curve and show how to construct the many Bézier control polygons that represent the curve. These control polygons, and their geometric constraints, are paramount in the definition of the B-spline curve.

pdficonsmall.gif To get a pdf version of these notes look here.


A Matrix Equation for a Cubic Curve

A cubic polynomial curve $ {\bf P} (t)$ can be written as a Bézier curve. If we let $ {\bf P} _0, {\bf P} _1, {\bf P} _2, {\bf P} _3$ be the control points of the curve, then it can be written as

$\displaystyle {\bf P} (t) = \sum_{i=0}^3 {\bf P} _i B_{i,3}(t)
$

where the $ B_{i,3}(t)$ are the cubic Bernstein polynomials. In this representation, $ {\bf P} _0 = {\bf P} (0)$ and $ {\bf P} _3 = {\bf P} (1)$.

\includegraphics {figures/piecing-1}

The representation of the curve can be written in a matrix form by

\begin{displaymath}\begin{aligned}{\bf P} (t) & = \sum_{i=0}^{3} {\bf P} _i B_i ...
...\\  {\bf P} _2 \\  {\bf P} _3 \end{array} \right] \end{aligned}\end{displaymath}

where

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

The matrix $ M$ defines the blending functions for the curve $ {\bf P} (t)$ - i.e. the cubic Bernstein polynomials. (In reality there are three equations here, one for each of the $ x$, $ y$ and $ z$ components of $ {\bf P} (t)$.)


Reparameterization using the Matrix Form

The control polygon $ \left\{ {\bf P} _0, {\bf P} _1, {\bf P} _2, {\bf P} _3 \right\}$ defines the unique cubic curve $ {\bf P} (t)$, and is most frequently used to represent the curve between $ t=0$ and $ t=1$, where $ {\bf P} _0 = {\bf P} (0)$ and $ {\bf P} _3 = {\bf P} (1)$. However, given an interval $ [a,b]$, there exists a unique control polygon $ \left\{ {\bf Q} _0, {\bf Q} _1,
{\bf Q} _2, {\bf Q} _3 \right\}$ defining a Bézier curve $ {\bf Q} (t)$, such that $ {\bf Q} (0) = {\bf Q} _0 = {\bf P} (a)$ and $ {\bf Q} (1) = {\bf Q} _3 = {\bf P} (b)$. These control polygons, called Bézier polygons can be generated by reparameterization and by manipulating the matrix representation above.

Suppose that we wish to find the Bézier polygon for the portion of the curve $ {\bf P} (t)$ where $ t \in \left[ a, b \right]$. If we define this new curve as $ {\bf Q} (t)$, then we can define $ {\bf Q} (t) = {\bf P} ((b-a)t + a)$. It is straightforward to check that both $ {\bf Q} (t)$ and $ {\bf P} (t)$ are cubic curves, and represent the same curve. We can calculate the control points for $ {\bf Q} (t)$ by using our matrix form, that is

\begin{displaymath}\begin{aligned}{\bf Q} (t) & = {\bf P} ((b-a)t + a) \\  & = \...
...\\  {\bf P} _2 \\  {\bf P} _3 \end{array} \right] \end{aligned}\end{displaymath}

where the matrix $ \left[ C \right]$ has columns whose entries are the coefficients of $ 1$, $ t$, $ t^2$ and $ t^3$ respectively in the polynomials $ 1$, $ (b-a)t+a$, $ ((b-a)t+a)^2$, and $ ((b-a)t+a)^3$, respectively. This can be rewritten as

\begin{displaymath}\begin{aligned}{\bf Q} (t) & = \left[ \begin{array}{cccc} 1 &...
...] M \left( S_{\left[ a,b \right]} {\bf P} \right) \end{aligned}\end{displaymath}

where $ S_{\left[ a,b \right]}$ is equal to

$\displaystyle S_{\left[ a,b \right]} = M ^ {-1} C M
$

The new control points for the portion of the curve where $ t$ ranges from $ a$ to $ b$ can now be written as $ \left( S_{\left[ a,b \right]} {\bf P} \right)$.


A Specific Example

An example of this which will be useful to us in learning how to piece together two Bézier curves is to find the control polygon for the curve $ {\bf P} (t)$ when its parameter ranges from $ 1$ to $ 2$. In this case, we have

\begin{displaymath}\begin{aligned}{\bf Q} (t) & = {\bf P} (t+1) \\  & = \left[ \...
...] M \left( S_{\left[ 1,2 \right]} {\bf P} \right) \end{aligned}\end{displaymath}

where

\begin{displaymath}\begin{aligned}S_{\left[ 1,2 \right]} & = {\left[ \begin{arra...
...& -4 & 4 \\  -1 & 6 & -12 & 8 \end{array} \right] \end{aligned}\end{displaymath}

So the control polygon for that portion of $ {\bf P} (t)$ curve where $ t$ ranges from $ 1$ to $ 2$ is given by

$\displaystyle \left[ \begin{array}{cccc} {\bf Q} _0 \\ {\bf Q} _1 \\ {\bf Q} _2 \\ {\bf Q} _3 \end{array} \right]$ $\displaystyle = \left[ \begin{array}{cccc} 0 & 0 & 0 & 1 \\ 0 & 0 & -1 & 2 \\ 0...
...{cccc} {\bf P} _0 \\ {\bf P} _1 \\ {\bf P} _2 \\ {\bf P} _3 \end{array} \right]$    
  $\displaystyle = \left[ \begin{array}{cccc} {\bf P} _3 \\ - {\bf P} _2 + 2 {\bf ...
...\\ - {\bf P} _0 + 6 {\bf P} _1 -12 {\bf P} _2 +8 {\bf P} _3 \end{array} \right]$ (1)

Working with some algebra, and defining new temporary points $ {\bf R} _1,
{\bf R} _2$    and $ {\bf R} _3$, we see that

$\displaystyle {\bf Q} _0$ $\displaystyle = {\bf P} _3$    
$\displaystyle {\bf Q} _1$ $\displaystyle = {\bf P} _3 + ( {\bf P} _3 - {\bf P} _2 )$ (2)
$\displaystyle {\bf R} _1$ $\displaystyle = {\bf P} _1 + ( {\bf P} _1 - {\bf P} _0 )$ (3)
$\displaystyle {\bf R} _2$ $\displaystyle = {\bf P} _2 + ( {\bf P} _2 - {\bf P} _1 )$ (4)
$\displaystyle {\bf R} _3$ $\displaystyle = {\bf R} _2 + ( {\bf R} _2 - {\bf R} _1 )$    
  $\displaystyle = {\bf P} _2 + ( {\bf P} _2 - {\bf P} _1 ) + ( {\bf P} _2 + ( {\bf P} _2 - {\bf P} _1 ) - {\bf P} _1 + ( {\bf P} _1 - {\bf P} _0 ) )$    
  $\displaystyle = {\bf P} _0 -4 {\bf P} _1 + 4 {\bf P} _2$ (5)
$\displaystyle {\bf Q} _2$ $\displaystyle = {\bf Q} _1 + ( {\bf Q} _1 - {\bf R} _2 )$    
  $\displaystyle = {\bf P} _3 + ( {\bf P} _3 - {\bf P} _2 ) + ( {\bf P} _3 + ( {\bf P} _3 - {\bf P} _2 ) - {\bf P} _2 + ( {\bf P} _2 - {\bf P} _1 ) )$    
  $\displaystyle = {\bf P} _1 -4 {\bf P} _2 + 4 {\bf P} _3$ (6)
$\displaystyle {\bf Q} _3$ $\displaystyle = {\bf Q} _2 + ( {\bf Q} _2 - {\bf R} _3 )$    
  $\displaystyle = {\bf P} _1 -4 {\bf P} _2 + 4 {\bf P} _3 + ( {\bf P} _1 -4 {\bf P} _2 + 4 {\bf P} _3 - {\bf P} _0 -4 {\bf P} _1 + 4 {\bf P} _2 )$    
  $\displaystyle = {\bf P} _0 + 6 {\bf P} _1 -12 {\bf P} _2 +8 {\bf P} _3$ (7)

Using these equations, these new control points can be analyzed geometrically and as a result each can be calculated by a simple geometric process using only the initial control polygon $ \left\{ {\bf P} _0, {\bf P} _1, {\bf P} _2, {\bf P} _3 \right\}$. If we consider the following figure, where we have displayed the control point $ {\bf P} _0, {\bf P} _1, {\bf P} _2,$    and $ {\bf P} _3$, it is easy to locate the point $ {\bf Q} _0 = {\bf P} _3$.

\includegraphics {figures/piecing-1}

By equation (2), $ {\bf Q} _1$ lies on an extension of the line $ \overline{ {\bf P} _2 {\bf P} _3}$ where the distance between $ {\bf P} _2$ and $ {\bf P} _3$, and between $ {\bf Q} _0$ and $ {\bf Q} _1$ are equal.

\includegraphics {figures/piecing-2}

By equation (4), $ {\bf R} _2$ lies on an extension of the line $ \overline{ {\bf P} _1 {\bf P} _2}$, where the lengths defined by $ \overline{ {\bf P} _1 {\bf P} _2}$ and $ \overline{ {\bf P} _2 {\bf R} _2}$ are equal - and as a result of this fact and equation (6), $ {\bf Q} _2$ lies on an extension of the line $ \overline{ {\bf R} _2 {\bf Q} _1}$, where the lengths defined by $ \overline{ {\bf R} _2 {\bf Q} _1}$ and $ \overline{ {\bf Q} _1 {\bf Q} _2}$ are equal. This enables us to construct $ {\bf Q} _2$.

\includegraphics {figures/piecing-3}

Similarly, using equations (3), (4), (5), and (7), we can construct $ {\bf Q} _3$ as in the the following illustration

\includegraphics {figures/piecing-4}

The result of this exercise is that we can construct the control points of the curve $ {\bf Q} (t)$ directly from the original control points for $ {\bf P} (t)$. These two functions represent the same curve.

An interesting exercise for the reader is to calculate the portion of the curve $ {\bf P} (t)$ as $ t$ ranges from 0 to $ 2$. In this case, the new curve $ {\bf Q} (t)$ can be defined as $ {\bf Q} (t) = {\bf P} (2t)$, and by substituting this into the matrix form, the resulting Bézier polygon should be $ \left\{ {\bf P} _0, {\bf R} _1, {\bf R} _3, {\bf Q} _3 \right\}$. Try it out.


A Expanded Example

The example above illustrated the fact that there are many Bézier polygons that can represent a cubic curve. However the geometric construction process generated by this example did not quite illustrate the fine details of the algorithm. To see the necessary characteristics of the algorithm, we will use the following example: Find the control polygon for the portion of the curve $ {\bf P} (t)$ when $ t$ ranges between $ 1$ and $ b$, for an arbitrary value of $ b$. In this case, we define the curve $ {\bf Q} (t) = {\bf P} (a t + 1)$, where $ a=b-1$ and use our matrix representation to calculate

\begin{displaymath}\begin{aligned}{\bf Q} (t) & = {\bf P} (at+1) \\  & = \left[ ...
...] M \left( S_{\left[ 1,b \right]} {\bf P} \right) \end{aligned}\end{displaymath}

where

\begin{displaymath}\begin{aligned}S_{\left[ 1,b \right]} & = {\left[ \begin{arra...
...2(a+1) & -3a(a+1)^2 & (a+1)^3 \end{array} \right] \end{aligned}\end{displaymath}

So the control polygon for that portion of $ {\bf P} (t)$ curve where $ t$ ranges from $ 1$ to $ b$ is given by

\begin{displaymath}\begin{aligned}\left[ \begin{array}{cccc} {\bf Q} _0 \\  {\bf...
...{\bf P} _2 +(a+1)^3 {\bf P} _3 \end{array} \right]\end{aligned}\end{displaymath}

These new control points can again be analyzed geometrically and as a result each can be calculated by a simple geometric process using only the initial control polygon $ \left\{ {\bf P} _0, {\bf P} _1, {\bf P} _2, {\bf P} _3 \right\}$. To accomplish this, we first write

\begin{displaymath}\begin{aligned}{\bf Q} _0 & = {\bf P} _3 \\  [.5em] {\bf Q} _...
...f P} _1 -3a(a+1)^2 {\bf P} _2 +(a+1)^3 {\bf P} _3 \end{aligned}\end{displaymath}

where the last calculation can be done with some algebra.

The important factor here is the $ a$ term. Each of these points is on an extension of a line of the original control polygon, or the extension of a constructed line. The factor $ a$ determines how much to extend. The following illustration shows the construction for our previous Bézier curve with $ a=\frac{3}{4}$, giving the portion of the $ {\bf P} (t)$ where $ t$ ranges from $ 1$ to $ \frac{7}{4}$.

\includegraphics {figures/piecing-5}


Summary

We have shown here that for a cubic curve, there are many control polygons that can define the curve. Using our matrix representation, we have shown how to determine the control polygon that covers an arbitary interval $ [c,d]$ of the original curve. Our examples will be very useful when we discuss how to piece two or more Bézier curves together.


\begin{singlespace}
\noindent
\footnotesize\bfseries All contents copyright (c) ...
...ment, University of California, Davis \\
All rights reserved.
\end{singlespace}


Ken Joy
2000-11-28