\documentclass{mysketch}
\usepackage[pdftex]{graphicx}
\usepackage[scaled=.92]{helvet}
\usepackage{times}

%% The 'graphicx' package allows for the inclusion of EPS figures.

%\usepackage{graphicx}

%% use this for zero \parindent and non-zero \parskip, intelligently.

\usepackage{parskip}
\usepackage[labelfont=bf,textfont=it]{caption}

%% If you are submitting a paper to the annual conference, please replace 
%% the value ``0'' below with the numeric value of your OnlineID. 
%% If you are not submitting this paper to the annual conference, 
%% you may safely leave it at ``0'' -- it will not be included in the output.

\onlineid{sap\_0287}

\pagestyle{empty}

\begin{document}

\title{Eureka: Euler spiral splines}
\author{Raph Levien\thanks{email: raph.levien@gmail.com}\\UC Berkeley
\and Carlo S\'equin\thanks{email: sequin@cs.berkeley.edu}\\UC Berkeley}

\teaser{
  \includegraphics[width=6in]{figs/interp}
  \caption{Using Euler spiral segments in an interpolating spline
yields pleasing, $G^2$-continuous designs.
Our solver also robustly generates all intermediate curves
between the fattest and the skinniest font outline,
by simply linearly blending the two extreme sets of control points.\vspace{-2mm}}
%  \caption{Linearly interpolating control point positions s preserves $G^2$ continuity.}
}

\maketitle

For many applications, one would like to define a complex curve with
just a few points so the resulting curve smoothly passes through all
the points given. Interpolating splines are the most intuitive user
interface for designing curves such as font outlines. Another
application is to draw smooth roadways on maps given a sequence of
point samples along their length.

Given a sequence of points, if a curve is \emph{ideal} with regard to
some metric, then it will not change if another point is added along
the curve. If they differ, then one or the other cannot have been
ideal. A spline that is invariant with respect to the addition of
on-curve points is considered to be \emph{extensible}. All curves
minimizing the value of some functional are extensible.

Such curves are difficult to achieve, and the solutions are often not
robust. Hence, cheap solutions such as B-splines and explicit B\'eziers
are popular. But the potential for better results and a simpler
interface make it worthwhile to spend a little more computer power and
cleverness on implementing high quality interpolating splines.

A classical approach is to simulate a thin flexible strip constrained to
go through the control points. The mathematical idealization of such a
strip is the \emph{elastica,} also known as the Minimum Energy Curve
(MEC). This curve is defined as the one minimizing the functional
representing total bending energy of the curve: $
MEC = \int_0^l\kappa(s)^2 ds $ \\
Here, $\kappa$ represents the curvature, $0 \leq s \leq l$ represents
the arclength, and $l$ is the total length of the curve. The MEC has
many desirable features, including $G^2$ continuity across control
points. Further, curves of low bending energy generally look smooth
and vice versa; MEC is a reasonably good metric for smoothness.

However, the MEC has a fatal flaw: it doesn't always converge on a
solution. Particularly in cases where a segment turns by more than
$\pi$ radians of arc, the MEC tends to diverge, with the total energy
approaching zero as the length of the curve approaches $\infty$.

In addition, MEC is not a perfect metric for smoothness. The circle is
obviously the smoothest curve interpolating a sequence of co-circular
points, but the MEC curve is not quite a circle. It has
slightly lower bending energy than the circle, because it is
longer and the MEC functional scales inversely with length.

A previously proposed solution is the Minimum Variation Curve (MVC). While
the MEC minimizes the $L_2$ norm of curvature, the MVC minimizes the $L_2$
norm of the \emph{variation} of curvature, i.e. the derivative of
curvature with respect to arclength: \\
$
MVC = \int_0^l\Big (\frac{d\kappa(s)}{ds} \Big )^2 ds
$

The MVC generates a circular arc when possible (clearly, the
variation of curvature is zero and therefore optimum), and converges
in many cases where the MEC diverges, but convergence is still not
guaranteed, and computational complexity is considerably worse even
than the MEC, precluding use in interactive applications.

The Euler spiral (also known as clothoid or Cornu spiral) fixes all
these problems, and is far more robust and computationally
tractable. It is characterized by curvature linear in arclength. The
Euler spiral shares a close kinship with the MEC, and some authors
have considered it as a useful approximation to the latter curve, but
we believe it stands on its own merits. Like the MEC, it has $G^2$
continuity across control points.

\begin{figure}[h]
\begin{center}
  \includegraphics[width=1.5in]{figs/eulersp}
  \raisebox{.66in}{$\mbox{}\hspace{2mm} \Rightarrow\hspace{1mm}\mbox{}$}
  \raisebox{.05in}{\includegraphics[width=1.1in]{figs/sketch_a}}
\end{center}
\caption{Euler spiral as segment of interpolating spline.}
\end{figure}

The Euler spiral is a solution to the variational equation
corresponding the the $L_\infty$ norm of the curvature variation,
given angle constraints at endpoints, and we conjecture that it is
indeed the solution that minimizes this functional. Thus, the Euler
spiral has equal standing to be considered a variationally ``optimal'' spline
like the MEC and MVC: $
EULER = \max_{0\leq s \leq l}\Big |\frac{d\kappa(s)}{ds} \Big |
$



%\section*{Numerical techniques}

To be practical, a spline, even an optimum one, needs a good
implementation. We have developed a suite of numerical techniques for
computing Euler spirals, making them entirely practical. Our solver
computes the global solution to an Euler spline in tens of
microseconds, and the resulting B\'eziers (easy to plot on standard
hardware) approximate the $G^2$ continuous splines to any desired precision. By
contrast, linearly interpolating the control points of cubic B\'eziers
doesn't even preserve $G^1$ continuity in the general case, much less
$G^2$.

The Euler spiral spline is thus ideal for font design applications,
among others. In map-drawing applications, the resulting curves may
well turn out to be an exact representation, since clothoid spirals are
often used in road and railway design due to their ability to smoothly
connect straight and curved sections. From a variational analysis of the
curve, we now see that it is optimal in a mathematical sense in
addition to being practical and aesthetically pleasing.



%\bibliographystyle{acmsiggraph}
%\nocite{*}
%\bibliography{curves}

\end{document}