《Computational Geometry》lecnotes20 Dr. K. H. Ko Prof. N. M. Patrikalakis

13472J/1.128J/2158J/16940J COMPUTATIONAL GEOMETRY Lecture 20 Pro R: Ki. Pat ricalakis Copyright( 2003 Massachusetts Institute of Technology Contents 20 Advanced topics in differential geometry eslcs 20.1.1 Motivation 20.1.2 Definition 20.1.3 Governing equations 20.1.4 Two-point boundary value problem 20.1.5 Example 20.2 Developable surface 20.2.1 Motivation 22223580002 20.2.2 Definition 20.2.3 Developable surface in terms of Bezier surface 20.2.4 Development of developable surface(flattening) 20.3 Umbilics 20.3.1 Motivation 20.3.2 Definition 20.3.3 Computation of umbilical points 20.3. 4 Classification 20.3.5 Characteristic lines 20.4 Parabolic, ridge and sub-parabolic points 20.4.2 Focal surfaces 20.4.3 Parabolic points 22 20.4. 4 Ridge points 0.4.5 Sub-parabolic points Bibliography Reading in the Textbook Geodesics: Chapter 10, pp. 265-291 Umbilics: Chapter 9, pp. 231-264

13.472J/1.128J/2.158J/16.940J COMPUTATIONAL GEOMETRY Lecture 20 Dr. K. H. Ko Prof. N. M. Patrikalakis Copyright ≤c 2003 Massachusetts Institute of Technology Contents 20 Advanced topics in differential geometry 2 20.1 Geodesics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 20.1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 20.1.2 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 20.1.3 Governing equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 20.1.4 Two-point boundary value problem . . . . . . . . . . . . . . . . . . . . . . . . . 5 20.1.5 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 20.2 Developable surface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 20.2.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 20.2.2 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 20.2.3 Developable surface in terms of B´ezier surface . . . . . . . . . . . . . . . . . . . 12 20.2.4 Development of developable surface (flattening) . . . . . . . . . . . . . . . . . . 13 20.3 Umbilics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 20.3.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 20.3.2 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 20.3.3 Computation of umbilical points . . . . . . . . . . . . . . . . . . . . . . . . . . 15 20.3.4 Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 20.3.5 Characteristic lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 20.4 Parabolic, ridge and sub-parabolic points . . . . . . . . . . . . . . . . . . . . . . . . . 21 20.4.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 20.4.2 Focal surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 20.4.3 Parabolic points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 20.4.4 Ridge points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 20.4.5 Sub-parabolic points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Bibliography 25 Reading in the Textbook • Geodesics : Chapter 10, pp.265 - 291 • Umbilics : Chapter 9, pp.231 - 264 1

Lecture 20 Advanced topics in differential geometry 20.1 Geodesics In this section we study the computation of shortest path between two points on free-form surfaces [14, 11 20.1.1 Motivation ship design robot motion planning · terrain navigation installation of underwater cable 20.1.2 Definition . t: Unit tangent vector of C at P n: Unit normal vector of c at p N: Unit surface normal vector of s at P u: Unit vector perpendicular to t in the tangent plane defined by n x t

Lecture 20 Advanced topics in differential geometry 20.1 Geodesics In this section we study the computation of shortest path between two points on free-form surfaces [14, 11]. 20.1.1 Motivation • ship design • robot motion planning • terrain navigation • installation of underwater cable 20.1.2 Definition • t: Unit tangent vector of C at P • n: Unit normal vector of C at P • N: Unit surface normal vector of S at P • u: Unit vector perpendicular to t in the tangent plane defined by N × t. 2

Figure 20.1: Definition of geodesic curvature We can decompose the curvature vector k of C into n component kn, which is called normal curvature vector, and u component ka, which is called geodesic curvature vector k=kn+ko=-knn+kou 20.1 Here kn and Kg are the normal and geodesic curvatures, respectively and defined as follows (20.3) · Consequently, ds Geodesic paths are sometimes defined as shortest path between points on a surface however this is not always a satisfactory definition Definition: Geodesics are curves of zero geodesic curvature 24 20.1.3 Governing equations The unit tangent vector of the curve C on the surface r is given by dr(u(s), v(s)) du ds Hence using chain rules ds =ruu)+2rw'ds ds +Iw(ds)+ruds2krd-u dt dudu du

t N u n k kg kn S P C Figure 20.1: Definition of geodesic curvature. • We can decompose the curvature vector k of C into N component kn, which is called normal curvature vector, and u component kg, which is called geodesic curvature vector k = kn + kg = −ρnN + ρgu (20.1) Here ρn and ρg are the normal and geodesic curvatures, respectively and defined as follows: ρn = −k N· (20.2) ρg = k u· (20.3) • Consequently, dt ρg = ds · (N × t) (20.4) • Geodesic paths are sometimes defined as shortest path between points on a surface, however this is not always a satisfactory definition. Definition: Geodesics are curves of zero geodesic curvature [24]. 20.1.3 Governing equations • The unit tangent vector of the curve C on the surface r is given by dr(u(s), v(s)) du dv t = = ru + rv (20.5) ds ds ds • Hence using chain rules ⎤ ⎦2 ⎤ ⎦2 dt du du dv dv d2u d2v = ruu + 2ruv + rvv + ru + rv (20.6) ds ds ds ds ds ds2 ds2 3

Consider that the surface normal n has the direction of normal of the geodesic line tn Since kn= g, equation(20. 7)can be rewritten as dt dt r,= (20.8) By substituting equation(20.6)into equations(20.8) we obtain du d 2u ds d +(re·ra ds2+ha2=0(20.9) dudu rua‘r ds )+2(rwu ro)ds ds +(roo r s)+ 0(20.10 By eliminating d! from equation(20.)using equation(2010), and eliminating d! from equation(20.10)using equation(20.9)and employing the Christoffel symbols, we obtain du du ds2 dsds (20.11) ds2 +Ii 12 dsds ds (20.12) Where Tik(i, 3, k= 1, 2)are the Christoffel symbols defined as follows TI GE-BC),l≈2EF1-EE+FE GE -2FF, +FE 2(E EG.-FE 2(EG-F2) 20.13) 2G,-GGu+ FG EGn-2FF+FG 2(EG-F2) 2(EG-F2) These two second order differential equations can be rewritten as a system of four first order differential equations 6 20.14 d q 中一山一 (20.16) (20.17

• Consider that the surface normal N has the direction of normal of the geodesic line ±n n r· u = 0, n r· v = 0. (20.7) dt • Since kn = ds , equation (20.7) can be rewritten as dt dt ru = 0, rv = 0 (20.8) ds · ds · • By substituting equation (20.6) into equations (20.8) we obtain ⎤ ⎦2 ⎤ ⎦2 du du dv dv d2u d2v (ruu · ru) + 2(ruv · ru) + (rvv · ru) + E + F = 0 (20.9) ds ds ds ⎤ ⎦2 du du dv ds ds2 ds2 ⎤ ⎦2 dv d2u d2v (ruu · rv) + 2(ruv · rv) + (rvv · rv) + F + G = 0 (20.10) ds ds ds ds ds2 ds2 v By eliminating d2 from equation (20.9) using equation (20.10), and eliminating d2u • ds2 ds2 from equation (20.10) using equation (20.9) and employing the Christoffel symbols, we obtain ⎤ ⎤ ⎦2 d2u du⎦2 du dv dv + �1 + 2�1 + �1 = 0 (20.11) ds2 11 22 ds ⎤ d2v du⎦2 12 ds ds ds ⎤ ⎦2 du dv dv + �2 + 2�2 + �2 = 0 (20.12) ds2 11 22 ds 12 ds ds ds • jk Where � (i, j, k = 1, 2) are the Christoffel symbols defined as follows: i �1 GEu − 2FFu + FEv �2 2EFu − EEv + FEu 11 = 11 = � 2(EG − F2) , 2(EG − F2) 1 GEv − FGu �2 EGu − FEv 12 = 12 = � 2(EG − F2) , 2(EG − F2) (20.13) 1 2GFv − GGu + FGv �2 EGv − 2FFv + FGu 22 = 22 = 2(EG − F2) , 2(EG − F2) • These two second order differential equations can be rewritten as a system of four first order differential equations [6]. du = p (20.14) ds dv = q (20.15) ds dp 2 2 = −�1 − 2�1 11p 12pq − �1 (20.16) 22q ds dq 2 2 = −�2 − 2�2 11p 12pq − �2 (20.17) 22q ds 4

Euler Lagrange Equations(Calculus of Variations We can also find this result by means of the general rules of the calculus of variations We want to minimize d f(u, v, i)du (20.18) f(u,u,d)=VE+2Fi+Gi2, Udu 20.1 This leads to the condition af d af 0 (20.20 from which we can derive the same differential equation for geodesics 20. 1.4 Two-point boundary value problem We can solve a system of four first order ordinary differential equations(20. 14)to(20.17) Initial-value problem(IVP), where all four boundary conditions are given at one point, or as Boundary-value problem(BVP), where four boundary conditions are specified at two distinct points The first order differential equation for a boundary value problem can be written in vector form as where, ds=g(s, y), y(A)=(uA, UA, PA, qA), y(B)=(uB,UB, PB, qB)? (20.21) where pA, PB, gA and gB are unknowns (u,0,P,q) g=(P,q,-Ip2-212p-r292,-I1p2-212p-r22)2(20.23) There are two commonly used approaches to the numerical solution of BVP Shooting method: easy to implement but unstable 2. Relaxation method: more sophisticated but stable · Shooting method We assume values at s= A, which are not given as boundary conditions at s= A and compute the solution of the resulting iVp to s=B

• Euler Lagrange Equations (Calculus of Variations) We can also find this result by means of the general rules of the calculus of variations. We want to minimize � b � b I = ds = f(u, v, v˙)du (20.18) a a where dv 2 f(u, v, v˙) = � E + 2F v˙ + Gv˙ , v˙ = (20.19) du This leads to the condition πf d πf (20.20) πv − du πv˙ = 0 from which we can derive the same differential equation for geodesics. 20.1.4 Two-point boundary value problem • We can solve a system of four first order ordinary differential equations (20.14) to (20.17) as – Initial-value problem (IVP), where all four boundary conditions are given at one point, or as – Boundary-value problem (BVP), where four boundary conditions are specified at two distinct points. • The first order differential equation for a boundary value problem can be written in vector form as: dy = g(s, y), y(A) = (uA, vA, pA, qA) T , y(B) = (uB, vB, pB, qB) T (20.21) ds where pA, pB, qA and qB are unknowns, y = (u, v, p, q) T (20.22) 2 12pq − �1 2 2 22q2 ) T g = (p, q, −�1 − 2�1 22q , −�2 − 2�2 12pq − �2 (20.23) 11p 11p • There are two commonly used approaches to the numerical solution of BVP. 1. Shooting method: easy to implement but unstable. 2. Relaxation method: more sophisticated but stable. • Shooting method – We assume values at s = A, which are not given as boundary conditions at s = A and compute the solution of the resulting IVP to s = B. 5