获取网格的边框边缘 - 在缠绕顺序 [英] Get border edges of mesh - in winding order

问题描述

我有一个三角形网格。假设它看起来像一个崎岖不平的表面。我希望能够找到落在网的边界周围的所有边缘。 （忘了内部顶点）

I have a triangulated mesh. Assume it looks like an bumpy surface. I want to be able to find all edges that fall on the surrounding border of the mesh. (forget about inner vertices)

我知道我必须要找到那些只连接到一个三角形的边缘，并收集所有这些结合在一起，这就是答案。但我想，以确保这些边缘的顶点形状周围按顺时针方向有序。

I know I have to find edges that are only connected to one triangle, and collect all these together and that is the answer. But I want to be sure that the vertices of these edges are ordered clockwise around the shape.

我想这样做，是因为我想避开网外的多边形线。

I want to do this because I would like to get a polygon line around the outside of mesh.

我希望这是不够清楚明白。从某种意义上说，我试图脱三角网格。哈！如果有这样一个术语

I hope this is clear enough to understand. In a sense i am trying to "De-Triangulate" the mesh. ha! if there is such a term.

推荐答案

边界边缘仅由在网状一个三角形引用的，所以可以找到他们需要通过在网格的所有三角形来扫描并采取与一个边缘单一的引用计数。为此，您可以高效地（在 O（N））通过使用一个哈希表。

Boundary edges are only referenced by a single triangle in the mesh, so to find them you need to scan through all triangles in the mesh and take the edges with a single reference count. You can do this efficiently (in O(N)) by making use of a hash table.

要在边缘设置转换为有序的多边形循环中，您可以使用遍历方法：

To convert the edge set to an ordered polygon loop you can use a traversal method:

1. 选择任何未访问的边缘片段 [v_start，v_next] 并添加这些顶点多边形循环。
2. 找到未访问的边缘片段 [V_I，v_j] 有两种 V-I = v_next 或 v_j = v_next 并添加其他顶点（一的没有的等于 v_next ）的多边形循环。复位 v_next ，因为这新增加的顶点，作为参观纪念的边缘，距离2继续。
3. 在遍历时，我们回到 v_start 完成的。

1. Pick any unvisited edge segment [v_start,v_next] and add these vertices to the polygon loop.
2. Find the unvisited edge segment [v_i,v_j] that has either v_i = v_next or v_j = v_next and add the other vertex (the one not equal to v_next) to the polygon loop. Reset v_next as this newly added vertex, mark the edge as visited and continue from 2.
3. Traversal is done when we get back to v_start.

遍历会给多边形循环，可以有两种顺时针或反顺时针顺序。一致的排序可以通过考虑多边形的的签署区域建立。如果遍历结果在错误的方向，你只需要扭转多边形环顶点的顺序。

The traversal will give a polygon loop that could have either clock-wise or counter-clock-wise ordering. A consistent ordering can be established by considering the signed area of the polygon. If the traversal results in the wrong orientation you simply need to reverse the order of the polygon loop vertices.

这篇关于获取网格的边框边缘 - 在缠绕顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！