用于计算三维网格表面上两点之间的最短路径的算法 [英] Algorithm to calculate the shortest path between two points on the surface of a 3D mesh
问题描述
我有：
-
3D三角形网格。三角形不一定在一个平面上。两个相邻三角形的范数向量之间的夹角小于90度。
两点。这两点位于三角形网格的边缘或网格的三角形内。
我需要计算表示网格上两点之间最短路径的折线。
最简单和/或最有效的策略是什么？
现在，您的问题没有明确定义;根据用于将线段投影到网格上的方向，可以有许多解决方案。
选择投影方向后，将网格平铺到垂直于投影方向的平面。此时，您的网格是2d边（线段）的集合;只需确定每条边与目标线段的交点（如果有的话）即可。
编辑：
现在更新的问题已经很好定义。由于我对原始问题（上文）的回答已被标记为已接受，可能这意味着以下评论中提供的信息实际上是正在被接受的更新问题。我会总结一下：
- 在3D网格上最短距离的谷歌搜索中会出现一些相关信息，如三角网格上的最短路径近似值
- 另请参阅： https://stackoverflow.com/a/10389377/294949 - danh
I am looking for an algorithm to calculate the following:
I have:
A 3D triangle mesh. The triangles do not necessarily lie in one plane. The angle between the norm vectors of two neighbouring triangles is less then 90 degrees.
Two points. The two points lie either on an edge of the triangle mesh or inside a triangle of the mesh.
I need to calculate the polyline which represents the shortest path between the two points on the mesh.
What is the simplest and/or most effective strategy to do this?
As it stands, your problem is not well defined; there can be many solutions depending on the direction used to "project" the line segment onto the mesh.
Once you have chosen the direction of projection, flatten the mesh onto a plane perpendicular to the direction of projection. At this point, your mesh is a collection of 2d edges (line segments); just determine the intersection (if any) of each edge with your target line segment.
Edit:
The updated question is now well defined. Since my answer to the original question (above) has been marked as accepted, presumably that means the information given in the comments below are actually what was really being "accepted" for the update question. I'll summarize:
- A google search of "shortest distance on 3d mesh" turns up some relevant information, like Shortest Path Approximation on Triangulated Meshes
- Also, see: https://stackoverflow.com/a/10389377/294949 -- danh
这篇关于用于计算三维网格表面上两点之间的最短路径的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
