\input Header.tex

\title{Parametric Curves}


These are manifold point sets, just like lines.

%<a href="smallprt.htm#nonmancrv"> SP </a> 

Indeed, they are just bent and stretched straight lines.  Other types
of curve exist, and need to be handled, but they seldom need to be
designed.  In practice we approximate them by parametric curves.

The bounded form is always assumed.  The curve is a map from the
interval [0..1] to a point set.

\section{Representations}

Whichever basis we use, the form of the equation is the same:
$$P(t) := \sum A_i f_i(t)$$
where the $A_i$ are the {\bf coefficients} used to
represent the curve segment and the $f_i(t)$ are the
{\bf basis functions} which decide what the map is between the
coefficients and the curve itself.

In all useful cases the coefficients are a collection of points and
displacements.  Some of the forms have just a sequence of points as
their representation. 

\filbreak
The basis functions are Real to Real functions, and for an equation of
the above form to fit the rules for computing points, we have to have
some restriction on the basis set.  This is:- 

{\narrower{

There must be a subset of the $i$ for which the sum of the
corresponding basis functions is identically equal to 1.  The
coefficients of these are points.

The coefficients of any other basis functions are displacements.

}
}

There are many possible sets of basis functions fulfilling these conditions. 

\filbreak
\theorem: Coordinate System Invariance

If a curve is defined by the above equation, it has coordinate system
invariance.

 \given a curve of the form 
$P(t) = \sum A_i f_i(t) + \sum B_j g_j(t)$, 
where $\sum f_i(t) =1$ and so all the $A_i$ are points and the
 $B_j$ are displacements.

 \toprove that transformation of the coefficients $A_i$ and $B_j$
 leads to transformation of every point $P(t)$ by the same
 transformation.

 \construction Each point is transformed by $A'_i = O + R.A_i$ and every displacement is transformed by  $B'_j = R.B_j$.

\proof

The result of transforming all the coefficients is

$$\eqalign{
P'(t) &= \sum A'_i f_i(t) + sum B'_j g_j(t)\cr
&= \sum [O + R.A_i] f_i(t) + \sum R.B_j g_j(t)\cr
&= O \sum f_i(t) + \sum R.A_i f_i(t) 
+ \sum R.B_j g_j(t)\cr
&= O  + R.[\sum A_i f_i(t) 
+ \sum B_j g_j(t)]\cr
&= O  + R.P (t)}$$

\endtheorem

Thus any curve with this kind of equation has the desirable property
of coordinate system invariance under linear transformations.  Note
that this includes affine transformations as well as solid body ones.



\filbreak
For reasons of economy and efficiency we are interested in primarily
two families of sets of basis functions:-

\+\cr
\+Those which span the space of {\bf polynomials}\cr
\+Those which span the space of {\bf piecewise polynomials}\cr
\+\cr


\section{Polynomial Curves}

Polynomials can be of different {\bf degree}s, and for any given
degree there are alternative bases all of which span the polynomials
of that degree.

\subsection{Monomials}

$$P(t) = Q + tT + t^2U + t^3V + \ldots$$

The coefficients are all displacements except $Q$.  They are related
to the derivatives of the curve at the start point.

This can be thought of as a kind of Taylor series.  The higher degree
coefficients are not particularly easy to choose when designing a
curve.

\subsection{Hermite}

This is a definition in terms of both end points and the derivatives
there\footnote{$^1$}{}.  It is most natural for
even degrees. A good example is the cubic
$$P(t) = P(0)f_0(t) + P(1)f_1(t) + P'(0)g_0(t) + P'(1)g_1(t)$$
where
$$\eqalign{
f_0(t) &= 1 -3 t^2 + 2t^3\cr
f_1(t) &= 1 - f_0(t) = 3t^2 - 2 t^3\cr
g_0(t) &= t( t - 1)^2\cr
g_1(t) &= t^2( t - 1 )}$$

The major problem when using this form for cubics is that the
derivative controls are displacements, whereas the end directions,
which they control, are merely directions.  It is not obvious what
lengths these displacements should have, although rules of thumb (make
them as long as the chord between the endpoints) work well, and
practitioners soon found tricks that they could play to get specific
effects.



\subsection{Lagrange}

These give polynomials interpolating equally spaced\footnote{$^2$}{}
 data values.

$$f_i(t) = {{\Pi_{j\ne i}(t-t_j)}\over{\Pi_{j\ne i}(t_i-t_j)}}$$

\subsection{Chebyshev}

These are not seriously used in CAGD.

\subsection{Bernstein}

Curves defined using these functions are usually referred to in CAGD
as {\bf \Bezier} curves, after Pierre \Bezier who popularised them.
Before that we used Hermite cubics under the name of {\bf Ferguson}
curves.

\filbreak
The Bernstein polynomials of degree $n$ are usually expressed in terms
of $t$ and $s = 1-t$ and are given by the terms in the binomial
expansion of
$$ (s+t)^n$$

\filbreak
Because $(s+t) = 1$, the whole set of basis functions sums to one, and
so all the coefficients are points.  There is a natural sequence of
basis functions, because they have their maxima equally spaced along
the interval [0..1], and we usually join the control points in this
sequence into a polygon called the {\bf control polygon}.

Thus for cubics we have
$$\eqalign{
f_0(t) &= s^3\cr
f_1(t) &= 3s^2t\cr
f_2(t) &= 3st^2\cr
f_3(t) &= t^3}$$

The generic form of the $i^{th}$ coefficient is
$$f_i(t) = {{n !}\over{i ! (n-i) !}} s^{n-i}t^i$$

\filbreak
An important property, the {\bf hodograph} property, is that the first
derivative is given by another Bernstein polynomial whose coefficients
are just $n$ times the first differences of the original control
points.

\noindent{\bf Immediate Exercise} Confirm this derivative property.

This property was theoretically extremely important, because it helped
Bernstein to prove the Weierstrass Approximation Theorem, that any
$C\infty$ function can be uniformly approximated over an interval
arbitrarily closely by a polynomial of high enough degree, together
with all its derivatives.

\filbreak
Bernstein used his polynomials, with coefficients taken from the curve
to be approximated, and showed that as the degree rose, the polynomial
so defined would get ever closer to the required curve.  The hodograph
property, coupled with the fact that $n$ times the first
differences gives a better and better approximation to the derivative,
shows the convergence of the derivatives as well.

\filbreak
The hodograph property also has the immediate corollary that the
$i^{th}$ derivative at an end is proportional to the $i^{th}$
difference of the control points at that end.  This is used to help
join adjacent Bezier segments together with continuity.  If we require
that two segments have $i$ derivatives continuous at their join, we
merely have to impose the conditions that the first $i$ differences of
their control polygons match across the junction.



\section{Piecewise polynomials.}

We are interested in the piecewise polynomials which have maximal
  continuity at the places where the polynomial pieces meet.  These
  are called {\bf Splines}, and there are again two important
  variants tabulated below.  Because of the maximal continuity
  constraint the number of control points is essentially one per
  polynomial piece, plus a few extra at the ends depending on the
  degree.

\subsection{Interpolating Splines}

 These are the equivalent of Lagrange Polynomials, in that the
  coefficients are a set of points through which the curve passes.
  They are, however, much less sensitive than the Lagrange
  Polynomials.  This is related to the fact that for small
  perturbations the cubic spline is the curve of minimum bending
  energy which interpolates the data points.

\subsection{B-Splines}

 These are analogous to Bernstein Polynomials, but have two
  interesting properties 

 The basis functions have {\bf finite support}.  This means that each
  function is zero outside a relatively narrow interval.

  Apart from at the ends of the curve, the basis functions are all the
  same shape. They are all translates (shifts in abscissa) of the same
  function, which is called {\bf the equal interval B-spline}\footnote{$^3$}{}
 of the given degree.

  They also have the property that the derivative is another spline
  over the B-spline basis one degree lower, whose coefficients are
  just {\sl degree} times the first differences of the original
  control points.

\filbreak
The basis functions for the low degree B-splines can be determined by
applying the conditions for continuity of Bezier segments.  For
example, the sequence of Bezier coefficients for the cubic B-spline
are

\centerline{|0 0 0 1 | 1 2 4 4 | 4 4 2 1 | 1 0 0 0 |}

\noindent all divided by 6.

For low degree interpolating splines, we can determine the basis
functions by solving the collocation equations to fit B-splines to
cardinal data with a unit value at one point and zero at all the
others.  The B-splines can then be summed to give the required basis
function.


\section{Comparison of polynomial and piecewise curves}

We essentially compare Lagrange polynomials with Interpolating
splines, and Bernstein polynomials with B-splines.


\subsection{Design convenience}

For small numbers of control points there is very little difference.
For large numbers, the Lagrange polynomial becomes far too sensitive
to small movements of the middle control points, while the Bernstein
polynomial becomes too insensitive.

For long curves, the ability to make a change to a limited region of
the curve, leaving the rest invariant, is a strong argument for the
B-splines.

\subsection{Efficiency of interrogation}

Again, for small numbers of control points there is little difference.
For large numbers, however, the B-spline shows a clear advantage in
that to evaluate the curve at a particular value of $t$ requires
only a relatively small number of control points to be accessed.

Although it is possible for a B-spline to be evaluated by determining
the polynomial piece that the query point lies at, it is far better,
for relatively low degrees, to use a procedure called the
{\bf Cox-deBoor} recurrence.


\section{Properties of Basis functions in general}

A property important for editing a curve is that each basis function
is essentially the derivative of the curve with respect to its
coefficient.  This is a trivial result of the linear definition.  What
is means is that basis functions which have clear maxima give good
local editing properties.  The part of the curve parametrically near
that maximum will lie close to the corresponding control point, and
they will then be influenced most strongly when the point is
moved.

The overall sensitivity of a curve to noisy control points can be
assessed by the norms

$\sqrt {\sum_i f_i^2(t)}$ is a function which shows the sensitivity of
the curve to uncorrelated noise on the coefficients.

$\sum_i |f_i(t)|$ is a function which shows the worst case effect on
the curve at each point by control point perturbations malevolently
chosen to give most effect at that point.

The bad sensitivity of the Lagrange interpolant is displayed quite
clearly by these measures.

\end
