Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

From Spiral to Spline: Optimal Techniques in Interactive Curve Design

Raphael Linus Levien

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2009-162
December 3, 2009

http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-162.pdf

A basic technique for designing curved shapes in the plane is interpolating splines. The designer inputs a sequence of control points, and the computer fits a smooth curve that goes through these points. The literature of interpolating splines is rich, much of it based on the mathematical idealization of a thin elastic strip constrained to pass through the points. Until now there is little consensus on which, if any, of these splines is ideal. This thesis explores the properties of an ideal interpolating spline. The most important property is fairness, a property often in tension with locality, meaning that perturbations to the input points do not affect sections of the curve at a distance. The idealized elastic strip has two serious problems. A sequence of co-circular input points results in a curve deviating from a circular arc. For some other inputs, no solution (with finite extent) exists at all. The idealized elastic strip has two properties worth preserving. First, any ideal spline must be extensional, meaning that the insertion of a new point on the curve shouldn’t change its shape. Second, curve segments between any two adjacent control points are drawn from a two-parameter family (and this propety is closely related to good locality properties). A central result of this thesis is that any spline sharing these properties also has the property that all segments between two control points are cut from a single, fixed generating curve. Thus, the problem of choosing an ideal spline is reduced to that of choosing the ideal generating curve. The Euler spiral has excellent all-around properties, and, for some applications, a log-aesthetic curve may be even better. Shapes in applications such as font outlines contain extra features such as corners and transitions between straight lines and smooth curves. Attaching additional constraints to control points expresses these features, and, carefully applied, give the designer a richer palette of curve types. The splines presented in this thesis are entirely practical as well, especially for designing fonts. Sophisticated new numerical techniques compute the splines at interactive speeds, as well as convert to optimized cubic B´ezier representation.

Advisor: Carlo H. Séquin


BibTeX citation:

@phdthesis{Levien:EECS-2009-162,
    Author = {Levien, Raphael Linus},
    Title = {From Spiral to Spline: Optimal Techniques in Interactive Curve Design},
    School = {EECS Department, University of California, Berkeley},
    Year = {2009},
    Month = {Dec},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-162.html},
    Number = {UCB/EECS-2009-162},
    Abstract = {A basic technique for designing curved shapes in the plane is interpolating splines. The designer inputs a sequence of control points, and the computer fits a smooth curve that goes through these points. The literature of interpolating splines is rich, much of it based on the mathematical idealization of a thin elastic strip constrained to pass through the points. Until now there is little consensus on which, if any, of these splines is ideal. This thesis explores the properties of an ideal interpolating spline. The most important property is fairness, a property often in tension with locality, meaning that perturbations to the input points do not affect sections of the curve at a distance. The idealized elastic strip has two serious problems. A sequence of co-circular input points results in a curve deviating from a circular arc. For some other inputs, no solution (with finite extent) exists at all.

The idealized elastic strip has two properties worth preserving. First, any ideal spline must be extensional, meaning that the insertion of a new point on the curve shouldn’t change its shape. Second, curve segments between any two adjacent control points are drawn from a two-parameter family (and this propety is closely related to good locality properties). A central result of this
thesis is that any spline sharing these properties also has the property that all segments between two control points are cut from a single, fixed generating curve. Thus, the problem of choosing an ideal spline is reduced to that of choosing the ideal generating curve. The Euler spiral has excellent all-around properties, and, for some applications, a log-aesthetic curve may be even better.

Shapes in applications such as font outlines contain extra features such as corners and transitions between straight lines and smooth curves. Attaching additional constraints to control points expresses these features, and, carefully applied, give the designer a richer palette of curve types.

The splines presented in this thesis are entirely practical as well, especially for designing fonts. Sophisticated new numerical techniques compute the splines at interactive speeds, as well as convert to optimized cubic B´ezier representation.}
}

EndNote citation:

%0 Thesis
%A Levien, Raphael Linus
%T From Spiral to Spline: Optimal Techniques in Interactive Curve Design
%I EECS Department, University of California, Berkeley
%D 2009
%8 December 3
%@ UCB/EECS-2009-162
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-162.html
%F Levien:EECS-2009-162