You can find geodesic paths in triangle meshes by just flipping edges
You can find geodesic paths in triangle meshes by just flipping edges
复制标题
DOI：
10.1145/3414685.3417839
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Nicholas Sharp;Keenan Crane
中科院分区：
文献类型：
--
作者：
Nicholas Sharp;Keenan Crane
本文介绍了一种在多面体表面计算测地线的新方法——其基本思想是迭代地进行边翻转，这与经典的德劳内翻转算法的思路相同。这个过程还会生成一个符合输出测地线的三角剖分，这对于几何处理和数值模拟中的任务立即有用。更准确地说，我们的FlipOut算法将给定的边序列转换为局部最短测地线，同时避免自相交（形式上：它在相同的同痕类中找到一条测地线）。该算法保证在有限次操作后终止；实际运行时间约为几毫秒，即使对于包含数百万个三角形的网格也是如此。同样的方法很容易应用于简单路径之外的曲线，包括闭合回路、曲线网络和多重覆盖曲线。我们探讨了该方法如何促进诸如拉直切割和分割边界、计算测地线贝塞尔曲线、将约束德劳内三角剖分（CDT）的概念扩展到曲面以及为偏微分方程（PDEs）提供准确边界条件等任务。对诸如Thingi10k等具有挑战性的数据集的评估表明，该方法既稳健又高效，即使对于低质量的三角剖分也是如此。
This paper introduces a new approach to computing geodesics on polyhedral surfaces---the basic idea is to iteratively perform edge flips, in the same spirit as the classic Delaunay flip algorithm. This process also produces a triangulation conforming to the output geodesics, which is immediately useful for tasks in geometry processing and numerical simulation. More precisely, our FlipOut algorithm transforms a given sequence of edges into a locally shortest geodesic while avoiding self-crossings (formally: it finds a geodesic in the same isotopy class). The algorithm is guaranteed to terminate in a finite number of operations; practical runtimes are on the order of a few milliseconds, even for meshes with millions of triangles. The same approach is easily applied to curves beyond simple paths, including closed loops, curve networks, and multiply-covered curves. We explore how the method facilitates tasks such as straightening cuts and segmentation boundaries, computing geodesic Bézier curves, extending the notion of constrained Delaunay triangulations (CDT) to curved surfaces, and providing accurate boundary conditions for partial differential equations (PDEs). Evaluation on challenging datasets such as Thingi10k indicates that the method is both robust and efficient, even for low-quality triangulations.