计算 3D 网格表面两点之间最短路径的算法
Algorithm to calculate the shortest path between two points on the surface of a 3D mesh
我正在寻找一种算法来计算以下内容：
我有：
3D 三角形网格。三角形不一定位于一个平面内。相邻两个三角形的范数向量夹角小于90度
两点。这两个点位于三角形网格的边缘或网格的三角形内。
我需要计算代表网格上两点之间最短路径的折线。
最简单的 and/or 最有效的策略是什么？
目前看来，你的问题没有明确定义；根据 "project" 线段到网格上的方向，可以有很多解决方案。
选择投影方向后，将网格展平到垂直于投影方向的平面上。此时，您的网格是二维边（线段）的集合；只需确定每条边与目标线段的交点（如果有的话）。
编辑:
更新后的问题现已明确定义。由于我对原始问题（上方）的回答已被标记为已接受，大概这意味着下面评论中提供的信息实际上是更新问题的 "accepted"。我总结一下：
- google 搜索 "shortest distance on 3d mesh" 会找到一些相关信息，例如 Shortest Path Approximation on Triangulated Meshes
- 另见： -- danh
由于您的 start/end 点可能位于网格上的任何位置（不限于顶点），我猜您正在搜索测地线最短路径（不是 Dikstra 最短路径后边）。 geometry-central中实现了一个很好的算法：http://geometry-central.net/surface/algorithms/flip_geodesics/
算法在论文"You Can Find Geodesic Paths in Triangle Meshes by Just Flipping Edges"中有描述。
我正在寻找一种算法来计算以下内容：
我有：
3D 三角形网格。三角形不一定位于一个平面内。相邻两个三角形的范数向量夹角小于90度
两点。这两个点位于三角形网格的边缘或网格的三角形内。
我需要计算代表网格上两点之间最短路径的折线。
最简单的 and/or 最有效的策略是什么？
目前看来，你的问题没有明确定义；根据 "project" 线段到网格上的方向，可以有很多解决方案。
选择投影方向后，将网格展平到垂直于投影方向的平面上。此时，您的网格是二维边（线段）的集合；只需确定每条边与目标线段的交点（如果有的话）。
编辑:
更新后的问题现已明确定义。由于我对原始问题（上方）的回答已被标记为已接受，大概这意味着下面评论中提供的信息实际上是更新问题的 "accepted"。我总结一下：
- google 搜索 "shortest distance on 3d mesh" 会找到一些相关信息，例如 Shortest Path Approximation on Triangulated Meshes
- 另见： -- danh
由于您的 start/end 点可能位于网格上的任何位置（不限于顶点），我猜您正在搜索测地线最短路径（不是 Dikstra 最短路径后边）。 geometry-central中实现了一个很好的算法：http://geometry-central.net/surface/algorithms/flip_geodesics/
算法在论文"You Can Find Geodesic Paths in Triangle Meshes by Just Flipping Edges"中有描述。