\chapter{Introduction}
\label{chap-intro}

A basic design task is drawing smooth curves in the plane. Curves are
needed in purely aesthetic applications such as making vector
drawings, purely industrial applications such as the cross-sections of
airplane wings or railway track layouts, and also applications both
functional and artistic, such as font design.

There are several approaches to curve design. The most popular is
drawing with B\'ezier curves, usually cubic. These curves are
versatile and very easy to compute and manipulate, but they are
somewhat difficult to learn, and it is especially difficult to get
smooth curves. In expert hands, the results are good, but for less
experienced designers, adding more control points to tweak a curve
often leads to more lumpiness.

Another approach is to sample real-world data (for example, from a
sculpture), then fit a curve to it. Since these points are noisy, it's
most common to fit an \emph{approximating spline} through them -- the
spline goes near the points but not necessarily through them.

The main focus of this thesis is \emph{interpolating splines,} or
curves that go through the points given, in sequence. With a good
interpolating spline, the designer can enter a relatively sparse
sequence of data points, and the result is a smooth curve.

\begin{figure*}
\begin{center}
\includegraphics[scale=.5]{figs/duckworks_keel}
\caption{\label{intro-mechanical}A mechanical spline.}
\end{center}
\end{figure*}

Interpolating splines have their roots in the mechanical spline, a
thin strip of flexible material constrained to go through the chosen
points with weighted implements (called ``ducks'' or ``whales'' due to
their shape), but otherwise free. An example is shown in Figure
\ref{intro-mechanical}. Such a strip will naturally find its minimal
energy configuration. Indeed, one approach to interpolating splines is
simply to simulate the mechanical spline. As we shall see,
such an approach is severely flawed.

A part of the problem with interpolating splines is that there are
many plausible constructions, with quite a few in actual use, but no
real consensus on which one is best, or even how to adequately measure
or compare. Many of the interpolating splines in use seem to have been
chosen based on expedience, simple representation, or cheap
computational cost. However, these criteria are not really justified,
not only because Moore's law has made even intricate computations
feasible at interactive speeds, but also because excellent practical
splines exist with a simple representation and an efficient
implementation.

This thesis will closely examine the question of what interpolating
spline is \emph{ideal} out of all possibilities. Such a focus
reduces the space of alternatives to consider, excluding all the
many rough and crude approximations.

By far, the most important property of an interpolating spline is
\emph{fairness,} (also known, less technically, as
smoothness). Indeed, one way to define an interpolating spline is to
choose a fairness metric (such as the total bending energy of a
flexible strip) and optimize it, given that the curve passes through
the control points. However, this approach may compromise other
important properties, such as robust convergence, locality
(intuitively, lack of ripples), stability, and others. Chapter
\ref{props-chapter} lists all these desirable properties of
interpolating splines and describes them in detail.


The mechanical spline is the basis for essentially all following work
in splines. Its mathematical idealization is the \emph{Minimum Energy
  Curve} (MEC), and the curve describing segments between adjacent
control points is the \emph{elastica.} This curve has surprising and
deep properties, and there are a number of ways to fully understand it
-- as the result of an energy minimization, as the limit of a finite
element system consisting of rigid beams connected by flexible
springs, and as the physical analogue of a pendulum (which explains why
the curve is periodic). Chapter \ref{elastica-chapter} explores all
these characterizations and the connections between them.

Yet, while the MEC is the optimum of a particular functional (bending
energy), it is clearly not the best possible spline. Experiment shows
that bending energy does not accurately predict perceived
smoothness. This finding is also supported by theoretical analysis --
in particular, the MEC spline lacks \emph{roundness,} the property
that control points arranged on a circular arc yields that arc. Further,
optimizing this particular metric yields a spline with poor robustness
-- for many inputs, no optimum solution exists at all. Even so, the
MEC has many desirable properties, some of which are worth
preserving. Two in particular stand out. An optimum spline must be
\emph{extensional,} meaning that adding an additional control point on
the curve of an existing spline preserves the shape of the curve.
Further, the MEC has the property that the family of curve segments
between any two adjacent control points is a manifold with a
two-dimensional parameter space. Chapter \ref{two-chapter} argues
that, for two-dimensional drawing applications, any ``best'' spline
should also have this property.

\begin{figure*}[tbh]
\begin{center}
\includegraphics[scale=0.5]{figs/rect_elast.pdf}
\caption{\label{intro-elast}Rectangular elastica.}
\end{center}
\end{figure*}

\begin{figure*}[tbh]
\begin{center}
\includegraphics[scale=0.5]{figs/espiral_45.pdf}
\caption{\label{intro-euler}Euler spiral.}
\end{center}
\end{figure*}

Chapter \ref{two-chapter} also presents one of the central technical
results of this thesis: any spline that is both extensional and
two-parameter is derived from a single, rigid generating curve, with
each segment cut from the curve, then rotated, scaled, and translated
into place to align with the endpoints. In the MEC, this curve is the
\emph{rectangular elastica} (shown in Figure \ref{intro-elast}), but
other choices yield better splines. In particular, the \emph{Euler
  spiral} (shown in Figure \ref{intro-euler}) produces results similar
to the MEC, but fixing the roundness and robustness problems. Chapter
\ref{two-chapter} then concludes by exploring the potential for the
family of \emph{log-aesthetic} curves to produce splines even slightly
``better'' than the Euler spiral spline, improving simultaneously
fairness (as determined by empirical measurement) and locality.

The two basic underlying curves for two-parameter splines, the
elastica and the Euler spiral, both have rich histories, dating back
hundreds of years.  But they have not been fully explained in one
concise source until now. For both of these curves, Jacob Bernoulli
wrote down the precise mathematical description and partially explored
the nature of the curves, while Euler characterized them fully. Chapter
\ref{hist-elast-chapter} deeply explores the history of the elastica,
including its subsequent role in founding the field of study of
elliptical integrals, which are now also useful for giving a
closed-form, analytical solution to the shape of the curve. Similarly,
Chapter \ref{hist-euler-chapter} explores the history of the Euler
spiral, including its repeated rediscovery and applications in other
diverse fields, such as solving diffraction problems and layout of
railroad tracks.

Two-parameter splines are ideal as basic interpolating splines used
for planar curve design, but there are applications where a higher
degree of geometric continuity is desired. Chapter
\ref{chapter-fourparam} presents the logical extension to a
four-parameter space, providing $G^4$-continuity, but at the cost of
reduced locality. The underlying curve family is also useful for
satisfying a richer family of constraints than merely that the curve
passes through the control points. In particular, such constraints can
specify smooth transitions from straight sections to curves, a
frequent pattern in font designs. The chapter also explores the
connection of this spline to the \emph{Minimum Variation Curve,} a
known spline based on minimizing a metric defined in terms of the
\emph{variation} of curvature rather than curvature itself, as in the
MEC.

None of these theoretical results about optimal splines would be much
use without an efficient, practical implementation. Chapter
\ref{toolbox-chapter} provides a toolbox of such techniques, including:
efficiently computing the integral defining the Euler spiral and
its generalization to a four-parameter spline; solving the parameters
of this curve to meet given tangent constraints; and providing an
efficient Newton-style solver for simultaneously solving all
the constraints required for a given spline. Together, these numerical
techniques add up to a very fast solver for splines, entirely suitable
for interactive work even in limited computational environments.

\begin{figure*}
\begin{center}
\includegraphics[scale=.7]{figs/a_fat}
\hspace{10mm}
\includegraphics[scale=.7]{figs/a_fat_bezier}
\caption{\label{intro-optim}Conversion to optimized B\'ezier curves.}
\end{center}
\end{figure*}

Even after solving the global spline and determining an analytical
curve that meets the constraints, the resulting curve is still not in
a form that can be widely used. Euler spirals (and their cubic
polynomial generalization, even more so) are considered ``special
functions'' and are very unlikely to be present as primitives in
graphics files formats, CAD applications, and so on. Thus, another
important component for actually using these splines in practice is
conversion to a more widely-supported format, of which by far the most
popular is cubic B\'ezier curves. Chapter \ref{chap-tobez} describes
how to convert these curves into B\'ezier form, with a tradeoff
between the computational effort expended on optimization and the
conciseness of the representation. For contexts when the size of the
representation matters (for example, when downloading fonts over the
network), the chapter presents a fully optimized technique, yielding
the best possible B\'ezier representation with respect to the
given error threshold. Figure \ref{intro-optim} shows an example of a
letterform converted into such an optimized B\'ezier representation.

A major motivation for this work was to improve tools for designing
fonts. I designed several complete fonts entirely using the splines
described in this thesis, and one, \emph{Inconsolata,} is released and
is widely used. Chapter \ref{fonts-chapter} presents some of these
font designs, and also discusses particular aspects of splines
relevant to the specific application of font design, including
prospects for more easily creating fonts with \emph{variation,} for
example, a smooth blending between light and heavy weights.

While the primary focus of this thesis is planar curves, the
principles are also useful for splines in space, as explored in
Chapter \ref{space-chapter}. An intrinsic formulation of planar curves
is a relationship between arc length and curvature. The corresponding
intrinsic form for a space curve is a relationship between arc length
and both curvature and torsion. Three parameters are sufficient to
attain $G^2$-continuity of space curves, as opposed to two for planar
curves. The MEC generalizes easily from planar to space curves, but of
course has the same limitations as the planar MEC. A beautiful curve
primitive due to Mehlum \cite{Meh94} generalizes the Euler spiral to
space curves. In addition to its excellent properties as a spline
primitive, it has a beautiful geometric construction in terms of
rolling up an Euler spiral on the surface of the sphere.

Chapter \ref{conclusion-chapter} concludes and summarizes the main
results of this thesis. The spline curves presented in the following
chapters are practical and well-suited to design tasks such as
fonts. Theoretical analysis characterizes large regions of the space
of all possible splines, suggesting that the ideal interpolating
spline is, in fact, drawn from an easy-to-understand family. In
addition, the discovery that all extensional, two-parameter curves are
derived from a characteristic generating curve unifies previously
disparate areas of the literature, in particular the Euler spiral
spline and variational techniques. It is hoped that these beautiful
curves will become more popular in the future, now that their
properties are better known, and their implementation need not be much
more complex or computationally expensive than various crude
polynomial approximations have been in the past.



% todo: I'm not sure if we really need to go into much detail with spirals

% \section{Spirals and their properties}
%
%We define a \emph{spiral} as a curve of monotone curvature. Other
%definitions exist, including monotonically increasing radius in a
%polar coordinates representation, but that definition admits curves
%that don't seem especially spiral-like, such as $r = \theta + .09 * 10
%\sin \theta$. (TODO: plot). A general continuous curve is piecewise
%spiral, with monotonic curvature between points of curvature extrema
%(called \emph{vertex} in the literature).

%\ref{Guggenheimer77}, Theorem 3-12 (Kneser): Any circle of curvature
%of a spiral arc contains every smaller circle of curvatuyre of the arc
%in its interior and in its turn is contained in the interior of every
%circle of curvature of greater radius.

%As stated, the property applies to spiral arcs, but it is just as
%valid for general spiral curves of monotone curvature, even if
%containing an inflection. It has several other corollaries, notably
%the fact that such a spiral does not self-intersect.