Efficiently Computing Exact Geodesic Loops within Finite Steps
Efficiently Computing Exact Geodesic Loops within Finite Steps
复制标题
DOI：
10.1109/tvcg.2011.119
复制
发表时间：
2012-06
影响因子：
5.2
通讯作者：
Shiqing Xin;Ying He;Chi-Wing Fu
中科院分区：
文献类型：
--
作者：
Shiqing Xin;Ying He;Chi-Wing Fu
闭测地线，或测地线环，是研究微分拓扑和微分几何的关键。光滑曲面上闭测地线的存在性及其性质在数学界已得到了广泛的研究，但在多边形曲面上如何计算闭测地线的研究进展相对较少。现有的算法大多将网格简单地视为一个图，因此生成的环仅限于网格边，而网格边与实际的测地线相距甚远。本文首次证明了封闭面序列上的测地线环的存在唯一性，并给出了一个在有限步内将给定网格上的初始封闭路径迭代演化为精确测地线环的有效算法.我们提出的算法只需要O（k）的空间复杂度和O（k）的时间复杂度（实验），其中m是由初始循环和结果测地线循环所包围的区域中的顶点数，k是进化循环通过的边序列中的平均边数。与现有的在预定义阈值内计算近似测地线环的测地线曲率流方法相比，我们的方法是精确的，并且可以直接应用于三角形网格，而不需要用数值求解器求解任何微分方程;它可以以交互速度运行，例如，对于具有大约50K个顶点的网格，在毫秒的数量级上，并且因此显著优于现有算法。实际上，我们的算法可以运行在交互式的速度，甚至更大的网格。除了输入网格的复杂性之外，几何形状也可以影响演化步骤的数量，即，演出我们激励我们的算法与交互式形状分割的例子在本文后面。
Closed geodesics, or geodesic loops, are crucial to the study of differential topology and differential geometry. Although the existence and properties of closed geodesics on smooth surfaces have been widely studied in mathematics community, relatively little progress has been made on how to compute them on polygonal surfaces. Most existing algorithms simply consider the mesh as a graph and so the resultant loops are restricted only on mesh edges, which are far from the actual geodesics. This paper is the first to prove the existence and uniqueness of geodesic loop restricted on a closed face sequence; it contributes also with an efficient algorithm to iteratively evolve an initial closed path on a given mesh into an exact geodesic loop within finite steps. Our proposed algorithm takes only an O(k) space complexity and an O(mk) time complexity (experimentally), where m is the number of vertices in the region bounded by the initial loop and the resultant geodesic loop, and k is the average number of edges in the edge sequences that the evolving loop passes through. In contrast to the existing geodesic curvature flow methods which compute an approximate geodesic loop within a predefined threshold, our method is exact and can apply directly to triangular meshes without needing to solve any differential equation with a numerical solver; it can run at interactive speed, e.g., in the order of milliseconds, for a mesh with around 50K vertices, and hence, significantly outperforms existing algorithms. Actually, our algorithm could run at interactive speed even for larger meshes. Besides the complexity of the input mesh, the geometric shape could also affect the number of evolving steps, i.e., the performance. We motivate our algorithm with an interactive shape segmentation example shown later in the paper.