Nội dung

From Spiral to Spline: Optimal Techniques in Interactive Curve Design by Raphael Linus Levien A dissertation submitted in partial satisfaction of the requirements for the degree of Doctor of Philosophy in Engineering–Electrical Engineering and Computer Sciences in the GRADUATE DIVISION of the UNIVERSITY OF CALIFORNIA, BERKELEY Committee in charge: Professor Carlo Séquin, Chair Professor Jonathan Shewchuk Professor Jasper Rine Fall 2009 From Spiral to Spline: Optimal Techniques in Interactive Curve Design Copyright © 2009 by Raphael Linus Levien Abstract From Spiral to Spline: Optimal Techniques in Interactive Curve Design by Raphael Linus Levien Doctor of Philosophy in Engineering–Electrical Engineering and Computer Sciences University of California, Berkeley Professor Carlo Séquin, Chair 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ézier representation. Professor Carlo Séquin Dissertation Committee Chair 1 To my father. i Contents Contents ii List of Figures vii List of Tables xi Acknowledgements xii 1 Introduction 1 2 Properties of splines 6 Fairness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1.1 Empirical testing of fairness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Continuity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Roundness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.4 Extensionality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.5 Existence and uniqueness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.6 Locality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.7 Transformational invariance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.8 Counting parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.9 Monotone curvature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1 2.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3 The Elastica 16 3.1 Statement of the elastica problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2 Variational study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2.1 The Euler–Lagrange equation . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2.2 Application of the Euler–Lagrange equation to the elastica . . . . . . . . . . 18 ii 3.3 A family of solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.4 Equilibrium of moments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.5 Pendulum analogy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.6 Equilibrium of forces: Finite element approach . . . . . . . . . . . . . . . . . . . . . 25 3.7 Solutions with length and endpoint constraints . . . . . . . . . . . . . . . . . . . . . 29 3.8 Elastica with general constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.9 Angle constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.10 Elastica as an interpolating spline . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.11 SI-MEC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.12 Real splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4 Two-parameter splines 42 4.1 Extensional two-parameter splines have a generating curve . . . . . . . . . . . . . . . 43 4.2 Properties of the MEC spline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.3 SI-MEC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4.4 Cubic Lagrange (with length parametrization) . . . . . . . . . . . . . . . . . . . . . . 47 4.5 Ikarus (biarc) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 4.6 Euler’s spiral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.6.1 Euler’s spiral as a spline primitive . . . . . . . . . . . . . . . . . . . . . . . . 51 4.6.2 Variational formulation of Euler’s spiral . . . . . . . . . . . . . . . . . . . . . 51 4.6.3 Euler spiral spline in use . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.6.4 Existence and uniqueness of Euler spiral spline . . . . . . . . . . . . . . . . . 53 4.7 Hobby’s spline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.8 Splines from fixed generating curves . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.8.1 4.9 Log-aesthetic curve splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 Piecewise SI-MEC splines, or Kurgla 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.10 Circle splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.11 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5 History of the elastica 67 5.1 Jordanus de Nemore – 13th century . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5.2 Galileo sets the stage – 1638 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5.3 Hooke’s law of the spring – 1678 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.4 James Bernoulli poses the elastica problem – 1691 . . . . . . . . . . . . . . . . . . . 70 iii 5.5 James Bernoulli partially solves it – 1692 . . . . . . . . . . . . . . . . . . . . . . . . 71 5.6 James Bernoulli publishes the first solution – 1694 . . . . . . . . . . . . . . . . . . . 73 5.7 Daniel Bernoulli proposes variational techniques – 1742 . . . . . . . . . . . . . . . . 77 5.8 Euler’s analysis – 1744 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 5.8.1 5.9 Moments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 Elliptic integrals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 5.10 Laplace on the capillary – 1807 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 5.11 Kirchhoff’s kinetic analogy – 1859 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 5.12 Closed form solution: Jacobi elliptic functions – 1880 . . . . . . . . . . . . . . . . . . 89 5.12.1 Inflectional solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 5.12.2 Non-inflectional solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 5.13 Max Born – 1906 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 5.14 Influence on modern spline theory – 1946 to 1965 . . . . . . . . . . . . . . . . . . . . 92 5.15 Numerical techniques – 1958 through today . . . . . . . . . . . . . . . . . . . . . . . 93 6 History of the Euler spiral 95 6.1 James Bernoulli poses a problem of elasticity – 1694 . . . . . . . . . . . . . . . . . . 95 6.2 Euler characterizes the curve – 1744 . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 6.3 Euler finds the limits – 1781 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 6.4 Relation to the elastica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 6.5 Fresnel on diffraction problems – 1818 . . . . . . . . . . . . . . . . . . . . . . . . . . 103 6.6 Talbot’s railway transition spiral – 1890 . . . . . . . . . . . . . . . . . . . . . . . . . 106 6.7 Mathematical properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 6.8 Use as an interpolating spline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 6.9 Efficient computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 7 Four-parameter curves 110 7.1 Why four parameters? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 7.2 Minimum Variation Curve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 7.2.1 Euler–Poisson equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 7.2.2 Euler–Poisson solution of MVC . . . . . . . . . . . . . . . . . . . . . . . . . . 115 7.3 Polynomial spiral spline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 7.4 Generalized constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 iv 8 Numerical toolbox 8.1 122 Numerical integration of polynomial spirals . . . . . . . . . . . . . . . . . . . . . . . 123 8.1.1 Polynomial approximation of the integral . . . . . . . . . . . . . . . . . . . . 124 8.1.2 Higher-order polynomial approximations . . . . . . . . . . . . . . . . . . . . . 125 8.1.3 Hybrid approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 8.2 Determining Euler spiral parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 8.3 Global constraint solver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 8.4 8.3.1 Two-parameter solver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 8.3.2 Four-parameter solver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 2-D Lookup table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 9 Converting to Bézier curves 135 9.1 Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 9.2 Error metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 9.3 Simple conversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 9.4 Equal arc length, equal arm length solution . . . . . . . . . . . . . . . . . . . . . . . 139 9.5 Fully optimized solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 9.6 Global optimum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 9.6.1 Hybrid error metric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 9.6.2 Simple subdivision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 9.6.3 Smarter subdivision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 9.6.4 Alternative optimum algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 147 10 Applications in font design 149 11 Space curves 160 11.1 Curves in space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 11.2 Minimum energy curve in space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 11.2.1 MEC as spline in 3-space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 11.3 Mehlum’s spiral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 11.4 Log-aesthetic space curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 11.5 Surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 12 Conclusion 167 v Bibliography 171 vi List of Figures 1.1 A mechanical spline. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Rectangular elastica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Euler spiral. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4 Conversion to optimized Bézier curves. . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1 Test instrument for fairness user study. . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Survey results for aesthetic curve preference. . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Continuity 6= fairness. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.4 MEC roundness failure. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.5 Circle spline extensionality failure. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.6 Nonexistence of solution to MEC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.7 Uniqueness failure in Euler spiral spline. . . . . . . . . . . . . . . . . . . . . . . . . 12 2.8 G2 spline has better locality than G4 . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.9 Attneave’s curvature experiment [5]. . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.1 The family of elastica solutions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.2 Curvature plots for the family of elastica solutions. . . . . . . . . . . . . . . . . . . 22 3.3 Equilibrium of moments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.4 An oscillating pendulum. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.5 Examples of pendulum analogy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.6 Finite element approximation of elastica as chain of struts and pivots. . . . . . . . . 27 3.7 Forces on a single strut. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.8 Forces on a single pivot. 3.9 Forces on a single pivot point in a chain. . . . . . . . . . . . . . . . . . . . . . . . . 28 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.10 Values of λ for varying chord lengths. . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.11 Multiplicity of solutions for same tangent constraints. . . . . . . . . . . . . . . . . . 31 vii