algorithm - 如何检测三角形网格中的孔？

Question

实际上，我可以通过检查三角形的哪个边缘没有任何邻居来检测凸三角形网格的边界或边缘。因此，如果网格有一些孔，那么我们可以轻松突出显示该部分，因为我们有边顶点。

但问题是，如果我们只有边顶点或边界，我们怎么知道网格有一些洞？网格有多少个孔？

我对这个问题想了很多，但无法理解，有什么想法吗？孔检测的条件或检查应该是什么？

检测到一个洞后，我想填补它。但首先要检测它吗？

谢谢。

Answer 1

假设网格已连接并且您可以突出显示所有边界。你剩下所有的洞+一个额外的边界，即网格本身的边界。您可以丢弃其中最大长度的边界并获得所有孔。

Answer 2

源自扫描仪（例如 Kinect）的三角形网格可能具有小碎片（孤立的补丁）以及小孔。我建议通常可以通过计算与边界上的顶点相邻的顶点数来检测孔。如果相邻顶点少于边界顶点，则不是洞。

Answer 3

我的答案只适用于封闭的网格，但它会处理凹凸孔的情况。

为了解释起见，让我们想象一个 2D 网格。

计算网格的边界框。在我们的示例中，边界框需要存储 X 和 Y 轴的最小值和最大值，以及每个值对应的顶点索引：

struct BoundingBox
{
  float minX,maxX,minY,maxY;
  int vminX,vmaxX,vminY,vmaxY;
}

迭代网格中的每个顶点，在添加每个点时增大边界框。当顶点负责更改最小/最大值之一时，使用顶点网格索引存储或覆盖相应的 vmin/vmax 值。

例如

BoundingBox bounds;
bounds.minX = verts[0].X;
bounds.maxX = verts[0].X;
bounds.minY = verts[0].Y;
bounds.maxY = verts[0].Y;
bounds.vminX = bounds.vmaxX = bounds.vminY = bounds.vmaxY = 0;
for (int i = 1; i < numVerts; i++)
{
  Vertex v = verts[i];
  if (v.X < bounds.minX) { bounds.minX = v.X; bounds.vminX = i; }
  if (v.X > bounds.maxX) { bounds.maxX = v.X; bounds.vmaxX = i; }
  if (v.Y < bounds.minY) { bounds.minY = v.Y; bounds.vminY = i; }
  if (v.Y > bounds.maxY) { bounds.maxY = v.Y; bounds.vmaxY = i; }
}

现在遍历您的边界，直到找到一个包含您在边界框中收集的所有顶点的边界。这是你的外边界。其余边界是网格内的孔。