\documentclass{article}
\usepackage[pdftex]{graphicx}

\begin{document}

\author{Raph Levien and Carlo H. S\'equin}
\title{Interpolating splines: Which is the fairest of them all?}

\maketitle

\abstract

Interpolating splines are a basic primitive for designing planar
curves. There is a wide diversity in the literature but no consensus
on a ``best'' spline, or even criteria for preferring one spline over
another. For the case of $G^2$-continuous splines, we propose two
properties that can arguably be expected in any definition of
``best,'' and show any such spline is made from segments cut from a
single generating curve such as the Euler spiral.

Keywords: $G^2$-continuity, interpolating splines, 2-parameter
splines, extensionality, locality, Euler spirals, aesthetic curves.

\section{Introduction}

A popular technique for designing curves is to fit an interpolating
spline through a relatively sparse sequence of points input by a
designer. Designers want the aesthetically pleasing curves from the
spline even when the control points are quite sparse.
Other popular techniques for designing planar curves include
approximating splines, and also direct input of Bezier control
points. However, with these methods, the relationship between the
input and the resulting curve is often not intuitive.

If criterion for choosing the best spline was a simple functional
expression for cost, the best spline would be the one that minimizes
that function, a straightforward optimization problem. However, the
most straightforward fairness metric (the energy needed to bend a
strip of idealized elastic material into the shape) yields less than
ideal results. For some sequences of input points, optimization fails
to converge, and for others, results are clearly not ideal. For
example, for points lying on a circle, the minimum energy curve (MEC)
deviates from that circle.

It is not straightforward, then, to devise a metric that correlates
well with perceived fairness, much less overall goodness (taking into
account other factors such as robustness of convergence). Thus, this
variational approach is not popular in practice. Yet, assuming such a
hypothetical fairness metric existed, we can infer properties of the
resulting spline.

Requiring just two properties of the MEC spline, which clearly must
also hold across a wide range of splines defined in terms of
optimizing some cost function, collapses the design space of splines
from an unfathomable infinite-dimensional space to those derived from
cutting segments of a single \emph{generating curve.} The properties
of this generating curve map closely to properties of the resulting
spline, and, more importantly, a ``best'' spline can be chosen
empirically. In particular, rather than trying to devise a formula to
capture the aesthetic perception of smoothness, it's possible to
choose a curve based on the most pleasing results.

We assume that the section of the resulting spline curve between any
two consecutive control points is a single \emph{segment}, drawn from
some family of curves. For some splines, the decomposition into
segments follows obviously from the definition of the spline. For many
others, particularly those defined as the minimization of some cost
functional, the nature of this family of curve segments follows
indirectly from the spefic cost functional being minimized.

This paper highlights two properties of a spline defined as the curve
minimizing some cost functional, but not specific to any particular
cost functional. We also argue that these properties are likely to be
held by any interpolating spline considered ``best.'' One property is
\emph{extensionality,} which states that adding an additional control
point on the curve of an exsiting spline solution leaves the curve
unmodified. Intuitively, it makes sense that an optimal spline is
extensional---if the new spline is better, then it should have also
been a better solution to the original problem.

The other property is that the shape each segment of the spline
(between two adjacent control points) depends only on the two tangent
angles (with respect to the chord) at those control points. Thus, the
parameter space of all curve segments lies on a two-dimensional
manifold. This property holds for the MEC spline as well as several
others in the literature. It is, however, less intuitive that this
property is implied by the notion of a ``best'' spline, a case we
shall make in Section \ref{sec-two-param}.

The central result of this paper is that (given certain other
reasonable assumptions), \emph{any} spline that satisfies these two
properties has the additional property that each curve segment is cut
from a single generating curve.

Finally, we present some empirical measurements from a user study to
propose a promising candidate for the most pleasing generating curve,
and hence the best spline. This spline is at least a plausible
candidate for the fairest interpolating spline of them all.

%\emph{Do we want to introduce this somewhat hand-wavy concept? It begs
%  the questions of how to measure error, and also the corpus of curves
%  to measure over. On the other hand, the choice of ``best'' spline is
%  dependent on that corpus, so it probably makes sense, and does
%  motivate including other desirable properties than fairness,
%  particularly locality.}
%
%An alternative metric of ``goodness'' for an interpolating spline is,
%given a particular curve as a design target (for example, the shape of
%a letter outline in a font), what is the minimum number of control
%points needed to approximate that curve within a particular error
%tolerance. Since this metric is relative to a specific curve, it is
%probably best evaluated over a corpus.

\section{Two-parameter splines}
\label{sec-two-param}

A \emph{two-parameter} spline is defined as one in which every
interpolating curve segment between two adjacent control points is
drawn from a family with a two dimensional parameter space, modulo the
transform needed to make the endpoints of the curve coincide with the
two control points. This transform consists of scaling, rotation, and
translation, and its parameters are not counted, as they are uniquely
determined by the context of the curve segment within the spline.

One example of a two-parameter spline is the Euler spiral spline, most
easily defined as the curve having for each segment between adjacent
control points, curvature linear in arclength, i.e. $\kappa = \kappa_0
+ s\kappa_1$, and with continuous curvature throughout the curve
(i.e. G2 continuity). The two parameters in this case are $\kappa_0$
and $\kappa_1$.

Another example of a two-parameter spline is the Minimum Energy Curve
(MEC) spline, defined as the curve that goes through the given
control points and minimizes the energy functional representing the
bending energy of the curve. It is the mathematical idealization of a
flexible strip which is constrained to go through the control points,
and also slide freely (i.e. its length is not constrained). It is not
immediately obvious from the definition that the spline has the
two-parameter property, but careful analysis (such as the study by
Forsythe and Lee \cite{ForsytheLee}) shows that it is so.

The MEC energy functional is the integral over arclength of the square
of curvature. Thus, the MEC spline can also be defined as the curve
that minimizes the L2 norm of curvature. Mathematically, the MEC is
the curve that minimizes the energy functional:

\begin{equation}
E_{MEC}[\kappa(s)] = \int_0^l \kappa^2 ds
\end{equation}

\begin{figure*}[ht]
\begin{center}
\includegraphics[scale=0.8]{figs/threecurves.pdf}
\caption{\label{threecurves-fig}Euler's spiral, rectangular elastica,
  and cubic parabola.}
\end{center}
\end{figure*}

As shown by Forsythe and Lee \cite{ForsytheLee}, this spline can also
be defined as piecewise segments of the \emph{rectangular elastica}
between each pair of adjacent control points, with G2 continuity
across control points (that is, the curvature is continuous
everywhere). The rectangular elastica is shown, along with two other
related curves, in Figure \ref{threecurves-fig}.

%\emph{could talk about endpoint conditions, but it's a detail of
%  little importance}

Besides the MEC and Euler spiral spline, a number of other
interpolating splines fit into the two parameter model. The spline
developed for the Ikarus font design system \cite{Karow87}, the spline
used in Metafont \cite{Hobby85}, and the ``circle spline'' of
S\'equin, Lee, and Yin \cite{DBLP:journals/cad/SequinLY05} also use
curve segments drawn from a two-parameter space. Finally, while
technically not an interpolating spline, the Potrace automated
curve-tracing system \cite{Selinger03} also uses a two-parameter
family of primitive curves.

\subsection{Locality}

\begin{figure*}[tbh]
\begin{center}
\includegraphics[scale=0.4]{figs/local_c2.pdf}
\includegraphics[scale=0.4]{figs/local_c4.pdf}
\caption{\label{props-locality}$G^2$ spline has better locality than $G^4$.}
\end{center}
\end{figure*}

Another desirable property of interpolating splines is
\emph{locality,} the property that perturbing one control point makes
only small changes to the rest of the spline. In general, with
interpolating splines there is a tradeoff between locality and
fairness. For example, the MVC (Minimum Variation Curvature) spline
has G4 continuity, but changes to a control point extend farther than
the MEC or Euler spiral spline. This is illustrated in Figure
\ref{props-locality}, which shows the Euler spiral spline on the left
(same locality properties as MEC) and an analogous $G^4$ spline (same
locality properties as MVC) on the right. As an extreme example in the other
direction, the degenerate ``straight line spline'' connecting the
control points with a polygon, has ideal locality but worst-case
fairness.

In general, fair extensible interpolating splines require
perturbations to ripple out indefinitely, but with exponential
die-off. Other splines (such as the circle spline) can bound the
effect of perturbations to a finite number of control points, but give
up fairness or extensibility or both. Note that several other
approaches to interactive curve design, such as direct input of Bezier
control points and some approximating splines, have excellent locality
properties, but without the usability advantages of interpolating
splines.

Based on evidence from existing splines in the literature, in general
two parameter splines have better locality than ones defined from a
larger parameter space. It is straightforward to achieve $G^2$
continuity with two parameters, and no higher degree of continuity is
required for a perception of fairness. Thus, it is reasonable to
expect that any ``best'' spline to those having the
two-parameter property.

\section{Extensionality}

One property closely associated with the idea of a ``best'' spline is
extensionality. In an extensional spline, adding an additional control
point lying on an existing spline leaves the curve unchanged. Among
other authors, Knuth presented extensionality as one of a set of
desirable properties for splines in a 1989 lecture on Mathematical
Typography \cite[pp. 39--42]{Knuth:1999:DT}. This property is also
known as \emph{consistency}, for example in Moreton's Ph. D. thesis
\cite[p. 28]{Moreton92}.

Extensionality follows directly from the definition of a spline as
minimizing some objective function. If adding a new point on the curve
changes the value of the functional, then the new curve must also be a
better solution to the old set of constraints.

While all variationally defined splines are extensional (including the
MEC and related Minimum Variation Curve), there exist splines not
defined varationally which are extensible, such as the Euler spiral
spline (first described by Birkhoff and de Boor \cite{Birkhoff65} in
1964, and implemented by Even Mehlum in the Autokon system in the
early 1970's \cite{Mehlum74}).

\begin{figure*}[tbh]
\begin{center}
\includegraphics[scale=0.4]{figs/cspline.pdf}
\caption{\label{props-cspline-ext}Circle spline extensionality failure.}
\end{center}
\end{figure*}

Many splines in the literature fail to exhibit extensionality. One
dramatic examples is the circle spline
\cite{DBLP:journals/cad/SequinLY05}, as shown in figure
\ref{props-cspline-ext}, in which each spline segment is a blend
between two circular arcs, each defined by 3 subsequent data
points. Adding a new point at the center dramatically changes the
curve, adding new inflection points. The Metafont \cite{Hobby85} and
Ikarus \cite{Karow87} splines (also discussed in section
\ref{sec-two-param}) are two other splines that fall into the
two-parameter category but are also not perfectly extensional. (The
Metafont spline can be thought of as a cubic approximation to the
Euler spiral spline, and therefore approximates the extensionality
property of that spline, especially for small angles).

\section{Generating curves}

The central result of this paper is this: for any two-parameter,
extensional splines, there exists a \emph{generating curve} so that
all curve segments between adjacent control points can be cut from
that generating curve, subject to scaling, rotation, translation, and
mirror image transformations, to make the endpoints of the cut segment
align with the endpoints in the spline.

Thus, any spline in this family can be defined simply in terms of the
generating curve. In some ways, this definition circles back to one of
the earliest formulations of nonlinear splines. Birkhoff and de Boor
wrote in 1964, referring to two approximations to MEC splines, ``After
looking carefully into the relevant equations, one realizes that the
schemes of \cite{MacLaren58} and \cite{Fowler62} do not approximate
mechanical splines more closely than other curves---nor does it seem
particularly desirable to have them do so. For example, they
approximate equally well to Hermite interpolation by segments of
\emph{Euler's spirals,} joined together with continuous
curvature''. \cite[p. 171]{Birkhoff65}. Here we propose that the
Euler spiral is but one of a family of desirable curves for
constructing extensional interpolating splines.

\newtheorem{conjecture}{Conjecture}
\begin{conjecture}
In an extensible, two parameter spline, there exists a curve such that
for any spline segment (parameterized by angles $\theta_0$ and
$\theta_1$ there exists two points on the curve ($s_0$ and $s_1$) such
that the segment of the curve between them, when transformed by rotation,
scaling and translation so that the endpoints coincide, also coincides
along the length of the segment.
\end{conjecture}

\begin{figure*}[tbh]
\begin{center}
\includegraphics[scale=0.5]{figs/two_continue.pdf}
\caption{\label{two-continue}Construction for extending two parameter spline.}
\end{center}
\end{figure*}

In broad strokes, the outline is that any given segment of spline can
be extended to a larger, more complete curve. Further, that curve is
unique up to scaling, rotation, translation, and mirror image. The
curve must be at least $G^2$ continuous.

Intuitively, for any curve segment from any instance of the spline,
there is a deterministic process for extending, or continuing, the
shape of the curve. This process works at either end of the curve, and
can also be run in reverse to shorten a curve segment. Thus, if there
were two curve segments which could not be cut from the same
generating curve, then this extensionality property allows us to
find a continuation of one of the curves so that it has the same
endpoint tangent angles as the other. Then, the two-parameter property
requires these curves to be identical. Any curve segment not cut from
the generating curve would either break extensionality or require a
larger parameter space.

The extension of a spline segment is shown in Figure
\ref{two-continue}. Starting with the segment defined by $\theta_0$
and $\theta_1$, vary
the two parameters in such a way as to extend the curve, preserving
the initial segment as a subcurve. For concreteness, imagine extending
the curve by $\Delta s$ arclength. Increase $\theta_0$ by $\Delta s \;
\tan \theta_1$, and increase $\theta_1$ by $\Delta s(\kappa_1 - \tan
\theta_1)$, where $\kappa_1$ is the curvature at the $\theta_1$ side of
the curve, assuming a chordlength of $1$. The $\tan \theta_1$ term
represents rotation of the chord, while $\kappa_1$ represents the
additional rotation of the tangent on that side of the curve.

Both conditions are necessary for the generating curve property to
hold, and there are counterexamples when either is not present. The
Ikarus, Metafont, and circle splines are two parameter and not
extensional, and do not have a single generating curve. The Minimum
Variation Curve (the minimization of L2 norm of curvature variation)
is extensible and four-parameter, and also does not have a single
generating curve.

\section{Aesthetic curves}

A very promising family of candidates for generating curves is the
\emph{aesthetic curve}, also known as the log-aesthetic curve
\cite{Miura05}. These are defined as having a straight line when
$\kappa' / \kappa$ is plotted against $\kappa$ with log-log scale. In
addition to a number of special cases (including the equiangular
spiral and Nielsen's spiral), the general formula for aesthetic curves
is $\kappa = s^\alpha$, where the exponent $\alpha$ is a parameter.

An intuitive motivation for the aesthetic curve is that the eye is not
as sensitive to \emph{absolute} variation of curvature as relative. In
areas of high curvature, high variation of curvature is also
tolerated. However, in low-curvature areas, even small variations in
curvature are visible.

\begin{figure*}[tbh]
\begin{center}
\includegraphics[scale=0.5]{figs/aesthetic.pdf}
\caption{\label{aesthetic-examples}Test instrument for fairness user study.}
\end{center}
\end{figure*}

The literature on aesthetic curves doesn't tend to include curves with
inflection points---on a log-log plot, these are off the
scale. However, since it is well known that the aesthetic curve with
$\alpha=1$ is the Euler spiral, curves with inflection points are
known to be part of the family. In general, odd integer values for
$\alpha$ have odd symmetry and admit inflection points, but it's
possible to generalize the formula to $\kappa = signum(s)|s|^\alpha$
to admit a continuous range of exponents. The family of such curves
(used to interpolate a zigzag sequence of control points) is shown in
Figure \ref{aesthetic-examples}.

\begin{figure*}[tbh]
\begin{center}
\includegraphics[scale=0.4]{figs/survey.pdf}
\caption{\label{survey-results}Results of aesthetic curve preference survey.}
\end{center}
\end{figure*}

Of these, the minimal bending energy is obtained with the exponent
$\alpha$ near $1$, corresponding to the Euler spiral. However, a
simple user study (simply asking respondents\footnote{The survey was
  presented in a thread on the Typophiles web forum, available at
  http://typophile.com/node/52821} to select the fairest curve from the
  choices shown in Figure \ref{aesthetic-examples}) finds that the
mean preferred exponent is $1.78$, a curve for which the MEC energy
is 6\% higher than the Euler spiral.

This experiment suggests two results. First, the MEC energy does not
accurately predict actual human perception of fairness. Second, the
asthetic curve with an exponent near $1.78$ is empirically a
generating curve for
an even fairer interpolating spline than the Euler spiral, the best
known to date.

\section{Properties of splines from generating curves}

Almost any curve can in principle be used as generating
curve. However, some will clearly work better than others. The
properties of the generating curve direcly influence the properties of
the resulting spline, and this section illuminates the connections
between the two.


\subsection{Inflection point}

Not all curves contain an inflection point, including many
spirals. Such curves can be used as the generating curve for a spline,
but the resulting spline will fail to converge when the target curve
contains inflection points.

Therefore, most single spirals, including the equiangular spiral,
Nielsen's spiral, and so on, are not broadly suitable as generating
curves. However, with the suitable tweak to signs so that the curve is
defined as $\kappa = signum(s)|s|^\alpha$, all curves in the aesthetic
curve family admit inflection points.

\subsection{Monotone curvature}

One desirable property in a spline is monotone curvature between
adjacent control points. The eye is particularly sensitive to minima
and maxima of curvature. This property insures that all such extrema
conincide with control points.

A fair amount of literature is concerned with constraining existing
curves (such as cubic polynomials) to have monotone
curvature. In the framework of generating curves, it is
straightforward - simply choose a generating curve that has monotone
curvature throughout. The Euler spiral, which has curvature linear
with arclength, obviously has this property. All instances in the
aesthetic curve family also have monotone curvature.

Note that the MEC does not have this property. Especially for segments
that are nearly circular, the MEC has a tendency to add additional
curvature maxima.

\subsection{Roundness}

\begin{figure*}[tbh]
\begin{center}
\includegraphics[scale=0.3]{figs/quadrant.pdf}
\caption{\label{mec-roundness}MEC roundness failure.}
\end{center}
\end{figure*}

A specific aspect related to fairness is roundness, the property that
control points placed on a circle yield an exact circle as the resulting
spline. It seems intuitively obvious that a circle is the fairest
possible curve in such situations, but many splines do not have this
property.

In particular, the MEC spline deviates fairly signficantly from
roundness, as shown in Figure \ref{mec-roundness}. The Euler spiral
spline, by contrast, readily forms a circle. What is the general
property of the generator curve that yields roundness in the
corresponding spline?

In general, it is that the curvature variation within a curve segment
tends to zero as the endpoint tangents tend to the symmetrical. This
property is expressed as a limit because curves like the Euler spiral
don't actually contain a circular arc, just approximate
it. Mathematically, this property is implied by:

\[
\lim_{s \rightarrow \infty} \frac{\kappa'}{\kappa^2} = 0
\]

This property holds for nearly any well-behaved curve with monotone
curvature, including curves with the implicit equation
$\kappa=s^\alpha$ for any exponent $\alpha$.

\subsection{Locality}
\label{locality-subsec}

\begin{figure*}[tbh]
\begin{center}
\includegraphics[scale=0.4]{figs/locality.pdf}
\caption{\label{props-locality-exp}Locality improves as exponent increases.}
\end{center}
\end{figure*}

In general, the shallower the curvature variation near the inflection
point of the generating curve, the better the locality of the
resulting spline. The aesthetic curve family varies from very steep to
very shallow curvature variation in this region across its parameter
space. For this concrete family of curves, we can accurately quantify
this relationship.

The falloff factor, plotted against aesthetic curve exponent, is shown
in Figure \ref{props-locality-exp}. For $\alpha = 1$, the Euler
spiral, each subsequent ripple is $.268$ the amplitude of the
preceding one (this ratio can be determined analytically by using the
small-angle approximation and solving for $\kappa_0\theta_1 =
\kappa_1\theta_0$ for the endpoints of a segment, and has a value of
$1/(2 + \sqrt{3})$). Note also that the MEC spline has the same
locality properties as the Euler spiral spline. For the preferred
exponent of $1.78$, the falloff factor is $0.173$, noticeably
better. It is possible to achieve even better locality at the expense
of fairness of the curve, if that is desired.

\section{Practical implementation}

Having an optimal interpolating spline would be of primarily academic
interest if it were expensive or impractical to compute. One reason
variationally defined splines are not popular is that numerical
solvers tend to be slow. For example, Moreton's
conjugate gradient solver for MEC and MVC curves took 18 and 75
seconds, respectively, to
compute the optimal solution to a 7 point spline \cite[p. 99]{Moreton92}.

Fortunately, the general two-parameter extensible spline admits an
extremely fast, simple implementation. Since the curve segments
are defined by two parameters, for any given generating curve it is
practical to precompute a lookup table indexed by the tangent angles
at the endpoints. The lookup table stores the curvatures at the
endpoints (used for enforcing curvature continuity across control
points), as well as the position and tangent angle of a midpoint, used
for subdivision while rendering the curve. Indeed, drawing the curve
is only slightly more complex than the standard de Casteljau
subdivision for rendering Bezier curves; the only difference is the
use of a lookup table rather than an algebraic formula to determine
the midpoint.

The global solver uses a Newton-style solver to enforce the curvature
continuity constraints across all control points. The partial
derivatives of curvature deltas with respect to tangent angles form a
tridiagonal matrix, which is easily solved in linear time. 
Each iteration of the global solver is essentially the same as the
matrix solver in the Metafont spline. Newton iteration converges
extremely quickly, so for most configurations of control points, three
or four iterations are sufficient to attain high precision.

The overall algorithm is efficient enough to offer excellent
interactive performance even when implemented in JavaScript for
execution in a standard web browser. The numerical code is
approximately 230 lines of JavaScript, and a set of 32x32 lookup
tables requires an additional 200k of uncompressed data. No doubt
careful tuning could reduce the data requirement further.

\section{Conclusions}

Interpolating splines are a useful and important primitive for
designing curves. However, choosing one from the multiplicity in the
literature is not easy. There is no universal consensus on what makes
the best spline, or even a metric for fairness. We have argued that
any spline to be considered as a candidate for ``best'' must satisfy
two properties: extensibility and having segments defined by two
parameters. Splines satisfying these properties can be defined simply
in terms of a generating curve, and the properties of this curve map
straightforwardly to the corresponding spline.

A very promising family for this generating curve is the aesthetic
curve, defined by the implicit equation $\kappa = s^\alpha$; its
properties match almost exactly to desirable properties for
constructing a spline. However, user testing shows that splines made
with an exponent of $1.78$ are perceived as fairer than those made
from the Euler spiral---a result not predicted by the bending energy
metric for fairness.

While the spline presented in this paper is not provably the best
possible, it is a very strong candidate. We have also mapped out the
design space, considerably narrowing the possible areas to find a
better spline. Within the two-parameter framework, a better spline
would have to be based on a better generating curve, but it is not at
all obvious how such a curve would be constructed. The properties of
the aesthetic curve---monotonic curvature, smooth curvature variation,
and shallow curvature variation near the inflection point to improve
locality---are exactly the properties desirable in a generating curve
for an interpolating spline. It is not easy to see how one could find
a very different curve which would also generate a good spline.

Another potential place to look for a better spline is to use more
than two parameters. Clearly, this is the correct approach for
achieving greater than $G^2$ continuity, but higher degrees of
continuity are not visibly smoother to the eye, and come at the cost
of poorer locality. It is conceivable that somebody may design a
spline which uses more than two  parameters to actually improve
locality, but there is nothing to suggest that this will actually work.

The two-parameter property is a useful organizing principle in the
taxonomy of splines. Many existing splines in the literature (MEC,
Euler spiral spline, IKARUS, Metafont spline, circle spline, Potrace
primitive) fall into this category, demonstrating its validity.
Further, splines in this category show good locality properties,
especially compared against splines with a higher-dimensional
parameter space.

We have quantified a tradeoff between fairness and locality, which is
covered by the parameter space of of the aesthetic curve. The Euler
spiral spline, the best interpolating spline known previously, is one
point along this spectrum. A higher but moderate value for the
exponent actually improves both fairness (as measured empirically) and
locality, providing results that are strictly better in both criteria.

Even though the Euler spiral has been known since the early 1970's,
other choices of interpolating spline have been more popular, perhaps
due to expedience or a misplaced concern for efficiency, perhaps
simply because of a lack of knowledge about the superior properties of
the spline. The aesthetic curve with an exponent near $1.78$ is an
even better spline, and our analysis of the design space strongly
suggests that it is among the best possible. We finally have a
plausbile answer to the question of which interpolating spline is the
fairest of them all.

\bibliographystyle{plain}
\bibliography{curves}

\end{document}