我有一个三角网格。假设它看起来像一个崎岖的表面。我想能够找到所有落在网格周围边界上的边缘。（忘记内部顶点）
我知道我必须找到只与一个三角形相连的边缘，并将所有这些收集在一起，那就是答案。但是我想确保这些边缘的顶点按顺时针顺序环绕形状。
我想这样做是因为我想获得网格外部的多边形线条。
我希望这足够清楚易懂了。某种意义上，我正在尝试“去三角化”网格。哈！如果有这样的术语的话。
获取网格的边缘 - 按顺序排列
21
- Ross Oliver
1
1好的，想象一下如果我的表面侧面有一个大凹痕，伸入其内部形状，但是有一个细长的颈部。凸包会跟随这个凹痕吗？还是会直接跳过它，因为它只考虑形状的最大范围？没有图片很难解释清楚。 - Ross Oliver
4个回答
27
边界边仅被网格中的单个三角形引用，因此要找到它们，您需要扫描网格中的所有三角形，并取带有单个引用计数的边。您可以有效地（在O（N））通过利用哈希表来完成。
要将边集转换为有序多边形环，可以使用遍历方法：
- 选择任何未访问的边缘线段
[v_start,v_next]并将这些顶点添加到多边形环中。 - 查找未访问的边缘线段
[v_i，v_j]，其中v_i = v_next或v_j = v_next，并将另一个顶点（不等于v_next）添加到多边形环中。将v_next重置为这个新添加的顶点，标记该边为已访问，并从2继续。 - 当我们回到
v_start时，遍历完成。
遍历将给出可能具有顺时针或逆时针排序的多边形环。可以通过考虑多边形的有向面积来建立一致的排序。如果遍历结果是错误的方向，则只需反转多边形环顶点的顺序。
- Darren Engwirda
3
嗨，达伦，我按照你上面建议的算法进行了操作。它第一次就成功了！谢谢你。它的工作原理非常合乎逻辑，所以感谢你给我的精确描述。我已经在网格中找到了仅存在于一个三角形中的边缘。所以我需要的只是遍历算法来正确排序顶点。 - Ross Oliver
如何高效地制造碰撞的哈希？即使起点和终点颠倒，边缘的哈希值也应该相同。 - TJHeuvel
@TJHeuvel：一种方法是在对索引进行排序后，对边的副本调用哈希函数。 - undefined
7
俗话说得好，先让它运行起来，然后再让它更好地运行。我注意到在上面的例子中，它假设边缘数组中的所有边缘都连接成了一个漂亮的边框。在现实世界中可能并非如此（正如我从使用的输入文件中发现的那样！）。实际上，我的一些输入文件实际上有许多多边形，并且需要检测所有边框。我还想确保绕序正确。所以我也修复了这个问题。请见下文。（感觉我终于有所进展了！）
private static List<int> OrganizeEdges(List<int> edges, List<Point> positions)
{
var visited = new Dictionary<int, bool>();
var edgeList = new List<int>();
var resultList = new List<int>();
var nextIndex = -1;
while (resultList.Count < edges.Count)
{
if (nextIndex < 0)
{
for (int i = 0; i < edges.Count; i += 2)
{
if (!visited.ContainsKey(i))
{
nextIndex = edges[i];
break;
}
}
}
for (int i = 0; i < edges.Count; i += 2)
{
if (visited.ContainsKey(i))
continue;
int j = i + 1;
int k = -1;
if (edges[i] == nextIndex)
k = j;
else if (edges[j] == nextIndex)
k = i;
if (k >= 0)
{
var edge = edges[k];
visited[i] = true;
edgeList.Add(nextIndex);
edgeList.Add(edge);
nextIndex = edge;
i = 0;
}
}
// calculate winding order - then add to final result.
var borderPoints = new List<Point>();
edgeList.ForEach(ei => borderPoints.Add(positions[ei]));
var winding = CalculateWindingOrder(borderPoints);
if (winding > 0)
edgeList.Reverse();
resultList.AddRange(edgeList);
edgeList = new List<int>();
nextIndex = -1;
}
return resultList;
}
/// <summary>
/// returns 1 for CW, -1 for CCW, 0 for unknown.
/// </summary>
public static int CalculateWindingOrder(IList<Point> points)
{
// the sign of the 'area' of the polygon is all we are interested in.
var area = CalculateSignedArea(points);
if (area < 0.0)
return 1;
else if (area > 0.0)
return - 1;
return 0; // error condition - not even verts to calculate, non-simple poly, etc.
}
public static double CalculateSignedArea(IList<Point> points)
{
double area = 0.0;
for (int i = 0; i < points.Count; i++)
{
int j = (i + 1) % points.Count;
area += points[i].X * points[j].Y;
area -= points[i].Y * points[j].X;
}
area /= 2.0f;
return area;
}
- Ross Oliver
4
遍历代码（不高效 - 需要整理，我会在某个时候处理）请注意：我将链中的每个段存储为 2 个索引 - 而不是达伦建议的1个。这纯粹是出于我自己的实现/渲染需求。
// okay now lets sort the segments so that they make a chain.
var sorted = new List<int>();
var visited = new Dictionary<int, bool>();
var startIndex = edges[0];
var nextIndex = edges[1];
sorted.Add(startIndex);
sorted.Add(nextIndex);
visited[0] = true;
visited[1] = true;
while (nextIndex != startIndex)
{
for (int i = 0; i < edges.Count - 1; i += 2)
{
var j = i + 1;
if (visited.ContainsKey(i) || visited.ContainsKey(j))
continue;
var iIndex = edges[i];
var jIndex = edges[j];
if (iIndex == nextIndex)
{
sorted.Add(nextIndex);
sorted.Add(jIndex);
nextIndex = jIndex;
visited[j] = true;
break;
}
else if (jIndex == nextIndex)
{
sorted.Add(nextIndex);
sorted.Add(iIndex);
nextIndex = iIndex;
visited[i] = true;
break;
}
}
}
return sorted;
- Ross Oliver
0
你的问题的答案实际上取决于三角网格在内存中的表示方式。如果使用半边数据结构，那么算法就非常简单，因为在半边数据结构构建期间已经完成了所有工作。
- 从任何边界半边开始
HE_edge* edge0（可以通过线性搜索所有半边来找到第一个没有有效face的边）。设置当前半边HE_edge* edge = edge0。 - 输出当前边缘的目标
edge->vert。 - 顺时针围绕形状（逆时针围绕周围的“孔”）的下一条边将是
edge->next。 - 当到达
edge0时停止。
- Fedor
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接