A survey on computing geodesic distances on meshes（网格模型上的离散测地线综述）
Published in Scientia Sinica Informationis, 2015
Abstract: Geodesic, the shortest path between two points on a three-dimensional surface, is analogous to a straight line between two points on a plane, and is an important concept in differential geometry. It is utilized extensively in computer graphics, image processing, computational geometry, computer vision, and other fields. Geodesic algorithms have also been studied extensively since the 1980s, with many researchers proposing various practical algorithms. This paper summarizes the definition, property, and algorithms associated with the shortest geodesic and straightest geodesic on a mesh after introducing the concept of geodesic on smooth and polyhedral surfaces. The main algorithms discussed are discrete geodesic algorithms on polyhedral surfaces, including the exact shortest geodesic algorithms and the approximate shortest geodesic algorithms on integral meshes and defective meshes. Various algorithms are also analyzed in depth, with the basic underlying idea and method of realization of each algorithm discussed in detail, and the merits and demerits of each algorithm compared from different perspectives. Further, their time complexity, space complexity, and fields of application are also compared. Finally, the prospects for discrete geodesic research are discussed with a view towards deeper study of geodesic.
Recommended citation: JunLi Zhao, ShiQing Xin, Yong-Jin Liu, XingCe Wang, ZhongKe Wu, MingQuan Zhou, Ying He (2015) A survey on computing geodesic distances on meshes（网格模型上的离散测地线综述）. Scientia Sinica Informationis, Vol. 45, No. 3, pp.313-335, in Chinese, 2015.