计算3D网格表面上两点之间最短路径的算法

Question

我正在寻找一种算法来计算以下内容:

我有:

1. 3D三角网格.三角形不一定位于一个平面中.两个相邻三角形的范数向量之间的角度小于90度.

2. 两点.这两个点位于三角形网格的边缘或网格的三角形内.

我需要计算折线,它代表网格上两点之间的最短路径.

这样做最简单和/或最有效的策略是什么？

Answer 1

就目前情况而言，您的问题没有明确定义；根据将线段“投影”到网格上的方向，可以有许多解决方案。

选择投影方向后，将网格展平到垂直于投影方向的平面上。此时，您的网格是二维边（线段）的集合；只需确定每条边与目标线段的交点（如果有）。

编辑：

更新后的问题现已明确定义。由于我对原始问题（上面）的回答已被标记为已接受，这大概意味着下面评论中给出的信息实际上是更新问题真正“接受”的信息。我总结一下：

• 谷歌搜索“3d 网格上的最短距离”会出现一些相关信息，例如三角网格上的最短路径近似
• 另请参阅：https ://stackoverflow.com/a/10389377/294949 -- danh