[most of a first draft in place of cad paper
raph.levien@gmail.com**20090105053407] {
hunk ./cad.tex 2
+\usepackage[pdftex]{graphicx}
+
hunk ./cad.tex 13
-Interpolating splines are a basic primitive, especially for 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. We propose two properties likely to be 
+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. We propose two properties that are reasonable to require in
+any definition of ``best,'' and show any such splines is made from
+segments cut from a single generating curve such as the Euler spiral.
hunk ./cad.tex 22
+A popular technique for designing curves is to fit an interpolating
+spline through a relatively sparse sequence of points input by a
+designer. With accurately placed dense points, almost any spline will
+do. But to draw a smooth curve, the smoother the spline, the fewer
+points are needed to achieve a good result.
+
+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 there were a simple mathematical criterion for choosing the best
+spline, the best spline would be the one that minimizes that cost
+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. Further, we find, these properties collapse 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.
+
+This paper highlights two properties in particular of the MEC spline,
+closely related to the fact that it's defined as the optimum relative
+to a cost functional, but not specific to the exact choice of
+functional to be optimized. 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 tangent
+angle (with respect to the chord) at those control points. Thus, the
+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}
+
+The Minimum Energy Curve (MEC) spline is defined as the curve which
+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. the length
+is not constrained).
+
+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 studied by Forsythe \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 derivative of curvature with
+respect to arclength exists 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}
+
+A number of existing interpolating splines fit into the two parameter
+model, including of course the MEC and Euler spiral spline. In
+addition, the spline developed for the Ikarus font design system
+\cite{Karow87}, the spline used in Metafont \cite{Hobby85}, and the
+``circle spline'' of Sequ\'in, 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 primitive family.
+
+\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}.
+
+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 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 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 that that segment of the curve, 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, and translation. The curve must be at
+least $G^1$ continuous, and it may be that the argument requires the
+curve to contain an inflection point.
+
+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{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. Properties
+of the generating curve.
+
+\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.
+
+\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.
+
+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
+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} = 0
+\]
+
+It's interesting to note that any spiral with the implicit equation
+$\kappa=s^\alpha$ has this property. In the limiting case as $\alpha
+\rightarrow \infty$, this curve approximate Nielsen's spiral.
+
+\subsection{Locality}
+
+\emph{This section really needs empirical results. Perhaps it is
+  acceptable to leave out?}
+
+
+\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; its properties match almost exactly to desirable properties for
+constructing a spline. Further, user testing shows that splines
+made with an exponent of 1.5 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 definitively the best
+possible, it's reasonable to believe that it's very close---that any
+future improvement is incremental. Even if so, the central result of
+this paper illuminates the path and shows where to look. One potential
+approach is to come up with a generating curve which is empirically
+better. However, the aesthetic curve meets the desirable properties
+(monotonic curvature, smooth curvature variation, especially shallower
+curvature variation near the inflection point) closely, so it is
+difficult to imagine how a better curve would be substantially
+different.
hunk ./cad.tex 363
-\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.}
+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. It is plausible that a future spline could be devised
+with both good locality and more than two parameters, but there is no
+evidence suggesting it is particularly promising.
hunk ./cad.tex 373
-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.
+Of the splines in the existing literature, the Euler spiral spline
+seems best. Other choices seem 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. We also
+propose a novel interpolating spline based on the aesthetic curve,
+with even slightly better fairness and locality properties. Our
+analysis of the design space strongly suggests that this spline is
+among the best possible. Perhaps we finally have a solution to the
+question of which interpolating spline is the fairest of them all.
hunk ./cad.tex 383
+\bibliographystyle{plain}
+\bibliography{curves}
hunk ./curves.bib 248
-  title     = {Fair, G2- and C2-continuous circle splines for the interpolation
+  title     = {Fair, {G2}- and {C2}-continuous circle splines for the interpolation
hunk ./curves.bib 821
+@inproceedings{Miura07,
+  author = "Kenjiro T Miura and Mariko Yagi and Yohei Kawata and Shin'ichi Agari and Makoto Fujisawa and Junji Sone",
+  title = "Input of Log-aesthetic Curves with a Pen Tablet",
+  booktitle = {Humans and Computers},
+  year = 2007,
+  pages = {83--88},
+  address = {Chofu, Tokyo}
+}
+
hunk ./curves.bib 839
+
+@misc{Selinger03,
+  author = "Peter Selinger",
+  title = "Potrace: a polygon-based tracing algorithm",
+  year = 2003,
+  url = "http://potrace.sourceforge.net/potrace.pdf"
+}
hunk ./props.tex 152
-\section{Extensibility}
+\section{Extensionality}
hunk ./props.tex 157
-fairness, extensibility is not so much a property of the curve
+fairness, extensionality is not so much a property of the curve
hunk ./props.tex 162
-Roundness is a very weak extensibility property; for the special case
+Roundness is a very weak extensionality property; for the special case
hunk ./props.tex 168
-Extensibility is closely related to the concept of choosing an optimal
+Extensionality is closely related to the concept of choosing an optimal
hunk ./props.tex 172
-be extensible. Extensibility is a powerful filter for weeding out
+be extensible. Extensionality is a powerful filter for weeding out
hunk ./props.tex 179
-\caption{\label{props-cspline-ext}Circle spline extensibility failure.}
+\caption{\label{props-cspline-ext}Circle spline extensionality failure.}
hunk ./props.tex 185
-extensibility, the circle spline (described in more detail in Section
+extensionality, the circle spline (described in more detail in Section
hunk ./props.tex 249
-However, finite support conflicts directly with extensibility, so in
+However, finite support conflicts directly with extensionality, so in
}
