\chapter{Numerical toolbox}
\label{toolbox-chapter}
One of the reasons for the enduring popularity of polynomial-based
splines is the ease of computation, and straightforward numerical
properties such as stability. By contrast, variational techniques are
considered to be extremely slow and unwieldy. For example, Moreton's
MVC solver took about 2.5 billion CPU cycles (75 s on the hardware of
the day) to compute the MVC solution to the 7-point data set posed by
Woodford \cite{Woodford1969}. Even though more refined techniques have
since been published, the prejudice continues. Kimia et
al \cite{Kimia03} state, ``The major shortcomings of the elastica are
that (i) they are not scale-invariant, (ii) they are computationally
expensive to derive, and (iii) they do not lead to circular completion
curves when the point-tangent pairs are, in fact, co-circular (i.e.,
both lie on the same circle).''
This chapter presents a toolbox of numerical techniques for computing
sophisticated splines quickly, and with high precision. Section
\ref{sec-numint} presents a polynomial approximation to a fundamental
integral that encompasses both the Euler spiral and the general
polynomial spiral used as a primitive in Chapter
\ref{chapter-fourparam}. Section \ref{solve-euler} presents a very
efficient solver fitting an Euler spiral segment to arbitrary endpoint
tangent constraints. Section \ref{sec-global-solver} presents a fast
Newton solver that globally satisfies the continuity constraints for
the interpolating spline. Section \ref{sec-lookup} presents a fast 2-D
lookup table approach for solving arbitrary two-parameter extensional
splines using a single code framework.
The combination of these techniques, along with optimized drawing
code, presented in Chapter \ref{chap-tobez}, yields an
interpolating spline that is extremely efficient to compute and easily
provides interactive response speeds. The complete spline is
implemented and released in the open source libspiro library, which
has also been integrated into FontForge, a font editing tool, and
Inkscape, a vector drawing editor.
The software release accompanying this thesis also includes a
JavaScript implementation, which runs in standard Web browsers.