三角形网格的测地线计算? [英] Geodesic computation on triangle meshes?
问题描述
我试图找出三角表面上两点之间的距离(测地线距离).它看起来像一个基本的操作，并不是微不足道的.所以我想知道是否有任何图书馆可以做到这一点?我的谷歌 fo 失败了，所以我将不胜感激任何指针.
I am trying to find the distance between two points on a triangulated surface (geodesic distance). It looks like a basic operation and is not trivial. So I am wondering if there are any libraries that do this? My google fo failed, so I would greatly appreciate any pointers.
(我知道 CGAL、scipy.spatial，但我在文档中找不到任何内容，如果我错过了那里的内容，请告诉我)
(I am aware of CGAL, scipy.spatial, but I couldn't find anything in the docs, let me know if I missed something there)
推荐答案
三角网格上计算测地线距离的实现有很多.有些是近似的，有些是精确的.
There are many implementation for computing geodesic distance on triangle mesh. Some are approximate and some are exact.
1.快速行进法.这种方法是近似的，实际上平均误差低于 1%.可以参考 Gabriel Peyre 在 matlab 中实现快进法.http://www.mathworks.com/matlabcentral/fileexchange/6110-toolbox-fast-marching
1.Fast Marching method. This method is approximate and in practice the average error is below 1%. You can refer to Gabriel Peyre's implementation of fast marching method in matlab. http://www.mathworks.com/matlabcentral/fileexchange/6110-toolbox-fast-marching
MMP 方法由 [1] 提出并在 [2] 中实现.这种方法是准确的，代码在 https://code.google.com/p/geodesic/ 中.与安特的评论相同.一个缺点是当网格较大时，MMP方法会消耗大量内存，O(n^2)，n为顶点数.
MMP method proposed by [1] and implemented in [2]. This method is exact and the code is in https://code.google.com/p/geodesic/ . Same as the comment by Ante. A disadvantage is that when the mesh is larege, MMP method will consume a lot of memory, O(n^2), n is the number of vertices.
[3] 中提出并在 [4] 中改进和实施的 CH 方法.这种方法比 MMP 方法精确且消耗更少的内存.代码在https://sites.google.com/site/xinshiqing/knowledge-share
CH method proposed in [3] and improved and implemented in [4]. This method is exact and consume less memory than MMP method. The code is in https://sites.google.com/site/xinshiqing/knowledge-share
[5]中提出的加热方法.一种实现是在 https://github.com/dgpdec/course这种方法是近似的，需要一个预处理过程.它比 Fast Marching 方法更快.
Heat method proposed in [5]. One implementation is in https://github.com/dgpdec/course This method is approximated and require a preprocessing process. It's faster than Fast Marching method.
[1] Joseph S. B. Mitchell、David M. Mount 和 Christos H. Papadimitriou.1987. 离散测地线问题.暹罗学家计算机.16, 4(1987 年 8 月)，647-668.
[1] Joseph S. B. Mitchell, David M. Mount, and Christos H. Papadimitriou. 1987. The discrete geodesic problem. SIAM J. Comput. 16, 4 (August 1987), 647-668.
[2] 维塔利·苏拉日斯基、塔蒂亚娜·苏拉日斯基、丹尼尔·基尔萨诺夫、史蒂文·戈特勒、休格斯·霍普.网格上的快速精确和近似测地线.ACM 翻译.图形 (SIGGRAPH)，24(3)，2005.
[2] Vitaly Surazhsky, Tatiana Surazhsky, Danil Kirsanov, Steven Gortler, Hugues Hoppe. Fast exact and approximate geodesics on meshes. ACM Trans. Graphics (SIGGRAPH), 24(3), 2005.
[3] Chen, J. 和 Han, Y.1990.多面体上的最短路径.InSCG '90:第六届计算几何年度研讨会论文集.ACM 出版社，纽约，纽约，美国，360{369
[3] Chen, J. and Han, Y.1990. Shortest paths on a polyhedron. InSCG '90: Proceedings of the sixth annual symposium on Computational geometry. ACM Press, New York, NY, USA, 360{369
[4] 辛世清、王国金.2009. 改进 Chen 和 Han 的离散测地线问题算法.ACM 翻译.图形.28, 4, 第 104 条(2009 年 9 月)，8 页.
[4] Shi-Qing Xin and Guo-Jin Wang. 2009. Improving Chen and Han's algorithm on the discrete geodesic problem. ACM Trans. Graph. 28, 4, Article 104 (September 2009), 8 pages.
[5] Crane K, Weischedel C, Wardetzky M. 热测地线:一种基于热流计算距离的新方法[J].ACM 图形交易 (TOG)，2013，32(5):152.
[5] Crane K, Weischedel C, Wardetzky M. Geodesics in heat: a new approach to computing distance based on heat flow[J]. ACM Transactions on Graphics (TOG), 2013, 32(5): 152.
这篇关于三角形网格的测地线计算?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
