Approximate geodesics on smooth surfaces of arbitrary topology

This paper introduces a new approach for computing large number of approximate geodesic paths from a given point to all directions on a 3D model (mesh or surface) of arbitrary topology. The basic idea is to unfold the 3D model into a °at surface so that the geodesic from a given point in a given direction can be obtained simply by drawing a straight line from the given point along the given direction on the unfolded surface. Hence our method does not require setting up any linear systems, nor any expensive matrix computation, but is simply done by iteratively extending the geodesic path along the given direction until the geodesic path reaches a certain length. The iterative process proceeds with a linear complexity. Therefore the new approach is very fast and can be used for meshes with large number of vertices. The smooth surface representation scheme used in this paper is Catmull-Clark subdivision surfaces, but the same idea can be applied to other subdivision schemes as well. Some test results obtained using this method are included. They show the effectiveness of our approach.