\chapter{Four-parameter curves}
\label{chapter-fourparam}

For the basic problem of interpolating splines, two-parameter splines
are ideal. However, when greater than $G^2$-continuity is needed, or
for designing particular shapes with straight-to-curve transitions,
a four-parameter family of primitive curves is appropriate. Where a
curve from a two-parameter family is determined by its tangent angles
at the endpoints, a four-parameter curve is determined by both tangent
angles and curvatures.

Section \ref{sec-why-four} motivates the need for four parameters in
more detail. Section \ref{sec-mvc} discusses a well-known
four-parameter spline, the Minimum Variation Curve, and presents a
general equation for the shape of the MVC primitive curve. Section
\ref{sec-polynomial-spiral} presents an approximation to the MVC,
where curvature is defined as a cubic polynomial of arc length. This
spline has generally similar properties, but is computationally
much more tractable and easier to analyze. Finally, Section
\ref{sec-constraints} presents a technique for applying labels to
control points representing different constraints, generalizing the
idea of blended corner curves with $G^2$-continuity to a richer set of
configurations.

\section{Why four parameters?}
\label{sec-why-four}

Chapter \ref{two-chapter} contained a strong argument in favor of
a two-parameter family of curves for interpolating splines. Why, then,
consider a four-parameter family? When are two parameters not
adequate?

First, while the human visual system appears to be sensitive only to
$G^2$-continuity, there are applications for which higher orders of
continuity are important. For example, ``reflection lines'' resulting
from the specular reflection of lines from a 3D surface show generally
exhibit only $C^{k-1}$ continuity when the underlying surface is $G^k$
(see \cite[p. 570]{Hoschek93} for a detailed discussion). Thus, to
guarantee smooth reflection lines, the surface must be designed with a
high order of continuity. Another application demanding higher order
continuity is the design of rail layouts for high-speed trains. At the
slower speeds characteristic of trains in the United States,
$G^2$-continuity is adequate, and clothoidal segments are the usual
design norm, but in the rest of the world there has been recent
attention on smoother curves \cite{Klauder01}.

\begin{figure*}
\label{g2-vs-g4}
\begin{center}
\includegraphics[scale=.5]{figs/ecc0}
\includegraphics[scale=.5]{figs/ecc3}
\begin{tabular}{ll}\\[-4.5in] $\kappa$ \\[2in] spline \end{tabular}
\caption{\label{ecc03}Eccentricity 0.56199 oval with $G^2$ and $G^4$ continuity.}
\end{center}
\end{figure*}

Figure \ref{g2-vs-g4} shows an example of a simple closed curve (an
ovoid shape with eccentricity 0.56199) drawn using both a
$G^2$-continuous spline and a $G^4$-continuous spline. It is clear
from the curvature plots that the curvature variation is smoother in
the $G^4$ curve, but the points of discontinuity of curvature variation
are not directly visible to the eye.

\begin{figure*}
\begin{center}
\includegraphics[scale=.6]{figs/suitcase}
\begin{tabular}{ll}\\[-2in] spline \\[1.5in] $\kappa$ \end{tabular}
\caption{\label{fig-suitcase}The suitcase corners problem.}
\end{center}
\end{figure*}

Second, many shapes are not best represented as a simple interpolating
spline. The outline of a letterform is not, in general, a smooth
undulating curve (although such examples do exist, such as the
lowercase `c' in Figure \ref{euler-c-example}). In addition to
sections of smooth curve, a letter form may also have sharp corners,
sections of straight line, and, most importantly for this discussion,
smooth transitions from straight lines to curved sections. A simple
example is shown in Figure \ref{fig-suitcase} (based on Fig. 4.10 in
Moreton's Ph.D. thesis \cite{Moreton92}), illustrating the
problem of blending smooth corners between sections of straight
line.

In font design, similar situations arise for bracketed serifs,
and for shapes such as the letter U, where straight sections blend
smoothly with curves. A typical example showing both situations is
shown in Figure \ref{fig-serifs}, a capital U from the author's font
Cecco. The entire curve (with the exception of the sharp corners) is
$G^2$ continuous, providing pleasing and smooth joins between the
straight and curved sections.

A four-parameter curve family provides enough flexibility to meet such
needs. It's clear that a single section of Euler spiral is not
adequate for one of the corners in Figure \ref{fig-suitcase}, as the
curvature must start out zero, increase to a value large enough for
the segment to turn by a right angle, then decrease again to zero.

\begin{figure*}
\begin{center}
\includegraphics[scale=.6]{figs/cap_u_Cecco}
\caption{\label{fig-serifs}Bracketed serifs and straight-to-curve joins.}
\end{center}
\end{figure*}

Third, by annotating curves with additional constraints, it's possible
to improve locality. In particular, constraints that propagate
curvature derivatives in one direction, but leave the parameters
unconstrained on one side (which we call ``one-way constraints'') can
isolate sections of extreme changes of curvature, so that those
sections do not influence nearby regions of gentle curvature change.

\begin{figure*}[tbh]
\begin{center}
\includegraphics[scale=0.4]{figs/local_c4.pdf}
\hspace{10mm}
\includegraphics[scale=0.4]{figs/local_oneway.pdf}
\begin{tabular}{ll}\\[-.8in] $\kappa$ \\[.4in] spline \end{tabular}
\caption{\label{oneway-locality}One-way constraints enforce locality.}
\end{center}
\end{figure*}

For example, Figure \ref{oneway-locality} shows how adding one-way
constraints keeps the variation of curvature localized to just two
segments of the overall spline, as opposed to the infinite extent of a
pure interpolating spline. The central point can be perturbed
arbitrarily without affecting the segments beyond the one-way
constraints. In this figure, the top plots show curvature as a
function of arc length, and the bottom plots show the control points
(with symbols representing the constraints) with the interpolating
curve. Note also that the curve with better locality also requires
considerably more curvature (and variation of curvature) to fit the
points.

There are two examples of a four-parameter primitive curve, both
straightforward generalizations of two-parameter counterparts. One is
the Minimal Variation Curve, which minimizes the $L_2$ norm of curvature
variation. Another is the generalization of the Euler spiral so that
curvature is an arbitrary cubic polynomial in arc length (the
definition of the Euler spiral is a linear relationship). Both of
these splines are $G^4$-continuous and use a primitive curve which has
four parameters. In practice, these curves are quite similar, and one
can easily be considered an approximation of the other.

The parameter space of a two-parameter spline can be understood as the
tangent angles of the endpoints, relative to the chord. Given
arbitrary endpoint tangents, a two-parameter curve family finds a
smooth curve meeting those constraints. Similarly, a four-parameter
curve family finds a smooth curve meeting given tangent and curvature
values at the endpoints.

\section{Minimum Variation Curve}
\label{sec-mvc}

The Minimum Variation Curve (MVC) is defined as the curve minimizing
the $L_2$ norm of the \emph{variation} in curvature. Moreton's
Ph.D. thesis \cite{Moreton92} argued in favor of this spline to
address known limitations of the MEC. In particular, the MEC lacks
roundness, but since a circular arc has zero curvature variation, it
is trivially the curve that minimizes the MVC cost functional when the
input points are co-circular.

\begin{equation}
\label{mvc-eq}
E_{\mbox{\scriptsize MVC}}[\kappa(s)] = \int_0^l (\kappa')^2\ ds\:.
\end{equation}

Most presentations of the MVC, including Moreton's, use a numerical
approach, approximating the curve with some other approximation (in
Moreton's case, quintic polynomials) and using a technique such as
conjugate gradient descent to minimize the cost functional. Gumhold's
more recent approach \cite{Gum04} is similar, also using conjugate
gradient descent. However, a variational approach analogous to that of
the MEC produces exact differential equations for the curve. The
simple Euler--Lagrange equation is inadequate for this task, as it only
handles functionals written in terms of a first derivative. Since the
MVC functional is in terms of the second derivative of $\theta$, the
more general Euler--Poisson equation is needed. Section
\ref{sec-euler-poisson} recaps the general technique from the calculus
of variations, then Section \ref{sec-eulerpoisson-mvc} applies it to
the MVC and gives the solution. One formulation is the impressively
simple $\kappa'' = \lambda y$, which is pleasingly analogous to $\kappa
= \lambda y$ as the general solution to the elastica (Equation
\ref{eq-simple-elastica}).

% Cheung C-\infty loop invariants (1987) may possibly anticipate this.

\subsection{Euler--Poisson equation}
\label{sec-euler-poisson}

Here we repeat the formulation of the general Euler--Poisson equation
as given by Elsgolts \cite{Elsgolts}:

Let us investigate the extreme value of the functional

\begin{equation}
\label{elsgolts1}
v[y(x)] = \int_{x_0}^{x_1} \!\! F(x, y(x), y'(x), \ldots, y^{(n)}(x))\ dx\:,
\end{equation}


\noindent where we consider the function F differentiable $n+2$ times with
respect to all arguments and we assume that boundary conditions are of
the form

\begin{eqnarray}
y(x_0) = y_0,\ y'(x_0) = y'_0,\ \ldots,\ y^{(n-1)}(x_0) = y_0^{(n-1)}\:; \\
y(x_1) = y_1,\ y'(x_1) = y'_1,\ \ldots,\ y^{(n-1)}(x_1) = y_1^{(n-1)}\:,
\end{eqnarray}

\noindent i.e. at the boundary points are given the values not only of the
function but also of its derivatives up to the order $n-1$ inclusive.

The function $y=y(x)$ that extremizes the functional given in
Equation \ref{elsgolts1} must be a solution of the equation

\begin{equation}
\label{euler-poisson}
{\frac{\partial F}{\partial y}} - {\frac{d}{dx}}{\frac{\partial F}
  {\partial y'}} + {\frac{d^2} 
  {dx^2}}{\frac{\partial F}{\partial y''}} + \ldots + (-1)^n {\frac{d^n}{dx^n}}
  {\frac{\partial F}{\partial y^{(n)}}} = 0
\end{equation}

\subsection{Euler--Poisson solution of MVC}
\label{sec-eulerpoisson-mvc}

We add Lagrange multipliers to represent the constraint that the
curve spans the endpoints. Adding the Lagrange multipliers and
eliminating $\kappa$ in favor of $\theta$, we seek to minimize

\begin{equation}
E = \int_0^l (\theta'')^2 + \lambda_1 \sin \theta + \lambda_2 \cos
\theta\ ds\:.
\end{equation}

To apply this equation to the MVC, we substitute $x = s$ and $y(x) =
\theta(s)$, so that

\begin{equation}
F(x, y, y', y'') = (y'')^2 + \lambda_1 \sin y + \lambda_2 \cos y\:.
\end{equation}

The relevant partial derivatives are

\begin{align}
{\frac{\partial F}{\partial y}} &= \lambda_1 \cos y - \lambda_2 \sin y\:, \\
{\frac{\partial F}{\partial y'}} &= 0\:, \\
{\frac{\partial F}{\partial y''}} &= 2y''\:, \\
\frac{d^2}{dx^2}{\frac{\partial F}{\partial y''}} &= 2y''''\:.
\end{align}

Applying \ref{euler-poisson} and reversing the variable substitution,
we derive an ordinary differential equation for the MVC,

\begin{equation}
\label{mvc-eqn}
\lambda_1 \cos \theta - \lambda_2 \sin \theta + 2\theta'''' = 0\:.
\end{equation}

Because at this point we are concerned only about the existence of the
Lagrange multipliers, not their actual values, we can ignore the
constant factor of $\frac{1}{2}$ and $-\frac{1}{2}$ for $\lambda_1$ and
$\lambda_2$, respectively.

\begin{equation}
\label{mvc-diffeq}
\theta'''' + \lambda_1 \cos \theta + \lambda_2 \sin \theta = 0\:.
\end{equation}

Note the pleasing similarity to the elastica (MEC) equation,

\begin{equation}
\label{mec-diffeq}
\theta'' + \lambda_1 \cos \theta + \lambda_2 \sin \theta = 0\:.
\end{equation}

As a special case when $\lambda_1$ and $\lambda_2$
become zero, all second order polynomial spirals $\kappa(s) = k_0 +
k_1 s + k_2 s^2$ are solutions to the MVC equation, as the the third
derivative of $\kappa$ (the fourth derivative of $\theta$)
vanishes. These solutions are analogous to circular arcs $\kappa(s) =
k_0$ as solutions of the elastica when the corresponding Lagrange
multipliers become zero.

Again as in the MEC case, we can reformulate this equation solely in
terms of first and higher derivatives of $\theta$, also eliminating
the Lagrange multipliers.

First, we differentiate Equation \ref{mvc-diffeq}, giving

\begin{equation}
\label{mvc-deriv}
\theta^{(5)} + \theta'(-\lambda_1 \sin \theta + \lambda_2 \cos \theta)\:.
\end{equation}

To integrate Equation \ref{mvc-diffeq}, we first multiply by
$\theta'$, giving

\begin{equation}
\theta''''\theta' + \theta'(\lambda_1 \cos \theta + \lambda_2 \sin \theta) = 0\:.
\end{equation}

This equation can readily be integrated, giving

\begin{equation}
\theta'''\theta' - \frac{(\theta'')^2}{2} + (\lambda_1 \sin \theta -
\lambda_2 \cos \theta) + C = 0\:.
\end{equation}

Combining with Equation \ref{mvc-deriv},

\begin{equation}
\theta^{(5)} + \theta'''(\theta')^2 - {\theta'(\theta'')^2} / 2 +
C\theta' = 0\:.
\end{equation}

Rewriting in terms of $\kappa$,

\begin{equation}
\kappa'''' + \kappa''\kappa^2 - \frac{\kappa(\kappa')^2}{2} + C\kappa
= 0\:.
\end{equation}

When the length is not constrained, the constant
$C$ becomes zero. This follows from transversality, a standard
technique in the calculus of variations \cite[p. 345]{Elsgolts}, and
is analogous to the way the corresponding constant becomes zero in the
case where the MEC is not length-constrained. Then, the equation becomes

\begin{equation}
\label{mvc-diffeq-k}
\kappa'''' + \kappa''\kappa^2 -  \tfrac{1}{2}\kappa(\kappa')^2 = 0\:.
\end{equation}

Equation \ref{mvc-diffeq-k} was also given by Brook et
al \cite{Brook05}; their solution does not encompass additional length
constraints (nonzero values of $C$). This equation is well suited to
standard numerical techniques such as Runge--Kutte integration for
very precise computation of the shape of the curve.

The MVC spline is defined as the curve that globally minimizes the
MVC metric over the space of all curves that interpolate the input
points. As in the MEC, this curve is made of segments of a
parametrized primitive curve, joined together at the control points
with continuity constraints. The MVC primitive curve (defined by
Equation \ref{mvc-diffeq-k}) is four parameter, and
it is $G^4$-continuous at the control points, as opposed to two
parameters and $G^2$ for the MEC.

At the endpoints of the MVC, $\kappa' = 0$ and $\kappa'' = 0$ (again,
analogous to the endpoint condition of the MEC, $\kappa=0$). It's
fairly easy to see why the latter conditions hold. At an endpoint, it
is possible to add at least points lying on a circular arc of matching
tangent and curvature. The resulting MVC spline must assign exactly
that circular arc to the additional segments, as the value of the MVC
functional itself for the arc is zero, and if there is any other curve
with a lower value for the functional, then it would have been a
better solution for the original problem. And since the MVC is
$G^4$-continuous, then $\kappa'$ and $\kappa''$ must match the values
for a circular arc, which are zero. These endpoint conditions can also
be derived straightforwardly (if abstractly) from the transversality
condition, a principle of the calculus of variation which determines
scalar parameters from the solution space to minimize the global
functional (see a textbook such as Elsgolts \cite{Elsgolts} for more
details).

There is also a simple equation for the MVC relating curvature and a
Cartesian coordinate, analogous to $\kappa = \lambda y$ for the MEC
case. To derive it, we first assume without loss of generality that
$\lambda_1 = 0$; unlike the formulation in terms of curvature alone,
the new equation will not be rotationally invariant. We then observe
that $\frac{dy}{ds} = \sin \theta$. Substituting that into Equation
\ref{mvc-diffeq}, we get

\begin{equation}
\theta'''' + \lambda_2y' = 0\:.
\end{equation}

Integrating (the constant of integration can be set at zero, since
that corresponds to a translation of the curve), substituting $\kappa =
\theta'$, and adjusting the constants so $\lambda = -\lambda_2$, the
resulting simple formulation is

\begin{equation}
\label{eq-mvc-simple}
\kappa'' = \lambda y\:.
\end{equation}

When $\lambda = 0$, this equation is equivalent to that of the Euler
spiral, in much the same way that $\lambda = 0$ is the value for which
the elastica becomes a circle. Kimia et al \cite{Kimia03} erroneously
gave this as the general solution to the MVC equation, correctly
observing that the Euler spiral is a special case of the MVC, but they
apparently overlooked the possibility of nonzero values of $\lambda$.

% I have an implementation of the MVC differential equation in mvc.c,
% but haven't wired it up into a spline.

\section{Polynomial spiral spline}
\label{sec-polynomial-spiral}

Another approach to four-parameter splines is to generalize the Euler
spiral to an implicit equation where curvature is a cubic polynomial
function of arc length. The general equation is:

\begin{equation}
\label{eq-poly-spiral}
\kappa(s) = a + bs + cs^2 + ds^3\:.
\end{equation}

This curve family is a very good approximation to the
MVC. Assuming small turning angles, $y$ is nearly proportional to $s$,
so substituting Equation \ref{eq-mvc-simple}, $\kappa'' \approx c_1s +
c_2$. Integrating twice (and bringing about two more constants of
integration) yields Equation \ref{eq-poly-spiral}. This approximation
is analogous to that of the Euler spiral approximating the MEC, but
can be expected to be even closer, as the nonlinear terms affect only
higher-order derivatives of curvature.

As in the MVC, the corresponding spline can be defined in terms of
enforcing $G^4$-continuity across control points. These are four
constraints per control point. Since each segment requires four
constraints to determine the four parameters of the polynomial, for an
open curve there are four additional parameters, or two for each
endpoint. One approach is to set tangent and curvature explicitly, but
a more natural approach (in the interpolating spline framework) is to
set $\kappa' = 0$ and $\kappa'' = 0$ at the endpoints, as in the
MVC. In this respect, the cubic polynomial spline is even
more closely related to the MVC than the Euler spiral is to the MEC,
because in the latter case the endpoint conditions differ; the natural
end condition is constant curvature (a circular arc), while the
natural endpoint condition for the MEC is zero curvature. In the
four-parameter world, the MVC endpoint conditions make sense and there
is no need to adjust them.

The cubic polynomial spiral spline was first proposed by Ohlin
\cite{ohlin87}, by analogy of making the pentic (polynomial) spline
nonlinear in the same way that the MEC is the nonlinear counterpart of
the cubic spline. Although Ohlin did express the natural variational
formulation of polynomial splines, and cited Mehlum's work indicating
that the Euler spiral spline was a consistent (extensional)
approximation to the MEC, he did not explicitly mention the MVC or
state that this new spline is a good approximation to it.

The idea of a curve defined as curvature being a cubic polynomial
function of arc length goes back even further. In 1936, Bloss proposed
a railroad transition spiral in which the curvature is a simple cubic
polynomial with respect to arc length \cite{Klauder01}. The Euler
spiral (or clothoid, as it is nearly universally known in that
application domain) is popular in railroad track design. The linear
change in curvature is desirably smooth on the interior of the
segment, but the literature has also long recognized the limitations
of smoothness at the joins between clothoid segments. These higher
derivatives of curvature become more significant as train speeds
increase. In particular, high speed train tracks are almost invariably
banked (or ``superelevated'') so that the rail on the outside of the
curve is higher than the inside, to a degree roughly proportional to
the curvature. Thus, passengers of a train traversing the tracks
experience a \emph{roll acceleration} roughly equal to the
\emph{second} derivative of curvature. At the join of two Euler spiral
segments, this roll acceleration is an impulse. Usually, the
suspension of the train provides enough cushioning to avoid an
unpleasant lurch, but curves with better continuity properties are
clearly desirable for a smooth, quiet ride. The Bloss
transition spiral is a very early example of a curve with higher
continuity, to avoid such impulses.

\begin{figure*}[tbh]
\begin{center}
\includegraphics[scale=0.4]{figs/local_c2.pdf}
\hspace{10mm}
\includegraphics[scale=0.4]{figs/local_c4.pdf}
\begin{tabular}{ll}\\[-.8in] $\kappa$ \\[.4in] spline \end{tabular}
\caption{\label{four-locality}$G^2$ spline has better locality than $G^4$.}
\end{center}
\end{figure*}

If $G^4$-continuity is smoother than $G^2$, then why not use it
everywhere? Unfortunately, the additional smoothness comes at the cost
of locality. As shown in Figure \ref{four-locality}, the effects of
perturbing a point ripple out almost twice as far as for the
Euler spiral spline. Since, for most applications, the difference in
smoothness is theoretical, rather than visible to the eye, it's better
to enjoy the superior locality properties of the $G^2$-continuous spline.

\section{Generalized constraints}
\label{sec-constraints}

The motivation for four-parameter splines showed a number of specific
examples of blended corners, straight-to-curve transitions, and so
on. This section presents a highly general technique that subsumes all
these examples, and provides a broad palette of curve transitions to
the designer.

A single segment of cubic polynomial spline has four free
parameters. In general, these can fit any tangent and
curvature constraints at the endpoints. One such example is to fit the
given tangent constraints of adjoining straight segments, as well as
zero curvature, as in the blended corners of Figure
\ref{fig-suitcase}.

The approach of this section will be to start from special cases, then
progressively generalize. First, observe that the input to the solver
for Figure \ref{fig-suitcase} must distinguish which segments are
straight and which are the curved corners. We propose the notation of
annotating points with half-circles. A segment between the two
straight sides of the half-circle is a straight line. A segment
between the two rounded sides is a blended corner. For such segments,
the solver fits a four-parameter spline segment to match the tangent
and curvature of the adjoining straight segment.

The next generalization is to allow more than one segment in the
curved section. In fact, any $G^4$-continuous spline interpolating
a sequence of control points has two free parameters at the
endpoints. For the most natural end conditions, these are determined by
constraining $\kappa' = 0$ and $\kappa'' = 0$, but it's also possible
to determine them by constraining tangent and curvature constraints to
specific values. In the case of the right half of Figure
\ref{oneway-locality}, there are two segments bracketed between the
half-circle sides of the one-way constraints, and the tangents and
curvatures are, as above, matched to the adjoining straight
segments. One important observation is that perturbing the central
point does not affect the curve beyond the one-way constraints.

\begin{figure*}[tbh]
\begin{center}
\includegraphics[scale=0.6]{figs/nonzerok.pdf}
\begin{tabular}{ll}\\[-1.5in] $\kappa$ \\[.75in] spline \end{tabular}
\caption{\label{fig-nonzerok}Matching nonzero curvatures.}
\end{center}
\end{figure*}

The next generalization is to match adjoining curvatures other than
zero. While straight-to-curve transitions are common, sometimes the
adjoining section will have some curvature, rather than be
straight. An example is shown in Figure \ref{fig-nonzerok}. The
general technique for the solver is to compute the adjoining curve
segments first, treating the flat side of the one-way constraint the
same as an endpoint, then use the tangent and curvature value at that
point to constrain the spline segment on the curved side. Generalizing
further, the one-way constraint is treated as a dependency, so that
the spline on the curved side depends on the tangent and curvature of
the other side, but not vice versa. In many cases, it's possible to
solve the entire spline by doing a topological sort of the segments,
and solving in order of dependency.

\begin{figure*}[tbh]
\begin{center}
\includegraphics[scale=0.6]{figs/cyclic.pdf}
\begin{tabular}{ll}\\[-2.5in] $\kappa$ \\[1in] spline \end{tabular}
\caption{\label{fig-cyclic}A one-way constraint creates a cyclic dependency.}
\end{center}
\end{figure*}


However, even this approach is not maximally general. Allowing
arbitrary annotations of control points can create a cyclic
dependency, as in Figure \ref{fig-cyclic}, which even so has a
meaningful solution. More importantly, the techniques above only allow
$G^4$-continuous joins for interior points, while, as we have seen,
Euler spiral segments ($G^2$-continuous joins) have better locality
properties.

In the general approach, each segment between two adjacent control
points is assigned a cubic polynomial spiral segment (i.e. as defined
by Equation \ref{eq-poly-spiral}). Note that an Euler spiral segment
fits into this framework; the parameters $c$ and $d$ are both
zero. Equivalently, $\kappa''$ is constrained to be zero at both
endpoints. For all types of internal points (other than corners, which
are considered endpoints) are also constrained to have
$G^2$-continuity, in other words, both tangent angle $\theta$ and
curvature $\kappa$ are constrained to be equal on both sides of a
control point. Different points have additional constraints, depending
on the type of point.

The total number of degrees of freedom (and thus, number of
constraints) is four times the number of segments. If each endpoint
has two constraints and each internal point has four, then the total
number of constraints is satisfied.

The complete list of point types, and associated mathematical
constraints, is given in the table below.

%\renewcommand{\arraystretch}{1.2}
\begin{table}[ht]
\[
\begin{array}{llll}
\mbox{\textbf{Type of constraint}} &
\multicolumn{2}{c}{\mbox{\textbf{Formula}}} &
\mbox{\textbf{Symbol}}
 \\
\hline
\mbox{Left endpoint} & & \kappa_r' = 0 &
\multirow{2}{10mm}{\includegraphics[scale = 0.8]{figs/cpoint-left}} \\
& & \kappa_r'' = 0 \\
\hline
\mbox{Right endpoint} & & \kappa_l' = 0 &
\multirow{2}{10mm}{\includegraphics[scale = 0.8]{figs/cpoint-right}} \\
& & \kappa_l''= 0 \\
\hline
G^2\ \mbox{curve point} & \theta_l = \theta_r & \kappa_l'' = 0 &
\multirow{2}{10mm}{\includegraphics[scale = 0.8]{figs/cpoint-g2}} \\
& \kappa_l = \kappa_r & \kappa_r'' = 0 \\
\hline
G^4\ \mbox{curve point} & \theta_l = \theta_r & \kappa_l' = \kappa_r' &
\multirow{2}{10mm}{\includegraphics[scale = 0.8]{figs/cpoint-g4}} \\
& \kappa_l = \kappa_r & \kappa_l'' = \kappa_r'' \\
\hline
\mbox{One-way (curve to terminal)} & \theta_l = \theta_r & \kappa_r' = 0 &
\multirow{2}{10mm}{\includegraphics[scale = 0.8]{figs/cpoint-ctt}} \\
& \kappa_l = \kappa_r & \kappa_r'' = 0 \\
\hline
\mbox{One-way (terminal to curve)} & \theta_l = \theta_r & \kappa_l' = 0 &
\multirow{2}{10mm}{\includegraphics[scale = 0.8]{figs/cpoint-ttc}} \\
& \kappa_l = \kappa_r & \kappa_l'' = 0 \\
\hline
\end{array}
\]
\caption{Constraints for curve points, and their corresponding formulae.}
\end{table}
\renewcommand{\arraystretch}{1.0}

For a given sequence of points with constraint annotations, the
resulting spline is defined as the curve that is piecewise cubic
polynomial spline, such that the tangent, curvature, and higher-order
derivatives satisfy the constraints given in the table above for each
point.

\begin{figure*}
\label{constraints-example}
\begin{center}
\includegraphics[scale=.8]{figs/constraints}
\caption{Examples of different kinds of constraint points.}
\end{center}
\end{figure*}

Figure \ref{constraints-example} shows a sequence of somewhat
arbitrary constraints, parallel with a curvature plot which shows the
effect of the different types of constraints in the curvature
domain. All segments between two $G^2$ curve points have linear
curvature. All segments between a $G^2$ point and an endpoint (or
between a $G^2$ point and the straight side of a one-way constraint)
have constant curvature, i.e. the segment is a circular arc. All of
the points have at least $G^2$ continuity, although if corner points
were added, those would have only $G^0$.

Section \ref{sec-global-solver} presents numerical techniques for satisfying
such a system of constraints, and Chapter \ref{chap-tobez} discusses
techniques for efficiently drawing the polynomial spline curves that
result. With all these components in place, the spline is both highly
flexible for drawing the types of shapes likely to arise in font
design, and also entirely practical for interactive editing.