Ma Shuai, Wang Wencheng, Hou Fei
IEEE Trans Vis Comput Graph. 2025 Sep;31(9):5655-5667. doi: 10.1109/TVCG.2024.3466242.
Fast detection of exact point-to-point geodesic paths on meshes is still challenging with existing methods. For this, we present a method to reduce the region to be investigated on the mesh for efficiency. It is by our observation that a mesh and its simplified one are very alike so that the geodesic path between two defined points on the mesh and the geodesic path between their corresponding two points on the simplified mesh are very near to each other in the 3D Euclidean space. Thus, with the geodesic path on the simplified mesh, we can generate a region on the original mesh that contains the geodesic path on the mesh, called the search region, by which existing methods can reduce the search scope in detecting geodesic paths, and so obtaining acceleration. We demonstrate the rationale behind our proposed method. Experimental results show that we can promote existing methods well, e.g., the global exact method VTP (vertex-oriented triangle propagation) can be sped up by even over 200 times when handling large meshes. Our search region can also speed up path initialization using the Dijkstra algorithm to promote local methods, e.g., obtaining an acceleration of at least two times in our tests.
利用现有方法在网格上快速检测精确的点对点测地线仍然具有挑战性。为此，我们提出了一种方法，为提高效率减少网格上需要研究的区域。据我们观察，一个网格与其简化后的网格非常相似，以至于网格上两个定义点之间的测地线与简化网格上其相应两点之间的测地线在三维欧几里得空间中非常接近。因此，利用简化网格上的测地线，我们可以在原始网格上生成一个包含网格上测地线的区域，称为搜索区域，通过它现有方法可以在检测测地线时缩小搜索范围，从而获得加速效果。我们阐述了所提方法背后的原理。实验结果表明，我们能很好地改进现有方法，例如，在处理大型网格时，全局精确方法VTP（面向顶点的三角形传播）甚至可以加速200倍以上。我们的搜索区域还可以加快使用迪杰斯特拉算法进行路径初始化的速度，以改进局部方法，例如，在我们的测试中至少获得两倍的加速。
