Fast Wavefront Propagation (FWP) for Computing Exact Geodesic Distances on Meshes
Fast Wavefront Propagation (FWP) for Computing Exact Geodesic Distances on Meshes
复制标题
用于计算网格上精确测地距离的快速波前传播 (FWP)
DOI：
10.1109/tvcg.2015.2407404
复制
发表时间：
2015-07
影响因子：
5.2
通讯作者：
He Ying
中科院分区：
文献类型：
--
作者：
Xu Chunxu;Wang Tuanfeng Y;Liu Yong Jin;Liu Ligang;He Ying
计算三角形网格上的测地距离是计算几何和计算机图形学中的一个基本问题。迄今为止，已经提出了两类著名的算法：Mitchell-Mount-Papadimitriou (MMP) 算法和 Chen-Han (CH) 算法。尽管如果数值计算精确，这些算法可以计算精确的测地距离，但它们的计算成本很高，这降低了它们对于大规模模型和/或时间关键型应用的有用性。在本文中，我们提出了快速波前传播（FWP）框架来提高 MMP 和 CH 算法的性能。与每次迭代时仅传播单个窗口（本地编码测地线信息的数据结构）的原始算法不同，我们的方法使用桶数据结构组织窗口，以便它可以同时处理大量窗口，而不会影响波前质量。由于其宏观性质，FWP 方法对网格三角测量的敏感度低于 MMP 和 CH 算法。我们在各种大规模现实世界模型上评估基于 FWP 的 MMP 和 CH 算法。计算结果表明我们的方法可以将速度提高3-10倍。
Computing geodesic distances on triangle meshes is a fundamental problem in computational geometry and computer graphics. To date, two notable classes of algorithms, the Mitchell-Mount-Papadimitriou (MMP) algorithm and the Chen-Han (CH) algorithm, have been proposed. Although these algorithms can compute exact geodesic distances if numerical computation is exact, they are computationally expensive, which diminishes their usefulness for large-scale models and/or time-critical applications. In this paper, we propose the fast wavefront propagation (FWP) framework for improving the performance of both the MMP and CH algorithms. Unlike the original algorithms that propagate only a single window (a data structure locally encodes geodesic information) at each iteration, our method organizes windows with a bucket data structure so that it can process a large number of windows simultaneously without compromising wavefront quality. Thanks to its macro nature, the FWP method is less sensitive to mesh triangulation than the MMP and CH algorithms. We evaluate our FWP-based MMP and CH algorithms on a wide range of large-scale real-world models. Computational results show that our method can improve the speed by a factor of 3-10.
登录
查看更多内容
DOI：
10.1145/73393.73407
发表时间：
1988-01
期刊：
--
影响因子：
--
作者：
C. Yap
通讯作者：
C. Yap
DOI：
10.1016/j.comgeo.2011.05.006
发表时间：
2011-11
期刊：
Comput. Geom.
影响因子：
--
作者：
P. Bose;Anil Maheshwari;Chang Shu;Stefanie Wuhrer
通讯作者：
P. Bose;Anil Maheshwari;Chang Shu;Stefanie Wuhrer
DOI：
10.1109/tvcg.2011.119
发表时间：
2012-06
影响因子：
5.2
作者：
Shiqing Xin;Ying He;Chi-Wing Fu
通讯作者：
Shiqing Xin;Ying He;Chi-Wing Fu
DOI：
10.1016/j.cad.2011.08.027
发表时间：
2011-11
期刊：
Comput. Aided Des.
影响因子：
--
作者：
Shiqing Xin;Xiang Ying;Ying He
通讯作者：
Shiqing Xin;Xiang Ying;Ying He
DOI：
10.1145/2407746.2407769
发表时间：
2012-11
期刊：
SIGGRAPH Asia 2012 Technical Briefs
影响因子：
--
作者：
Shiqing Xin;D. T. P. Quynh;Xiang Ying;Ying He
通讯作者：
Shiqing Xin;D. T. P. Quynh;Xiang Ying;Ying He