\chapter{Properties of splines}
\label{props-chapter}

The space of all possible interpolating splines is infinite,
and there is no consensus in the spline literature of which
is ``best.'' However, a number of properties have emerged as good
criteria for evaluating interpolating splines. Foremost among these is
\emph{fairness,} which is a technical term for smoothness. There is no
agreed-upon formal definition for fairness, but it is associated with
smoothly varying curvature.

Although fairness is important, other properties matter too. For
example, some splines (including those modeling the mechanical spline)
do not exist for arbitrary sequences of points. This chapter explores
fairness deeply, and lists other desirable properties of splines. In
subsequent chapters, the evaluation of splines will be based on the
properties described below.

%The space of all possible interpolating splines is unboundedly
%large. This work is concerned with characterizing that space,
%identifying tradeoffs within it, and identifying optimum examples
%(given a tradeoff). Thus, we define a number of desirable properties
%of splines.

%In this chapter, we propose a set of properties useful for deeper
%understanding of various splines. Some such properties are common to
%all functions which might reasonably be considered splines. For
%example, when the points of the control polygon lie in a straight
%line, that line is the only reasonable result.

\section{Fairness}

In almost all applications, the most important property of a spline is
\emph{fairness,} also known as smoothness. Fairness is ultimately a
property of the way humans perceive curves, not an abstract
mathematical property. As in Justice Potter
Stewart's definition of pornography, ``I know it when I see
it.''\footnote{Justice Potter Stewart, concurring opinion in
  Jacobellis v. Ohio 378 U.S. 184 (1964), regarding possible obscenity
  in The Lovers.}

Even so, there are a number of metrics that correlate reasonably well
with perception of fairness. Knowledge of the human visual system and
empirical evidence show that fairness is intimately tied to
\emph{curvature,} which of course is an objective mathematical
property. Curves with regions of extremely high curvature are clearly
not fair. In addition, while more subtle, discontinuities in curvature
and regions with large curvature variation are also perceived as
lack of fairness.

%A fair curve won't have sharp or wild variations in curvature. When
%driving along a fair curve, the motions of the steering wheel are
%economical. Of course, interpolating the points of the control polygon
%may demand hairpin turns. A fair spline exhibits no more variation in
%curvature than necessary.

%This steering analogy is a colorful way to visualize the underlying
%geometry, and is also directly relevant in the application of road and
%railroad track design. There, $x''$ corresponds directly to forces
%experienced by passengers. For high-speed trains, even higher
%derivatives have direct physical meaning. When curvature varies, the
%forces experienced at the front of the train are different from those
%experienced at the back, causing stresses and noise.

Curvature is central in many other application domains as well. There
is compelling evidence that the human visual system perceives curves
in terms of curvature features, motivating a substantial body of
literature on \emph{shape completion,} or inferring missing segments
of curves when shapes are occluded in the visual field. A recent
example, advocating the Euler spiral spline, is Kimia et al. \cite{Kimia03}.

\subsection{Empirical testing of fairness}
\label{empirical-fairness-sec}

Bending energy has been proposed as a fairness metric, and minimizing
that metric is the definition of the MEC spline (which is discussed in
considerable detail throughout this thesis). However, does it
accurately measure human perception of smoothness?

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

To address this question, I did a very simple user study, asking
respondents to choose the fairest curve from a range of possibilities,
shown in Figure \ref{aesthetic-examples}.\footnote{The discussion
  thread is on the web at http://typophile.com/node/52821} The
individual curves are all generated with the formula $\kappa =
cs^\alpha$, with $\alpha$ the varying parameter and $c$ chosen to make
the curvature continuous at the endpoints. These are part of a family
of so-called ``log-aesthetic curves'' \cite{Miura05}, discussed in more detail in Section \ref{sec-aesthetic}.

\begin{figure*}[tbh]
\begin{center}
\includegraphics[scale=0.6]{figs/survey.pdf}
\caption{\label{survey}Survey results for aesthetic curve preference.}
\end{center}
\end{figure*}

Among the curves in this family, minimal bending energy is obtained
with an exponent $\alpha$ near 0.9; thus the Euler spiral, with the
exponent $\alpha=1$, also yields very low bending energy. The on-line
study then asked respondents to select the ``fairest'' curve from the
choices shown in Figure \ref{aesthetic-examples}. The results are
plotted in Figure \ref{survey}, along with the MEC bending energy. The
mean preferred exponent is 1.78; this is a curve for which the bending
energy is 6\% higher than the Euler spiral. These results confirm the
belief that the concept of fairness is rather fuzzy, and that it
varies significantly among different designers and graphic
artists. Nonetheless, the preference for an exponent in the range 1.5
to 2 is marked. In particular, this study establishes that MEC energy
does not in fact accurately predict the perception of fairness.

\section{Continuity}

A concrete property related to fairness is the \emph{degree of
  continuity,} essentially the number of higher derivatives that
exist. A parametrized polygon, for example, has a first derivative
everywhere, but that first derivative is not continuous. Thus, a
polygon has only $G^0$-continuity (the property of being a connected
curve). All splines worthy of the name have at least $G^1$-continuity,
meaning that the second derivative exists everywhere, but relatively
fewer have $G^2$-continuity, corresponding to continuous curvature. It
is worth remembering, though, that wild but continuous swings in
curvature are no fairer in practice than tiny jumps at the control
points.

Intuitively,
curvature is the position of the steering wheel when driving a car
along the curve. Therefore, $G^2$ continuity is equivalent to the lack
of jerks of the steering wheel.

\begin{figure*}[tbh]
\begin{center}
\includegraphics[scale=0.4]{figs/continuity.pdf}
\caption{\label{cspline-continuity}Continuity $\neq$ fairness.}
\end{center}
\end{figure*}

Figure \ref{cspline-continuity} illustrates clearly that continuity is not
the same as fairness. The spline on the left is an Euler spiral
spline, with $G^2$ continuity, and the spline on the right is a
circle spline, with $G^3$. It seems clear that the one on the
left, the $G^2$
spline, is fairer, because it exhibits less variation in curvature.

\section{Roundness}

One specific aspect of fairness is \emph{roundness.}  A round spline
always yields a circular arc when the control points are co-circular.
It seems intuitively obvious that a circular arc is the fairest (or
smoothest) curve.

It makes sense for circular arcs to be the result of splines, as the
circle is often found in nature and is also essential in
mechanics. However, many splines merely produce an approximation, some
better than others. In particular, any spline based on polynomials
cannot be exactly round.

Roundness is not an all-or-nothing property. Even the splines that do
not generate perfect circular arcs produce curves that are fairly
close. Exactly \emph{how} close can be quantified, as we will see in
the discussions of individual splines.

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

Splines other than polynomials can also fail the roundness
property. For example, the curve minimizing the bending energy of a
thin strip (the Minimum Energy Curve) fails to describe a perfect
circular arc. The deviation from roundness, interpolating three control
points placed on an equilateral triangle, is shown in Figure
\ref{props-mec-roundness}, and will be discussed in more detail in
Section \ref{mec-props}. In this figure, the circle is on the inside,
and the MEC describes a curve with somewhat larger total arc length.

\section{Extensionality}

An \emph{extensional} interpolating spline is one in which adding a new
point to the control polygon, lying on the curve generated from the
original control polygon, does not change the resulting curve. Unlike
fairness, extensionality is not so much a property of the curve
segments used to generate the spline
as of the effect of changes to the control polygon (adding and
deleting points) on the resulting curve.

Extensionality is closely related to the concept of choosing an
optimal curve with respect to some fairness metric. If adding an
on-curve point changes the curve, either the new or the old curve
must not have been optimal.  Therefore, splines defined in terms of
minimizing a functional tend to be extensional. Extensionality is a
powerful filter for weeding out crude approximations, but it does
admit a variety of interesting splines in addition to those defined in
terms of optimization.

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


Figure \ref{props-cspline-ext} shows a spline with particularly poor
extensionality, the circle spline (described in more detail in Section
\ref{cspline-sec}). Adding the point in the center changes the tangent
radically at that point, introducing new inflection points, and
clearly degrading the overall quality. In this case, the problem
arises because the tangents are derived from a local window; when
three consecutive control points are co-linear, that line determines
the tangent of the middle one even when it is not ideal given the
global shape.

Roundness is a very weak extensionality property; for the special case
of control points on a circle, adding an additional point on the
circle does not change the resulting curve. However, even though these
two properties are related, there are round splines that are not
extensional (Ikarus \cite{Karow87}), and extensional splines that are
not round (MEC).

\section{Existence and uniqueness}
\label{props-existence-sec}

One highly desirable property of a spline is that all control polygons
yield interpolating curves. Especially in interactive applications,
where control polygons may well pass through ill-defined or degenerate
states on the way, it is inconvenient at best for there to be no
solution.

\vspace{5mm}
\begin{figure*}[tbh]
\begin{center}
\includegraphics[scale=0.7]{figs/runaway.pdf}
\caption{\label{runaway-fig}Nonexistence of solution to MEC.}
\end{center}
\end{figure*}

Figure \ref{runaway-fig} shows a configuration in which the MEC spline
has no viable solution. In this configuration, the tangent angles at
the endpoints are constrained to be at greater than a right angle with
respect to the chord, but the curve is otherwise unconstrained. In
particular, the length of the curve is allowed to assume the value
that minimizes overall bending energy. Intuition suggests that, for
any given functional to optimize, \emph{some} curve is better than
none at all, so the lack of a solution is surprising.

Better intuition comes from considering the MEC as a model of a
mechanical spline. Bending energy tends to decrease as the curve gets
longer. In particular, the longer curves in Figure \ref{runaway-fig}
have a lower bending energy than the shorter ones. Thus, the
mechanical springiness applies a force to pull in more
length. In a real spline, at some point this force becomes so small
that it is easily defeated by the friction at the control point, but
in the mathematical idealization, it would continue indefinitely until
the length became infinite and the bending energy zero.

Ironically, even though intuition would suggest that \emph{some} curve
is better than no curve at all, the splines with the worst existence
properties are those defined in terms of minimizing a fairness
functional. Apparently, fairness is not the \emph{only} measure of
quality. In general, splines defined in terms of meeting continuity
constraints at the control points tend to have better existence
properties. For example, an interpolating Euler spiral spline always
exists, as discussed in Section \ref{euler-existence-sec}.

\vspace{5mm}
\begin{figure*}[tbh]
\begin{center}
\includegraphics[scale=0.6]{figs/unstable.png}
\caption{\label{props-unstable}Uniqueness failure in Euler spiral spline.}
% Sophie sees it and says 'What are those, eyes? Are those...for
% bubbles, and wind?'
\end{center}
\end{figure*}

Another desirable property is \emph{uniqueness,} the principle that
only one curve exists that satisfies the definition of the spline, for
a fixed input. For splines that are defined by optimization, the
concern is that there may be multiple local minima, where a local
minimum is a solution that is locally optimum under smooth deformation
of the curve while it still interpolates the control points.
Correspondingly, for splines that are defined in terms of continuity
constraints on parametrized curve segments, there may be multiple
assignments of parameters that satisfy the constraints and still
interpolate the points. Figure \ref{props-unstable} shows an example,
based on the Euler spiral spline. Both curves interpolate the same
five input points, in the same order, both are composed of Euler
spiral segments between each pair of adjacent control points, and both
satisfy the $G^2$-continuity constraints.

It is possible to fix the uniqueness problems of a spline by adding an
additional (global) criterion, to prefer one solution to the other.
Then, the revised spline can be defined as one that both satisfies the
local constraints and also optimizes the global criterion. It may be
difficult to properly implement a spline revised in this way, as
search for a global optimum is often expensive, but at least such a
spline is well defined.

As will be discussed in Section \ref{hobby-sec}, Hobby used the
criteria of existence and uniqueness to motivate the design of his
spline. Using ``mock curvature'' guarantees existence of a unique
solution, even though it has less desirable fairness properties.

\section{Locality}

% *** this section still needs rewrite ***

When a control point moves, how much of the resulting curve changes? A
small section in the neighborhood of the control point, perhaps, or
does the entire spline change? This is the property of
\emph{locality}.

Some splines have \emph{finite support,} a particularly strong form of
locality. In these splines, moving a control point changes the curve
only for a section bracketed by a finite number of control points on
either side of the one moving. For example, in circle-splines this
section consists of four segments bracketed by stepping out two
control points in either direction. %***PICTURE***

% todo: reference is stray, but that's because the derivation needs
% writing (it's in the CAD '09 source)
However, finite support conflicts directly with extensionality, so in
general we will measure locality in terms of how quickly the effect of
moving a control point dies out as we move away from it. In splines
with good locality, this effect falls off exponentially in the
distance from the control point (measured by counting control
points). Then, locality can be quantified by the ratio of effect from
one control point to the next. Section \ref{sec-aesthetic} shows, this
ratio is $2 + \sqrt{3} \approx 3.73$ for the Euler spiral spline (as
well as the MEC).

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

Figure \ref{props-locality} shows two splines with different
locality. The one on the left is an Euler spiral spline with
$G^2$-continuity, and the one on the right is its $G^4$
counterpart. In general, there is a tradeoff between the degree of
continuity and the locality, so the latter spline has more wiggling
farther from the perturbed point.

\section{Transformational invariance}

Another basic property is invariance under various transformations and
symmetries. All functions worthy of being considered splines are
invariant under rigid body transformations (rotation and translation)
as well as uniform scaling. If the control polygon undergoes a rigid
body transformation, then the resulting curve undergoes exactly the
same transformation.

Further, all of the splines we consider in this thesis are invariant
under mirror symmetry and front-to-back reversal of the order of the
points in the control polygon. These are very common properties, but
it is worth noting that quaternion splines computed on the surface of
the sphere lack front-to-back symmetry.

A sometimes desirable property of splines is \emph{affine invariance},
meaning that the shape of the spline is preserved through affine
transformation of the control points. This property is observed in
many polynomial-based splines, but it conflicts with the roundness
property. Consider that any round spline fits a circular arc to an
input consisting of three control points. Yet, affine transformation
of the resulting curve yields an ellipse, which in general would not
match the spline resulting from the three transformed control points
-- which would also need to be a circular arc due to the roundness
property. For the types of designs considered in this thesis,
roundness is more important than affine invariance, so the latter will
not be considered in detail.

\section{Counting parameters}

In an arbitrary spline, the family of curve segments between any two
control points is potentially drawn from an infinite-dimensional
space. In practice, most splines use curve segments chosen from a
finite-dimensional manifold. Generally, there is a vector of real
parameters that uniquely determines the shape of the curve between any
two endpoints. In counting these parameters, we hold the endpoints
fixed, and apply the rotation, scaling, and translation to make the
curve coincide with these endpoints.

Thus, the degenerate spline consisting of straight lines is
effectively a zero-parameter spline. A fair number of interesting
splines fall into the category of two-parameter splines, and these are
discussed further in Chapter \ref{two-chapter}. Well constructed
splines in this class can achieve $G^2$ continuity.

\section{Monotone curvature}
\label{monotone-curvature-sec}

The human visual system is particularly sensitive to minima and maxima
of curvature. This property suggests that all curvature extrema should
coincide with the given control points, and that the spline segments
in between should exhibit monotone curvature. A fair amount of
literature is concerned with constraining existing curves (such as
cubic polynomials) to have monotone curvature.  One such citation is
``Measures of Fairness for Curves and Surfaces''
\cite[p. 93]{Roulier94}, which also discusses fairness metrics in
considerable detail. The Euler spiral, in which curvature varies
linearly with arc length, obviously has this property, as do other
related curves. However, the MEC does not have this property; for
symmetrical end conditions it has a tendency to increase arc length
and to add a curvature maximum in the middle of the segment. The MVC
also in general does not place curvature extrema to coincide with the
control points.

\begin{figure*}[tbh]
\begin{center}
\includegraphics[scale=1.0]{figs/attneave.pdf}
\caption{\label{attneave-fig}Attneave's curvature experiment
  \cite{Attneave54}.}
\end{center}
\end{figure*}

Evidence that the visual system is sensitive to minima and maxima of
curvature goes all the way back to Attneave's seminal experiments in
the mid 1950's \cite{Attneave54}. Attneave presented test subjects
with somewhat random, blobby drawings and asked them to annotate which
points along the outline were the most salient. An example is shown in
Figure \ref{attneave-fig}. The ``porcupine quills'' emanating from the
shape represent the relative frequency that subjects identified the
points. These strongly tend to coincide with curvature
extrema. As such, in interactive curve design it is reasonable to
expect designers to place these points first, then refine the curves
with more control points only as needed. A good spline should
accommodate such a designer by preserving the curvature extrema as
marked.

\section{Summary}

The most important property for interpolating splines is
fairness. Yet, other properties such as robustness and locality are
also important.

Several previous authors have proposed a set of properties desirable
in splines. Knuth's enumeration of such properties, for example,
comprised invariance, symmetry, extensionality, locality, smoothness,
and roundness \cite[pp. 39--42]{Knuth:1999:DT}.

Similarly, Henry Moreton in his Ph.D. thesis \cite[ch. 2]{Moreton92} gives
a rather exhaustive list of properties, including most of the ones
described above.