网格模型上的离散测地线  

A survey on the computing of geodesic distances on meshes

作　　者：赵俊莉[1,2] 辛士庆[3] 刘永进[4] 王醒策[1] 武仲科[1] 周明全[1] 贺英 

机构地区：[1]北京师范大学信息科学与技术学院,北京100875 [2]青岛大学软件技术学院,山东266071 [3]宁波大学信息科学与工程学院,浙江315211 [4]清华大学计算机科学与技术系,北京100084 [5]School of Computer Engineering, Nanyang Technological University

出　　处：《中国科学：信息科学》2015年第3期313-335,共23页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:61170170;61170203;61271366;61322206)资助项目

摘　　要：测地线是微分几何中的重要概念,用于描述曲面上两点之间的最短曲线,相当于平面上两点之间的直线段,它在计算机图形学、图像处理、计算几何、计算机视觉等学科中有着广泛的应用.自20世纪80年代以来,关于离散测地线已有广泛研究,众多学者提出了许多切实可行的算法.本文将在介绍光滑曲面上的测地线和离散网格上测地线概念的基础上,对网格模型上的离散最短测地线和最直测地线的定义、性质及相关算法进行归纳总结,重点讨论网格模型上离散最短测地线的相关算法,包括完整网格和有缺陷网格上最短测地线的精确算法和逼近算法,对各类算法进行深入研究,详细论述每个算法的基本思想与实现方法,从多个角度分析每个算法的优缺点,并对他们各自的时间复杂度、空间复杂度及适用范围等进行对比,最后对离散测地线的相关研究进行展望,有利于后续对测地线算法的深入研究.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 1980 s, 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.

关 键 词：测地线 测地距离 最短测地线 最直测地线 网格 算法 

分 类 号：O186.1[理学—数学]