CAGD-banner.gif
On-Line Geometric Modeling Notes
A MATRIX FORMULATION OF THE CUBIC BÉZIER CURVE


Overview

A cubic Bézier curve has a useful representation in a matrix form. This is a non-standard representation but extremely valuable if we can multiply matrices quickly. The matrix which we develop, when examined closely, is uniquely defined by the cubic Bernstein polynomials. We can use this form to develop ``subdivision matrices'' that allow us to use matrix multiplication to generate different Bézier control polygons for the cubic curve.

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


Developing the Matrix Equation

A cubic Bézier Curve can be written in a matrix form by expanding the analytic definition of the curve into its Bernstein polynomial coefficients, and then writing these coefficients in a matrix form using the polynomial power basis. That is,

\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}

and so a cubic Bézier curve is can be written in a matrix form of

$\displaystyle \left[ \begin{array}{cccc}
1 & t & t^2 & t^3
\end{array} \right]
...
...c}
{\bf P} _0 \\  {\bf P} _1 \\  {\bf P} _2 \\  {\bf P} _3
\end{array} \right]
$

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)$.

Utilizing equipment that is designed for fast $ 4 \times 4$ matrix calculations, this formulation can be used to quickly calculate points on the curve.


Subdivision Using the Matrix Form

Suppose we wish to generate the control polygon for the portion of the curve $ {\bf P} (t)$ where $ t$ ranges between 0 and $ \frac{1}{2}$ - subdivide the curve at the point $ t=\frac{1}{2}$. This can be done by defining a new curve $ {\bf Q} (t)$ which is equal to $ {\bf P} (\frac{t}{2})$. Clearly this new curve is a cubic polynomial, and traces out the desired portion of $ {\bf P} $ as $ t$ ranges between 0 and $ 1$. We can calculate the Bézier control polygon for $ {\bf Q} $ by using the matrix form of the curve $ {\bf P} $.

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

where the matrix $ S_{\left[ 0,\frac{1}{2}\right]}$ is defined as

\begin{displaymath}\begin{aligned}S_{\left[ 0,\frac{1}{2}\right]} & = M ^{-1} \l...
...} & \frac{3}{8} & \frac{1}{8} \end{array} \right] \end{aligned}\end{displaymath}

So $ {\bf Q} (t)$ is a Bézier curve, with a control polygon given by

$\displaystyle \left[ \begin{array}{cccc}
1 & 0 & 0 & 0 \\
\frac{1}{2} & \frac...
...bf P} _2 + \frac{3}{8} {\bf P} _1 + \frac{1}{8}
{\bf P} _0
\end{array} \right]
$

In the same way, we can obtain the Bézier control polygon for the second half of the curve - the portion where $ t$ ranges between $ \frac{1}{2} $ and $ 1$. If we call this new curve $ {\bf Q} (t)$, then

\begin{displaymath}\begin{aligned}{\bf Q} (t) & = {\bf P} (\frac{1}{2} + \frac{t...
...\\  {\bf P} _2 \\  {\bf P} _3 \end{array} \right] \end{aligned}\end{displaymath}

where

$\displaystyle S_{\left[ \frac{1}{2},1 \right]} \: = \:
\left[ \begin{array}{ccc...
... \\
0 & 0 & \frac{1}{2} & \frac{1}{2} \\
0 & 0 & 0 & 1
\end{array} \right]
$

obtaining a matrix that can be applied to the original Bézier control points to produce Bézier control points for the second half of the curve.


Generating a Sequence of Bézier Control Polygons.

Using matrix calculations similar to those above, we can generate an iterative scheme to generate a sequence of points on the curve. To do this, we need one additional $ S$ matrix. If we consider the portion of the cubic curve $ {\bf P} (t)$ where $ t$ ranges between $ 1$ and $ 2$, We generate the Bézier control points of $ {\bf Q} (t)$ by reparameterization of the original curve - namely by replacing $ t$ by $ t+1$ - to obtain

\begin{displaymath}\begin{aligned}{\bf Q} (t) & = {\bf P} (t+1) \\  & = \left[ \...
...\\  {\bf P} _2 \\  {\bf P} _3 \end{array} \right] \end{aligned}\end{displaymath}

where, after some calculation, $ S_{[1,2]}$ is given by

$\displaystyle S_{[1,2]} \: = \:
\left[ \begin{array}{cccc}
0 & 0 & 0 & 1 \\
0 & 0 & -1 & 2 \\
0 & 1 & -4 & 4 \\
-1 & 6 & -12 & 8
\end{array} \right]
$

Now, using a combination of $ S_{\left[ 0, \frac{1}{2} \right]}$, $ S_{\left[
\frac{1}{2} , 1 \right]}$ and $ S_{\left[ 1, 2 \right]}$, we can produce Bézier control polygons along the curve similar to methods developed with divided differences. To see what I mean here, first notice that

$\displaystyle S_{\left[ 1, 2 \right]} S_{\left[ 0, \frac{1}{2} \right]}
= S_{\left[ \frac{1}{2} , 1 \right]}
$

This states that by applying $ S_{\left[ 0, \frac{1}{2} \right]}$ to obtain a Bézier control polygon for the first half of the curve, we can then apply $ S_{\left[ 1, 2 \right]}$ to this control polygon to obtain the Bézier control polygon for the second half of the curve.

Extending this, if we apply

$\displaystyle S_{\left[ 1, 2 \right]}^i S_{\left[ 0, \frac{1}{2} \right]}^k
$

(that is, apply $ S_{\left[ 0, \frac{1}{2} \right]}$ $ k$ times and then $ S_{\left[ 1, 2 \right]}$ $ i$ times), we obtain the Bézier control polygon for the portion of the curve where $ t$ ranges between $ \frac{i}{2^k}$ and $ \frac{i+1}{2^k}$. By repeatedly applying $ S_{\left[ 1, 2 \right]}$, we move our control polygons along the curve.


Summary

We have developed a matrix form for the cubic Bézier curve. Using reparameterization, we then developed matrices which enabled us to produce Bézier control polygons for sections of the curve, and to move from one Bézier control polygon to an adjacent for on the curve. These operations are extremely useful when utilizing hardware with geometry engines that multiply $ 4 \times 4$ matrices rapidly.


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


Ken Joy
2000-11-28