三角网格的测地计算？ [英] Geodesic computation on triangle meshes?

问题描述

我试图找出三角形表面上两点之间的距离（测地距离）。它看起来像一个基本的操作，并不是微不足道。所以我想知道是否有任何图书馆这样做？我的google fo失败，所以我会非常感谢任何指针。

（我知道CGAL，scipy.spatial，但我在文档中找不到任何东西，让我知道，如果我错过了那里的东西）

解决方案

有很多实现计算三角网格上的测地距离。有些是近似值，有些是准确的。

1.快速行进法。这种方法是近似的，实际上平均误差低于1％。你可以参考Gabriel Peyre在MATLAB中实现快速行进方法。
http://www.mathworks.com/matlabcentral/fileexchange / 6110-toolbox-fast-marching

2. MMP方法由[1]在[2]中实现。此方法是精确的，代码位于 https://code.google.com/p/geodesic/ 。与Ante的评论相同。缺点是当网格是larege时，MMP方法将消耗大量的内存，O（n ^ 2），n是顶点的数量。




3. CH方法[3]提出并在[4]中改进和实现。这种方法是精确的，消耗比MMP方法更少的内存。代码位于 https://sites.google.com/site/xinshiqing/knowledge-share




4. [5]中提出的加热方法。一种实现方式位于 https://github.com/dgpdec/course 中。
   此方法是近似的并需要预处理过程。

[1] Joseph SB Mitchell，David M. Mount和Christos H. Papadimitriou。离散测地问题。 SIAM J.Comput。 16，4（1987年8月），647-668。

[2] Vitaly Surazhsky，Tatiana Surazhsky，Danil Kirsanov，Steven Gortler，Hugues Hoppe。在网格上快速精确和近似测地线。 ACM Trans。图形（SIGGRAPH），24（3），2005。

[3] Chen，J.and Han，Y.1990。多面体上的最短路径。 InSCG'90：Proceedings of the Six annual symposium on Computational geometry。 ACM出版社，纽约，纽约，美国，360。[4]石庆新，王国金。改进陈和汉的离散测地问题算法。 ACM Trans。图形。 28，4，第104条（2009年9月），8页。因此，本文提出了一种基于热流计算距离的新方法[J]。计算机工程与计算机工程。 ACM Transactions on Graphics（TOG），2013，32（5）：152。

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.

(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.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

2. 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. 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

4. 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, and Christos H. Papadimitriou. 1987. The discrete geodesic problem. SIAM J. Comput. 16, 4 (August 1987), 647-668.

[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. 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] 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. Geodesics in heat: a new approach to computing distance based on heat flow[J]. ACM Transactions on Graphics (TOG), 2013, 32(5): 152.

这篇关于三角网格的测地计算？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！