\chapter{Two-parameter splines} \label{two-chapter} The broad goal of this work is to find the \emph{best} spline, or at least provide a menu of best choices, each suited to a specific requirement. In attempting to characterize the space of all splines, including making a taxonomy of existing splines in the literature, a remarkable number share this property: \begin{quote} \label{two-param-def} \textbf{A two-parameter spline} is defined as one for which each curve segment between two knots is uniquely determined by the two angles between tangent and chord at the endpoints of the segment. \end{quote} Examples of two-parameter splines include the Minimum Energy Curve, the Euler spiral spline, Mehlum's {\sc kurgla 1}, Hobby's spline, Ikarus, and S\'equin's circle spline. Note that the count of parameters excludes the scaling, rotation, and translation required to get the curve segment to coincide with the two endpoints -- those additional parameters are uniquely determined by the constraints that the curve segment fits the endpoints, providing no additional flexibility for the shape of the curve. Any given two-parameter spline can be characterized by two properties: the family of curves parametrized by the endpoint tangent angles, and the algorithm used to determine the tangent angles. For example, the Euler spiral spline uses a curve family with linearly varying curvature, and uses a global solver to ensure $G^2$-continuity to determine the tangents. Of the two-parameter splines listed above, the MEC and the Euler spiral are extensional. In the case of the MEC, this property follows directly from the variational statement -- if adding a new on-curve point would produce a new curve with a lower cost functional, that curve would have satisfied the old constraints as well. In addition, both splines are based on cutting segments from a fixed \emph{generating curve}, the rectangular elastica or the Euler spiral. These properties are not simply coincidental. In fact, all two-parameter, extensional splines correspond to a single generating curve, and any generating curve can be used as the basis of a two-parameter extensional spline. The two families, then, are essentially equivalent. \section{Extensional two-parameter splines have a generating curve} \label{extensional-equivalence} A central result of this thesis is that for any extensional two-parameter spline there exists a generator curve so that all curve segments between adjacent control points can be cut from that generator curve, subject to scaling, rotation, translation, and mirror image transformations to make the endpoints of the cut segments align with the endpoints in the spline. Thus, any spline in this family can be defined simply in terms of the generator curve. In some ways, this definition circles back to one of the earliest formulations of nonlinear 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}. The Euler spiral is but one of a family of desirable curves for constructing extensional interpolating splines. \newtheorem{theorem}{Theorem} \begin{theorem} In an extensional, $G^2$-continuous, two-parameter spline, there exists a curve such that for any spline segment (parametrized by angles $\theta_0$ and $\theta_1$) there exist two points on the curve ($s_0$ and $s_1$) such that the 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{theorem} \begin{figure*}[tbh] \begin{center} \includegraphics[scale=0.9]{figs/two_continue.pdf} \caption{\label{two-continue}Incremental construction of the generator curve of a two-parameter spline.} \end{center} \end{figure*} A typical section of curve is shown in Figure \ref{two-continue}. For some given endpoint angles, the generated curve segment is the section from $s_0$ to $s_2$. Because of the extensionality, for any $s_1$ along this curve, the subdivided curve from $s_0$ to $s_1$ (which is the result of applying $\theta_0$ and $\theta_1$ endpoint constraints) must be consistent with the original segment. Modulo scaling, the curvature $\kappa$ and its derivatives $\kappa'$ and $\kappa''$ must of course also match between these two segments. The proof of this theorem revolves around the quantity $\kappa'/\kappa^2$, which is also the limit of $6(\theta_1-\theta_0)/(\theta_0+\theta_1)^2$ as $\theta_0$ and $\theta_1$ both approach zero, i.e. as the length of the curve segment becomes infinitesimal (this limit follows from Equation \ref{fit-euler-approx}, which is derived in detail in Section \ref{solve-euler}). This quantity represents the amount of curvature variation for a segment of a set amount of curvature -- it is invariant to similarity transformations including uniform scaling. As such, for a given generator curve, it uniquely identifies a point on the curve (modulo periodicity, if the curve is periodic as opposed to monotone in curvature). We propose that for any two-parameter spline that is also extensional, the \emph{second} derivative of curvature, suitably normalized for scale invariance, $\kappa''/\kappa^3$, is uniquely determined given a particular value of $\kappa'/\kappa^2$. If there are two curve segments with different values for this second derivative, then it is possible to cut subsegments from each with identical $\theta_0$ and $\theta_1$ values. However, the value of $\kappa''/\kappa^3$ remains invariant even after such a cutting, so there are two different values for this. Yet, the two parameter property states that there exists only a single curve for a given $\theta_0,\theta_1$ pair -- a contradiction! Thus, there is a process for constructing the generator curve. Start with arbitrary $\kappa$ and $\kappa'$ values sampled from some point on the curve, then continually derive $\kappa''$ based on the lookup process suggested by the above relation: find a curve segment that has the correct value for $\kappa'/\kappa^2$, then sample $\kappa''/\kappa^3$ at that point. Continually integrate (in the sense of an ordinary differential equation), and the result is a curve. The final component of the argument is that for any given $\theta_0,\theta_1$ pair, there exists a segment cut from this curve such that it is equal to the spline segment. Determine $\kappa'/\kappa^2$ for one side ($s_0$) of the spline segment, and find that point on the generator curve. Continue extending the curve until the other side is reached. Since at each point $\kappa''/\kappa^3$ must be equal between the two curves, the curves themselves must also be equal. This argument depends on the assumption that the curve is a continuous function of the parameters $\theta_0$ and $\theta_1$. We conjecture that this assumption follows from the assumption of $G^2$-continuity and extensionality, but do not have a rigorous proof. It is also possible the continuity assumptions could be weakened and the theorem would still be valid. Both the two-parameter and extensionality conditions are necessary for the generator curve property to hold, and there are counterexamples when either is not present. The Ikarus and Metafont splines are two-parameter curves, but not extensional, and they do not have a single generator curve. The Minimum Variation Curve (discussed in much more detail in Section \ref{sec-mvc}) is extensional but does not fit into a two-parameter space, and also does not have a single generator curve. % --- old text follows --- The Minimum Energy Curve and the Euler spiral spline have a number of features in common, among them that all segments between two adjacent control points are fully determined by two parameters. This count of parameters does not include the scaling, rotation, and translation needed to make the two endpoints coincide -- just the shape of the curve once the positions of the endpoints are fixed. In fact, the parameter space for each such segment is described by the tangent angles at endpoints. Since our definition of ``interpolating spline'' requires $G^1$-continuity, determining a single tangent angle at each control point suffices. Thus, combining a two-parameter curve family with a technique for determining tangent angles at the control points yields an interpolating spline. Note that there are also several splines in the literature designed to approximate the MEC (quite accurately in the case of small angles), but do not fit into the two-parameter framework. In general, cubic polynomial curves have four parameters. In a standard cubic spline, the curve segments can be any cubic polynomial, so the parameter space is four dimensional. Parametrizing by chord length approximates the MEC more closely but does not reduce the dimensionality of the parameter space. Similarly, the scale invariant MEC (dubbed SI-MEC in \cite{Moreton93}) has segments that are piecewise elastica, and there is an additional parameter global to the spline (and associated with tension forces at the endpoints, in a physical model of the spline) that increases the dimension space of individual segments from the two of the pure MEC to the three admitted by the elastica. % --- begin old stuff While the previous chapter examined the elastica with constrained endpoints, a more general problem is the minimum energy curve that interpolates a sequence of control points. More formally, we seek, over the space of all curves that pass through the control points $(x_i, y_i)$ in order, the one that minimizes the MEC energy functional, restated here: \begin{equation} E_{\mbox{\scriptsize MEC}}[\kappa(s)] = \int_0^l \kappa^2 ds \end{equation} This problem is the mathematical idealization of a mechanical spline through control points fixed in position but free to rotate, and with an infinitely thin beam free to slide through them with zero friction. The earliest discussion of this more general problem is probably Birkhoff and de Boor in 1964. Over the next few years, several authors published algorithms for computing these ``nonlinear splines.'' Probably the most illuminating and accessible discussion of the early nonlinear spline theory is the 1971 report of Forsythe and Lee \cite{ForsytheLee}. A brief summary of their results follows: \begin{itemize} \item Each segment between knots is a MEC with $\lambda = 0.5$. \item Curvature is continuous across knots ($G^2$-continuity). \item Curvature is zero at endpoints (in the open case). \item The spline is extensional. \end{itemize} For each segment between knots, the elastica with $\lambda$ fixed has two remaining parameters, corresponding to the tangent angles at the endpoints. Recall that Figure~\ref{mecrange-fig} shows instances over the entire two-dimensional space in which such solutions exist, as well as the boundary of that solution space. In particular, in the case of symmetrical endpoint tangents, the curve is \emph{not} a circular arc, so the MEC spline does not have the roundness property. Forsythe and Lee found this unappealing, and propose adding an arc length penalty term to the functional, \begin{equation} E[\kappa(s)] = \int_0^l \kappa(s)^2 + c\ ds\:. \end{equation} As we now know, this change admits the solutions to the elastica equation other than $\lambda = 0.5$. Forsythe and Lee derive the value for $c$ so that the solution is a circular arc (corresponding to $\lambda = 0$), and speculate ``whether such an approach could be generalized is an open question.'' Answering their question is a primary focus of this chapter. \section{Properties of the MEC spline} \label{mec-props} \begin{figure*}[tbh] \begin{center} \includegraphics[scale=0.35]{figs/quadrant.pdf} \caption{\label{mec-roundness}MEC roundness failure.} \end{center} \end{figure*} The most important property the MEC spline is lacking is roundness. For three control points placed in an equilateral triangle (shown in Figure~\ref{mec-roundness}, with the spline drawn in a thick line, and the circle going through the control points thin), the containing radius for the spline is approximately $1.035$ times the radius of the circle going through the control points. With four points, this radius deviation decreases to about $1.009$, and asymptotically converges as $O(n^4)$ with the number of points. Another unpleasant property of the MEC spline is the failure to converge to a stable solution. This property is intimately related to the relatively small envelope enclosing the solution space -- for symmetric solutions the maximal endpoint tangent for $\lambda=0.5$ is $\pi/2$, and it is not much better for any of the non-symmetric solutions. \section{SI-MEC} \label{simec} Several researchers have tried to address these shortcomings in the MEC spline. One is the scale invariant minimum energy curve (or SI-MEC) proposed by Moreton and S\'equin \cite{Moreton93}. This spline is defined as the curve minimizing the SI-MEC functional \begin{equation} E[\kappa(s)] = l\int_0^l \kappa(s)^2 \ ds\: . \end{equation} The functional is termed ``scale invariant'' because its value is invariant as the entire curve is scaled up. By contrast, the MEC functional is proportional to the reciprocal of the scaling constant. The MEC functional can be seen as rewarding increases in the length of the curve, which accounts for the roundness failure -- the actual curve obtained is slightly longer than the circle, which accounts for the lower MEC functional. In the SI-MEC, the bias toward longer curves is removed, and, in fact, the spline is round when the control points are co-circular. The SI-MEC minimizes the MEC functional for a given length (a curve with a lower MEC energy at the same length would also obviously have a lower SI-MEC cost functional). Thus, an appealing physical interpretation is that of a mechanical spline with a bit of tension pulling at the endpoints, making the overall curve slightly shorter. Such a curve is generally \emph{not} two-parameter in the formulation above, and, in fact, all values of the elastica are possible (thus, it can be seen as a three-parameter spline). The SI-MEC has an unpleasant global coupling (equivalent to finding the tension to apply to the mechanical spline) that makes a global solver considerably slower than the corresponding pure MEC \cite{Moreton93}. The SI-MEC is extensional, which follows directly from its variational formulation as the curve minimizing an energy functional, such that it passes through all the control points. It shares $G^2$-continuity and similar locality properties with the MEC. % All of this text is really subsumed in Section \ref{kurgla1-sec}. %\section{Piecewise SI-MEC} % %Another practical approach to improving the MEC is to use segments %that each minimize the SI-MEC functional between any adjacent pair of %control points (given the tangent constraints at the endpoints), and %enforce $G^2$ continuity across the control points. A careful reading %of Mehlum's description \cite{Mehlum74} shows that this is the spline %approximated by his {\sc kurgla} 1 algorithm. % %The MEC, piecewise SI-MEC, and Euler spiral splines are all very %closely related, and are essentially identical in the small-angle %case. For larger bending angles at the control points, the difference %is in the way that curvature varies: % %\begin{itemize} % %\item Curvature in the MEC increases linearly with the distance from % the line tangent to the inflection point. % %\item Curvature in the piecewise SI-MEC increases linearly along the % chord. % %\item Curvature in the Euler spiral spline increases linearly along % the arclength. % %*** really needs a figure *** % %\end{itemize} % %Since any dependence on the chord breaks extensibility (adding a new %point changes the chords), the arclength is the most robust measure. %For any given set of control points, the Euler spiral spline will have %a slightly larger MEC functional, but almost all of that can be traced %to the fact that the scaling of the MEC functional rewards a longer %total curve length. % TODO: should probably reinstate cubic lagrange section \section{Cubic Lagrange (with length parametrization)} \label{cubic-lagrange-sec} The cubic Lagrange spline is defined as follows (see \cite[p. 23]{Kvasov00} for more detail), given a sequence of input data $(t_i, z_i)$, where $z_i$ can be interpreted as the vector $(x_i, y_i)$: \begin{equation} L_{i,3}(t) = \sum_{j = i - 1}^{i + 2} z_j \frac{\omega_{i-1,3}(t)}{(t - t_j)\omega'_{i- 1, 3}(t_j)},\ \ \ \omega_{i-1,3}(t) = \prod_{j=i-1}^{i + 2}(t - t_j) \end{equation} To obtain the Lagrange polynomial normalized by chord lengths, set successive $t_{i+1}$ so that $t_{i+1} - t_i = |z_{i + 1} - z_i|$. In other words, the parametrization is the same as the chord length. (Set $t_0 = 0$ for convenience, but the shape of the spline doesn't depend on it.) This spline is a reasonable approximation to MEC when the angles of the control polygon are small. It is also not round, as it is based on a polynomial approximation. It shares locality properties with the MEC as well. Further, the spline is not extensional, as adding additional points perturbs the chord length parametrization. Without chord length parametrization, the cubic Lagrange spline is extensional, but prone to wild excursions when the control points are not spaced evenly. The cubic Lagrange spline is sometimes used on its own, but its main interest here is as the basis of the Ikarus spline, discussed in the next section. \section{Ikarus (biarc)} \label{ikarus-sec} The spline used by Peter Karow's Ikarus system \cite{Karow87} also falls into the category of two-parameter splines. It was intended for font design, and was particularly well suited for interpolating between ``masters'' of different weights. The Ikarus spline uses two completely different mechanisms to achieve the two basic elements of the two parameter spline: the determination of tangents and the shapes of the curve segments between control points. To determine the tangents, first a cubic Lagrange polynomial (with normalization based on the chord lengths, as described in Section \ref{cubic-lagrange-sec}) is fit through the control points. Then the polynomial curve is discarded (but the tangents preserved), and, for each segment, a curve defined by biarcs is substituted. An arbitrary biarc has one additional degree of freedom, corresponding to the split point where the two arcs join, and Ikarus defines this somewhat arbitrarily to provide reasonable results. Even though the Lagrange polynomial fit can easily incorporate inflection points, the biarc primitive cannot, so inflection points must be explicitly marked in the input. % TODO: probably move the comparison to the fonts chapter. \begin{figure*}[tbh] \begin{center} \includegraphics[scale=1.25]{figs/karow-a.pdf} \caption{\label{ikarus-fig}Typical letter-shape using Ikarus.} \end{center} \end{figure*} The spline is not extensional, as adding points perturbs the chord length parametrization. Further, roundness is fairly decent, as the biarc becomes a circular arc when the endpoint tangents are symmetrical. Continuity is only $G^1$, but the biarc segments keep the spline from exhibiting extreme variations in curvature typical of purely polynomial-based splines. The spline is reported to work well when the control points are dense. Karow \cite{Karow91} recommends one control point for every 30 degrees of arc. A typical example is shown in Figure \ref{ikarus-fig} (reproduced from \cite{Karow91}). See also Figure \ref{ikarus-fig-compare} for a comparison with the splines of this thesis. \section{Euler's spiral} One particularly well-studied two-parameter spline is Euler's spiral, also known as the spiral of Cornu or the clothoid. More precisely, it is the spline formed by joining piecewise Euler's spiral segments with curvature ($G^2$) continuity at the knots. \begin{figure*}[tb] \begin{center} \includegraphics[scale=0.8]{figs/cornu.pdf} \caption{\label{euler-spiral-fig}Euler's spiral} \end{center} \end{figure*} Euler's spiral, plotted in Figure~\ref{euler-spiral-fig} over the range $[-5, 5]$, is most easily characterized by its intrinsic definition: curvature is linear in arc length. \begin{equation} \kappa(s) = \frac{s}{2}\: . \end{equation} Integrating the intrinsic equation yields this equation, known as the Fresnel integrals (historically, one each for the real and complex part): \begin{equation} \label{fresnel-int-eq} x(s) + iy(s) = \int_0^s e^{it^2} dt\: . \end{equation} This integral is also commonly expressed with a scale factor applied to the parameter. The resulting curve is similar; its size is $\sqrt{\frac{2}{\pi}}$ times that of the first formulation, with the velocity similarly scaled so that it also has unit velocity. The traditional notation for these integrals is $C(s)$ and $S(s)$, which evoke cosine and sine, respectively. \begin{equation} \label{fresnel-rescaled} C(s) + iS(s) = \int_0^s e^{i\pi t^2 / 2} dt\: . \end{equation} \subsection{Euler's spiral as a spline primitive} \begin{figure*} \begin{center} \includegraphics[scale=.7]{figs/clothmap} \caption{\label{clothmap}Euler's spiral spline primitive over its parameter space.} \end{center} \end{figure*} Euler's spiral is readily adapted for use as a two-parameter primitive for a spline. Given tangent angles at the endpoints, find parameters $t_0$ and $t_1$ from which to ``cut'' a segment from the spiral, so that the resulting segment meets the endpoint constraints (for now, assume that such parameters can be found; an efficient algorithm will be given in Section~\ref{solve-euler}). The behavior of this primitive is shown in Figure~\ref{clothmap}. Compare to Figure~\ref{mecrange-fig}, showing the corresponding behavior for the MEC spline. Note, among other things, that the Euler's spiral spline primitive is defined and well-behaved over a much wider range of endpoint tangent angles. \subsection{Variational formulation of Euler's spiral} The spline literature has generally been split into two camps: variational techniques, and the use of explicitly stated curves such as the Euler spiral. Ironically, Euler's spiral was born of the study of elastic springs just as was the elastica, but for the most part the literature does not examine Euler's spiral from a variational point of view. This section ties these two threads together, showing that the Euler spiral does indeed satisfy some fundamental variational properties. First, as noted by Kimia et al \cite{Kimia03}, the Euler spiral is among the solutions of the equation for the MVC functional, i.e. the curve that minimizes the MVC energy functional subject to various endpoint constraints: \begin{equation} E_{MVC}[\kappa(s)] = \int_0^l \Big(\frac{d\kappa}{ds}\Big)^2ds \end{equation} This result can be readily derived by treating the problem as an Euler variational problem expressed in terms of $\kappa$, i.e. $F(x, y, y') = y'^2$, with $s$ for $x$ and $\kappa$ for $y$ in the terms of Equation~\ref{var-statement}, as stated in Chapter~\ref{elastica-chapter}. The corresponding Euler--Lagrange equation is particularly simple: \begin{equation} \kappa'' = 0 \end{equation} The solution family is thus $\kappa = k_0 + k_1s$, which are simple similarity transformations of the basic Euler spiral. While the simplicity of this result is pleasing, it is unsatisfying for a variety of reasons. First, because the variational equation is written in terms of $\kappa$ rather than $\theta$, the boundary conditions are written in terms of curvature rather than tangent angle. Similarly, the additional terms corresponding to Equation~\ref{elastica-pos} representing the {\em positional} endpoint constraints are missing. Recall that without these constraints, the only solution to the MEC equation is a straight line. % todo - needs fixing So this result only tells us that the Euler spiral is the MVC-optimum curve satisfying {\em curvature} constraints on the endpoints, but with unconstrained endpoint positions and tangent angles. As we shall explore more deeply in Section~\ref{sec-eulerpoisson-mvc}, the solution to the MVC under other constraint configurations will in general not be an Euler spiral, a point not clearly made in the presentation by Kimia et al. A more fundamental problem is that the degree of continuity doesn't match. A spline made of piecewise Euler spiral segments has $G^2$-continuity, the same as a MEC spline, while the solution to the MVC functional with positional constraints for internal knots has $G^4$-continuity. So the Euler spiral is a reasonably good first-order approximation to the MEC functional, and is a special case in the solution space of the MVC functional, but might there be a functional for which it is actually \text{the} optimum? In a sense, this is the reverse of the usual variational problem, in which a function is sought that minimizes a given function. Here, we seek a functional which happens to be minimized by the given function, in this case the Euler spiral. We conjecture that there is indeed a functional: the maximum rate of curvature change over the entire arc length, \begin{equation} E_{\mbox{\scriptsize MAXVC}}[\kappa(s)] = \max\Big |\frac{d\kappa}{ds}\Big |\: . \end{equation} This functional is related to the MVC; while the MVC is the 2-norm of curvature variation, $E_{\mbox{\scriptsize MAXVC}}$ corresponds to the $\infty$-norm. \subsection{Euler spiral spline in use} How does the Euler spiral perform in the intended application domain of drawing glyph outlines? Experimentation yields encouraging results. One such example, a lowercase `c' traced from 14 point metal Linotype Estienne, is shown in Figure~\ref{euler-c-example}. Estienne is a distinguished book face designed by the eminent English printer George W. Jones, and released by Linotype in 1930 \cite[p. 133]{McGrew93}. It is not currently available in digital form, making it an attractive candidate for digitization. The `c' is a simple closed curve, reasonably smooth everywhere, but with regions of high curvature at both terminals. Below the glyph itself is a curvature plot, beginning at the knot marked by an arrow and continuing clockwise. The long flat section on the left is the inner contour, the sharp spike is the lower terminal, and the other long flat section (which is both longer and lower curvature) is the outer contour. Note that the curve has two inflection points, corresponding to zero crossings on the curvature plot and marked on the outline with short lines. \begin{figure*}[tb] \begin{center} \includegraphics[scale=0.8]{figs/c_g2.pdf} \caption{\label{euler-c-example}Closed Euler example.} \end{center} \end{figure*} \begin{figure*} \begin{center} \includegraphics[scale=0.8]{figs/g_g2.pdf} \caption{\label{euler-g-example}Complex Euler example.} \end{center} \end{figure*} A more complex example is shown in Figure~\ref{euler-g-example}, in this case a lowercase `g' from the same font. In this case, there are three closed curves; the outer shape and two ``holes.'' While the top hole is a simple smooth curve, the other curves contain both $G^2$-continuous smooth knots and ``corner points'', with only $G^0$-continuity. Such curves can be factored into sections consisting of the corner points at the endpoints and the smooth knots in the interior, then joined together. Note that sections with no smooth knots are straight lines (there is one at the top of the ``ear''), and sections with a single smooth knot are circular arcs (two of these make up the rest of the ear). More generally, each spline segment bordered by a corner point is a circular arc, with zero variation of curvature. Experience with drawing a significant number of glyphs is encouraging. The Euler spiral spline can represent a wide range of curves expressively and with an economy of points. Further, in an interactive editor, the correspondence between the input (the placement of knots and control points) seems considerably more intuitive than the standard B\'ezier curve editing techniques. \begin{figure*} \begin{center} \includegraphics[scale=0.8]{figs/pure_u.pdf} \caption{\label{pure-u}Difficulty with straight-to-curved joins.} \end{center} \end{figure*} The trickiest curves to draw using pure Euler's spiral splines are transitions between straight lines and curves, as typical in the shape of a ``U.'' The difficulty is illustrated in Figure~\ref{pure-u}. Essentially, the problem is that the segment adjoining the corner point tends to be a circular arc segment, rather than being constrained to be a straight line. It's possible, by careful interactive placement, to decrease this curvature so that it's almost a straight line, but then any changes to the curved segment will undo the effect of this careful placement. Similar problems occur if the points are determined by interpolation between different masters, or some other parametric variation. We shall return to the problem of straight-curve joins in Section \ref{sec-constraints}. \subsection{Existence and uniqueness of Euler spiral spline} \label{euler-existence-sec} One of the serious shortcomings of the MEC spline is lack of existence for all configurations of control points (see Section \ref{props-existence-sec} for a general discussion). An appealing feature of the Euler spiral spline is that it solutions exist in many cases when no such solution exists for the MEC spline. The obvious question is then, does a solution to the Euler spiral spline always exist, no matter what sequence of points are given? Also, is the solution unique? A partial answer is given in a 1982 paper by Stoer \cite{Stoer82}.\footnote{Although, the reader is warned, this paper contains numerous errors, including in the statement of the crucial Theorem 2.25.} Stoer considered a slightly weaker formulation of the Euler spiral spline: each segment is piecewise an Euler spiral segment, and there is $G^2$-continuity, but there are no additional constraints on the endpoints. Given these relaxed constraints, there is always a solution, in fact infinitely many. In other words, for any given sequence of control points, there exist infinitely many assignments of Euler spiral parameters such that the resulting segments have $G^2$-continuity. The proof is dependent on the following theorem: \begin{quote} \textbf{Stoer's theorem 2.25} (restated): For all points $P_0$ and $P_1$, tangent angles $\theta_0$, and curvatures $\kappa_0$, there exist countably many different Euler spiral segments connecting $P_0$ to $P_1$ such that the tangent at $P_0$ is $\theta_0$ and the curvature at $P_0$ is $\kappa_0$. \end{quote} \begin{figure*}[tbh] \begin{center} \includegraphics[scale=1.0]{figs/stoer_fig6.pdf} \caption{\label{stoer-fig6}Multiple windings for Euler spiral segment connecting two points (from \cite{Stoer82}).} \end{center} \end{figure*} Stoer's proof is based on the fact that an Euler spiral segment with gently varying curvature may wind around arbitrarily many times before reaching $P_1$. In the limit, the total winding number of the spiral segment increases by approximately $2\pi$ for each successive solution. Such multiple windings are shown in Figure \ref{stoer-fig6}, reproduced from \cite[p. 329]{Stoer82}. The result that there are infinitely many piecewise-Euler spiral, $G^2$-continuous interpolating splines follows readily from Stoer's theorem 2.25. Start at the first point, choosing arbitrary tangent and curvature, then choose one of the solutions guaranteed by the theorem, and repeat until the final point is reached. With arbitrary choices, such a procedure will tend to produce splines with excessive winding. Stoer proposed using the MEC energy to select a single ``best'' spline from the myriad alternatives. Stoer also gave an algorithm based on the standard band-diagonal Jacobian matrix, and claimed that it gave good results in general, but did not include a proof that the algorithm achieves a global optimum in all cases. In addition, using the global minimum of MEC energy will also have an effect on the curvature at the endpoints. Since minimizing MEC over all curves assigns zero curvature to endpoints (see Section \ref{mec-interp-sec}), and the Euler spline primitive is a fairly good approximation of the MEC primitive, at least in the small-angle assumption the curvature at the endpoints would be approximately zero. It is not currently known whether a solution always exists in the presence of additional endpoint constraints, such as zero curvature variation for the terminal segments. Obviously, with the methods of Stoer it is possible to apply such a constraint to one side, but it's not clear whether there, for all input sequences of points, an assignment of tangent for the left side such that the curvature variation is zero on the right side. The numerical techniques proposed later in this thesis (Section \ref{sec-global-solver} converge on a solution (and a solution with no excess windings, as well) for reasonable input sequences of control points, but can fail to converge when turning angles become excessive. \section{Hobby's spline} \label{hobby-sec} A significant interpolating spline, especially in font design, is Hobby's spline as implemented in Metafont \cite{Hobby85}. It is perhaps easiest to understand this spline as a very computationally efficient approximation to the Euler spiral spline of the previous section. The definition of the primitive segment, with endpoint tangent angles $\theta_0$ and $\theta_1$, is \begin{equation} \begin{array}{l} a = \sqrt{2}, \\ b = \frac{1}{16}, \\ c = (3 - \sqrt{5}) / 2, \\ \alpha = a(\sin\theta_0 - b\sin\theta_1)(\sin\theta_1 - b\sin\theta_0)(\cos\theta_0-\cos\theta_1), \\ \rho = \frac{2 + \alpha}{1 + (1-c)\cos\theta_0 + c\cos\theta_1}, \\ \sigma = \frac{2 - \alpha}{1 + (1-c)\cos\theta_1 + c\cos\theta_0}, \\ x_0, y_0 = 0, 0, \\ x_3, y_3 = 1, 0, \\ x_1, y_1 = \frac{\rho}{3\tau}\cos\theta_0, \frac{\rho}{3\tau}\sin\theta_0, \\ x_2, y_2 = 1 - \frac{\sigma}{3\tau}\cos\theta_1, \frac{\sigma}{3\tau}\sin\theta_1. \end{array} \end{equation} The $(x_i, y_i)$ are the coordinates for a standard cubic B\'ezier curve. The adjustable parameter $\tau$ corresponds closely to the ``tension'' parameter of B-splines, and its default value is $1$. In the Metafont sources for Computer Modern, the most common other value found is $0.9$, and that is only for a few glyphs, including lowercase `c' \cite[p. 311]{Knuth:1986:CMT}. \begin{figure*} \begin{center} \includegraphics[scale=.7]{figs/hobby} \caption{\label{hobby-fig}Hobby spline primitive over its parameter space.} \end{center} \end{figure*} The behavior of the Hobby spline primitive over its parameter space can be seen in Figure~\ref{hobby-fig} (see Figure~\ref{mecrange-fig} for comparison to the MEC). It is defined for all values of $\theta_0$ and $\theta_1$, but the figure only shows values up to $2.156$ radians (123.5 degrees). \begin{figure*} \begin{center} \includegraphics[scale=.7]{figs/hobbyk} \caption{\label{hobbyk-fig}Curvature plot of Hobby spline over its parameter space.} \end{center} \end{figure*} Similarly, the curvature plot is shown in Figure~\ref{hobbyk-fig}. For relatively small angles, its approximation to linear curvature is good, but sharp curvature peaks are apparent at large angles. While the Euler spiral spline is defined as the one which is a piecewise Euler spiral and $G^2$-continuous at the control points, the Hobby spline uses a slightly different criterion. Hobby introduces the concept of \emph{mock curvature}, which is the linear approximation (taking only the first-order term of the exact equation) of endpoint curvature as a function of the endpoint angles $\theta_0$ and $\theta_1$. The global solution to the spline is the assignment to the vector of tangent angles so that mock curvature is equal on either side of each knot. A very important consequence is that solving the global spline is a \emph{linear} problem. In fact, since each tangent angle affects two neighboring segments, and each segment in turn contributes to the mock curvature constraint at its two endpoints, the entire system of constraints can be represented as a tridiagonal linear equation, which is readily solvable in $O(n)$ using textbook techniques. Hobby also proves that the matrix is nonsingular over a reasonable range of values for $\tau$, including $\tau=1$. Thus, Hobby's is one of the few ``advanced'' splines for which there is a solution for \emph{all} configurations of input points. Evaluating the spline properties, we find that the Hobby spline does fairly well. For small angles, it closely approximates the Euler spiral spline. It is not round, but converges to roundness as $O(n^6)$ as opposed to the MEC, which is only $O(n^4)$. Similarly, the extensionality and continuity of curvature are only approximate, and only good at small angles. However, as noted above, it is an exceedingly robust spline. It is thus a good choice if computational resources are limited, robustness is key, and the input control points are closely enough spaced that angles are small. Another two-parameter curve family closely related to the Hobby spline is the primitive used in Potrace \cite{potrace03}. While Potrace is not an interpolating spline (rather, it is a tool for automatically converting bitmaps into vector curve outlines), its use of a primitive curve family is conceptually similar. Like the Hobby spline, the potrace primitive curve family is based on cubic B\'ezier curves (inherently four parameters), with mathematical equations to determine the additional two parameters. \section{Splines from fixed generating curves} \label{generator-curve-sec} The MEC has the property that all segments between control points can be cut from a single generating curve, the rectangular elastica (here, ``cut'' means selecting points on the generating curve, then performing the unique rotation, scaling and translation to make these endpoints match the corresponding control points). This property can be derived from the equilibrium-of-forces formulation of the elastica, and the fact that the constraints at the control points exert zero tension, but these facts are not intuitively obvious. Similarly, in the Euler spiral spline, segments between control points are cut from the Euler spiral (``cut'' may also include a mirror flip, because this curve lacks a mirror symmetry). What do splines cut from a single generating curve have in common? Why do so few other splines have this property? Might there be some additional flexibility that can be gained by choosing segments from a curve family rather than a fixed generating curve? The key to answering these questions is extensionality. In fact, as demonstrated in Section \ref{extensional-equivalence}, the class of two-parameter extensional splines is exactly equal to the class of two-parameter splines cut from a generating curve. Other properties, such as roundness, can then be derived from properties of the generating curve. For example, for the spline to be round, the curve must tend to a circular shape in the limit. More precisely, $\lim_{s \rightarrow \infty} \kappa'(s) / \kappa(s)^2 = 0$. The Euler spiral meets this condition because $\kappa$ tends to infinity, while $\kappa'$ is fixed. Another possibility would be a curve tending to fixed curvature in the asymptote, in which case $\kappa'$ would tend to $0$. The MEC, by contrast, clearly does not have this property. The envelope of endpoint chord angles (as plotted in Figure~\ref{mecrange-fig} for the MEC) also has an effect. A small envelope yields failure to exist. A generating curve without an inflection (such as a parabola) excludes all antisymmetric endpoint angle configurations from this envelope, even for tiny angles. \subsection{Log-aesthetic curve splines} \label{sec-aesthetic} A very promising family of candidates for generator curves is the \emph{aesthetic curve,} also known as the \emph{log-aesthetic curve} \cite{Miura05}. These curves are defined as having a straight line when $\kappa'/\kappa$ is plotted against $\kappa$ on a 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 the parameter that distinguishes the members of this family. An intuitive motivation for the aesthetic curve is that the eye is not as sensitive to absolute variation of curvature as it is to relative variation. In areas of high curvature, high variation of curvature is more easily tolerated; but in low-curvature areas, even small variations in curvature are visible. \begin{figure*}[tbh] \begin{center} \includegraphics[scale=0.6]{figs/aesthetic.pdf} \caption{\label{aesthetic-examples-two}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, but it's possible to generalize the formula to $\kappa=\mbox{sign}(s)|s|^\alpha$ to admit a continuous range of exponents. A family of such curves (used to interpolate a zigzag sequence of control points) is shown in Figure \ref{aesthetic-examples-two}. As described in Section \ref{empirical-fairness-sec}, an empirical user study establishes that MEC energy is not an accurate predictor of perceived fairness. MEC energy is minimized at $\alpha=0.9$, so if MEC energy were an accurate predictor of fairness, that would have been the preferred value. Since the mean preferred value was $\alpha=1.78$, that hypothesis is refuted. % note: hand-cropped to remove whitespace \begin{figure*}[tbh] \begin{center} \includegraphics[scale=0.6]{figs/locality.pdf} \caption{\label{aesthetic-locality}Perturbation fall-off rate as a function of aesthetic curve exponent.} \end{center} \end{figure*} The exponent of the aesthetic curve used as the generator curve in a spline also has a profound effect on the locality of the resulting spline. In general, the weaker the curvature variation near the inflection point of the generator curve, the better the locality. The aesthetic curve family varies from very steep to very shallow curvature variation across its parameter space. The falloff factor for a single perturbed point, a quantitative measurement of locality, is plotted against the exponent of the aesthetic curve in Figure \ref{aesthetic-locality}. For $\alpha=1$, which represents the Euler spiral, the amplitude of the ripple diminishes by 0.268 from one crest to the next 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, which yields a value of $1/(2+\sqrt{3})$ for the Euler spiral. Note also that the MEC spline has the same locality properties as the Euler spiral spline. For the user-preferred exponent of 1.78, the falloff factor is 0.173, noticeably smaller and thus better. It is possible to achieve even better locality at the expense of higher curvature variation, if that is desired. \section{Piecewise SI-MEC splines, or Kurgla 1} \label{kurgla1-sec} The Autokon system of Mehlum \cite{Mehlum74} was inspired by the goal of simulating a real, mechanical spline, but its {\sc kurgla} 1 algorithm actually implemented something a bit different, with both advantages and disadvantages with respect to the MEC it was intended to mimic. Mehlum based his design on the fact that the curvature of an elastica is linear in distance from the line of action. His solver approximated the integration of this intrinsic equation as a sequence of circular arcs, the curvature of each determined by the distance from the line of action. As we've seen, the general elastica has three degrees of freedom; two for the position and angle of the line of action with respect to the control point chord, and one for the amplitude of the curvature variation. Note that inflections occur at the line of action. In this formulation, choosing all these parameters to minimize the total bending energy is a tricky global optimization problem, and {\sc kurgla} 1 did not attempt it. In particular, it nailed down the \emph{angle} of the line of action, choosing it to be perpendicular to the chord. In this way, the parameter space was reduced from three to two, and the problem became much more tractable. In particular, the curve segments were determined by the tangents at the endpoints, and the remaining global problem of choosing tangents for $G^2$-continuity yields to simple Newton-style solution. As shown in Section \ref{simec-section}, an elastica segment with the line of action perpendicular to the chord is the one minimizing the SI-MEC energy for the angle constraints at those endpoints. Thus, the {\sc kurgla} 1 algorithm effectively computes a piecewise SI-MEC. One consequence is that {\sc kurgla} 1 is round, unlike the pure MEC, since the SI-MEC describes a circular arc in the case of symmetrical endpoint angle constraints. Another consequence is considerably better robustness than the pure MEC, because the envelope of parameter space is approximately twice as large. However, the price paid for these improvements is loss of extensionality; when a new on-curve point is added, it generally changes the chords, and thus the lines of action for the resulting elastica sections. Thus, though it is based on the elastica, and has some desirable properties, {\sc kurgla} 1 is neither a true energy minimizing spline like the MEC, nor does its extensionality and robustness compare well to the Euler spiral spline. Indeed, Mehlum was aware of these limitations, and his subsequent {\sc kurgla} 2 algorithm is the earliest known implementation of the Euler spiral spline.\footnote{Mehlum wrote to George Forsythe on July 9, 1971, mentioning ``Fresnel integral splines'' as recent work. The work was published in 1974 \cite{Mehlum74}.} \begin{figure*}[thb] \begin{center} \includegraphics[scale=0.8]{figs/mec_euler_compare.pdf} \caption{\label{mec-euler-compare}MEC, SI-MEC, and Euler spiral compared.} \end{center} \end{figure*} The MEC, SI-MEC, and Euler spiral are closely related. One way to visualize this relation is to consider the gradient of curvature. In an Euler spiral, curvature increases linearly along the arc length of the curves. In a SI-MEC defined by two endpoint tangents, curvature increases linearly along the chord between the endpoints. And in a pure MEC, curvature increases along the line tangent to the inflection point. Figure \ref{mec-euler-compare} shows these gradients of curvature visually -- along each of the curves, tick marks meter the rate of change of curvature, and the tick mark is angled so that the rate of curvature change is constant between parallel lines. This figure also shows that the SI-MEC and Euler spiral are visually very similar. \section{Circle splines} \label{cspline-sec} \begin{figure*}[thb] \begin{center} \includegraphics[scale=0.6]{figs/cspline.pdf} \caption{\label{cspline-fig}Circle spline extensionality failure.} \end{center} \end{figure*} Interpolating splines have a tradeoff between extensionality and locality. The two-parameter splines described above favor extensionality. It is possible to make different choices, and favor locality instead. An excellent example is the ``circle spline'' of S\'equin, Lee, and Yin \cite{DBLP:journals/cad/SequinLY05}. In the circle spline, the tangent angle at each control point is chosen as the tangent of the circle going through the control point and its two neighbors. Each segment is then constructed using a blending of these circles from the tangents at the endpoints. Thus, moving a control point only affects four segments -- two on either side. The construction of the primitive curves is robust and smooth. In fact, the construction guarantees zero $\kappa'$ at the endpoints, and that the curvature is identical to that of the circle used to determine tangents, so the resulting spline has $G^3$-continuity. Unfortunately, even though the spline has good locality and $G^3$-continuity, it is not particularly smooth for all inputs, and adding additional on-curve control points can cause serious deviations from extensionality, in many cases adding inflections. Figure \ref{cspline-fig} clearly shows the lack of extensionality; the two paths differ only by the addition of the central point in the right-hand figure. \section{Summary} This chapter described an important class of interpolating splines, those with a primitive curve described by a two-dimensional parameter space. A great many splines in the literature fall into this category, notably the Minimum Energy Curve. A central result of this work is that any two-parameter, extensional spline is defined in terms of a fixed generating curve. These properties hold across a large family of desirable splines, and makes the choice of an optimum spline a much simpler problem. Choosing a most preferred generating curve can be done empirically. By contrast, the variational approach would require developing an accurate model of the perception of curve fairness. Empirical testing establishes that the most common such metric, bending energy, does not coincide accurately with user preference. \newcommand{\rateexc}{$+++$} \newcommand{\ratevg}{$++$} \newcommand{\rategood}{$+$} \newcommand{\ratefair}{$-$} \newcommand{\ratepoor}{$--$} \newcommand{\ratebad}{$---$} \newcommand{\sml}{\footnotesize} \vspace{5mm} \begin{table}[ht] \label{twoparam-table} %\[ \begin{tabular}{ll|lcccc} % \sml in every cell is inelegant, but gets the job done. \sml \textrm{Curve type} & \sml \textrm{Tangents} & \sml \textrm{Continuity} & \sml \textrm{Extensionality} & \sml \textrm{Roundness} & \sml \textrm{Robustness} & \sml \textrm{Locality} \\ \hline \sml MEC & \sml $G^2$ & \sml $G^2$ & \sml \rateexc & \sml \ratepoor & \sml \ratepoor & \sml \rategood \\ \sml Euler spiral & \sml $G^2$ & \sml $G^2$ & \sml \rateexc & \sml \rateexc & \sml \ratevg & \sml \rategood \\ \sml log-aesthetic & \sml $G^2$ & \sml $G^2$ & \sml \rateexc & \sml \rateexc & \sml \ratefair & \sml \ratevg \\ \sml Hobby & \sml $\approx G^2$ & \sml $\approx G^2$ & \sml \ratefair & \sml \ratefair & \sml \rateexc & \sml \rategood \\ \sml Biarc (Ikarus) & \sml Lagrange & \sml $G^1$ & \sml \ratepoor & \sml \rateexc & \sml \ratevg & \sml \rategood \\ \sml {\sc kurgla} 1 & \sml $G^2$ & \sml $G^2$ & \sml \ratefair & \sml \rateexc & \sml \rategood & \sml \rategood \\ \sml Circle & \sml local & \sml $G^3$ & \sml \ratebad & \sml \rateexc & \sml \rateexc & \sml \rateexc \end{tabular} %\] \caption{Comparison of properties of two-parameter splines.} \end{table} Table \ref{twoparam-table} summarizes the properties of several splines in this two-parameter family. All of these are known and appear in the literature. \begin{itemize} \item MEC is the interpolating spline minimizing the total bending energy. Each segment between control points is a piece of a rectangular elastica, and the tangents are chosen so that $G^2$ continuity is preserved across each control point. (Section \ref{mec-interp-sec}) \item Euler spiral is the interpolating spline for which each segment between control points is a section of an Euler spiral, i.e. curvature is linear in arc length. Like the MEC, the tangents are chosen for $G^2$-continuity. (Section \ref{euler-interp-sec}) \item log-aesthetic is the two-parameter extensible spline based on log-aesthetic curves with an exponent near $\alpha=2$. (Section \ref{sec-aesthetic}) \item Ikarus (Section \ref{ikarus-sec}). \item Hobby is a piecewise cubic spline developed for the Metafont system. It is best understood as a polynomial approximation to the Euler spiral spline, with better robustness but lower performance on other metrics such as smoothness and extensionality \cite{Hobby85} (Section \ref{hobby-sec}). \item {\sc kurgla} 1 (Section \ref{kurgla1-sec}). \item Circle spline (Section \ref{cspline-sec}). \end{itemize} For the basic interpolating spline problem, two-parameter extensible splines seem likely to be the best possible choice. From this family, while the MEC (based on the rectangular elastica) is the original inspiration for virtually the entire field of splines, the Euler spiral spline is superior and has excellent all-around properties, and is especially well-suited for interactive use due to its stability. The elastica and Euler spiral are particularly important and beautiful curves. In addition, they have a fascinating and intertwined history, explored in detail in the next two chapters.