Computing Straightest Geodesics On Triangle Mesh

Geodesics generalize the concept of straight lines on curved surfaces and manifolds in differential geometry. Computing geodesics on triangle mesh is widely used in computer graphics and pattern recognition research and in the area of engineering design and manufacture. With the more and more applications of discrete models, both theory and practice demand accurate and efficient algorithms computing geodesics on triangle mesh.Geodesics on smooth surface have many good geometric properties and there are equivalent partial differential equations and analytical methods solving it. On discrete model,it is not able to keep all the geometric properties and different definitions arise. Now, most research and applications focus on shortest geodesics and three different solutions dominate among them. The first is the discrete geodesic problem [3] which carefully defines and proves this problem. This continuous Dijkastra method they present is to unfold the triangle sequence geodesic passing by into a plane. Moreover, it is proved with approximate ratio 1 and the time complexity is from O(n2 logn) to O(nlogn) base on different implement strategies and data structures. The second class of methods adopts a front propagation way updating geodesic distance by solving geodesic differential equation. It can attain better approximate ratio but the time complexity will vary from O(nlogn) to O(n) for the special accuracy level. The third solution constructs new subdivision weighted graph on current Dijkastra path and incident triangles and compute a new Dijkastra path until a given precision. Obviously, this method costs too much time and space. Among the three solutions, the most widely used method FMM (Fast Marching Method) belongs to the second one.Straightest geodesics are with intact differential definition and theory system, but related study and application in graphics is very few now. The existing algorithms include equivalent left and right curve angle by definition, normal section line method and tangent projection etc. But all their precisions are limit to one-order truncation error, and make severe accumulate error on discrete models. We present two practical linear methods computing straightest geodesics starting from a given point and going along a special tangent direction on triangle mesh. Our methods do not need extra processing for obtuse triangles and have unit computing on triangle vertex and edge. The point is they make better accuracy and efficiency both on convex and non-convex models and to a great extent cue the severe accumulate error of existing methods.The main contributions of this paper are:1) Studying systematically the differential geometry definition of geodesics and two main discrete geodesics shortest and straightest geodesics on mesh. Summering properties and behavior of geodesics on surface and discussing the difference, relationship and solutions of them.2) Giving an intact descript of normal section line method and explain the effectiveness and computational error. We proof that normal section line method has one-order truncation error and is equivalent to geodesic Euler method both in theory and experiment results.3) We present the tangent and normal adjusting method computing straightest geodesics on triangle mesh. It attains fourth-order truncation error even on coarse mesh and thus largely settle the accumulate error problem of existing method. Moreover, we have analyzed its robust with normal disturbance and step length and concluded that it is applicable with estimated normal and step length.