next up previous contents index
Next: 10.2 Geodesic equation Up: 10. Geodesics Previous: 10. Geodesics   Contents   Index


10.1 Introduction

Computation of shortest paths on free-form surfaces is an important problem in geometric design of ship hulls, robot motion planning, computation of medial axis transforms of trimmed surface patches, terrain navigation, NC machining, and cable installation on the sea floor. The history of geodesic lines begins with a study by Johann Bernoulli, who solved the problem of the shortest distance between two points on a convex surface in 1697, according to Struik [412]. He showed that the osculating plane of the geodesic line must always be perpendicular to the tangent plane. The equation of geodesics for implicit surfaces was first obtained by Euler (1732). His attention to the problem was due to Johann Bernoulli, probably through the aid of his nephew Daniel, who was at St. Petersburg with Euler [411]. Bliss [28] obtained the geodesic lines on the anchor ring, which has a torus shape, analytically. Munchmeyer and Haw [281] applied geodesic curves to geometric design of ship hulls, namely to find out the precise layout of the seams and butts on a ship hull. Beck et al. [22] performed both initial-value integration and boundary-value integration (based on shooting method) of geodesic paths, using the fourth order Runge-Kutta method on a bicubic spline surface. Patrikalakis and Bardis [296] computed geodesic offsets of curves on rational B-spline surfaces using the initial-value integration of geodesics normal to an initial progenitor curve on the surface. One application of such offsets is automated construction of linkage curves for free-form procedural blending surfaces. Sneyd and Peskin [398] investigated the computation of geodesic paths on a generalized cylinder based on an initial value problem using a second order Runge-Kutta method. Their work was motivated by constructing the great vessels of the heart out of geodesic fibers. Kimmel et al. [200] presented a numerical method for finding the shortest path on surfaces by calculating the propagation of an equal geodesic-distance contour from a point or a source region on the surface. The algorithm works on a rectangular grid using finite difference approximations. Maekawa [247] and Robinson and Armstrong [347] computed the geodesics by discretizing the governing differential equations using a finite difference approximation on a mesh of points, which reduces the problem to a set of nonlinear equations. The set of nonlinear equations can be solved by quadratically convergent Newton iteration method, which starts with an initial guess and improves the solution iteratively. This technique is referred as, direct method, relaxation method or finite difference method. The shortest path problem is also very active among the robot motion planning and terrain navigation communities, however they usually represent the surface as a polyhedral surface and solve the problem using techniques from the field of computational geometry [269].

A geodesic path is sometimes defined as the shortest path between two points on a surface; however this is not always a satisfactory definition. In this book we follow Struik [412] and define geodesics as below:

\begin{definition} Geodesics are curves of zero geodesic curvature\index{geodesic!curvature}. \end{definition}

In other words, the osculating planes of a geodesic curve on a surface contain the surface normal. From this definition we can easily see that the geodesic between two points on a sphere is a great circle. But there are two arcs of a great circle between two such points, and only one of them provides the shortest distance, except when the two points are the end points of a diameter of the sphere. This example indicates that there may exist more than one geodesics between two points on a surface.

Let $ Q(t)$ describe a moving point on a surface where $ t$ may be viewed as a time parameter belonging to an interval beginning with $ t_0$ , and $ Q[t_0, t_1]$ describe the path between points $ Q(t_0)$ and $ Q(t_1)$ . If the point $ Q(t)$ moves away from the starting point $ Q(t_0)$ along a geodesic path $ C$ , i.e. curve with zero geodesic curvature, then it may occur that $ Q(t)$ will reach a point $ Q(t_R)$ such that for every $ \varepsilon > 0$ the path $ Q[t_0,t_R + \varepsilon]$ is no longer the shortest surface path joining the points $ Q(t_0)$ and $ Q(t_R + \varepsilon)$ . In other words, $ Q(t_R)$ was the last time point such that the geodesic path $ Q[t_0,t_R]$ is the shortest surface path joining the points $ Q(t_0)$ and $ Q(t_R)$ . This point $ Q(t_R)$ is called conjugate to $ Q(t_0)$ on the geodesic $ C$ (see also [449]). The location, where each extension of a shortest geodesic fails to define a shortest path from $ Q(t_0)$ , belongs to the cut locus of the point $ Q(t_0)$ on the surface. This geometric locus and its generalizations (being important for considerations on shortest paths and geodesic distance) have been studied in [447,449].

next up previous contents index
Next: 10.2 Geodesic equation Up: 10. Geodesics Previous: 10. Geodesics   Contents   Index
December 2009