algorithm - 检测几何中的孔

Question

我正在使用序列化管道。我正在制作模型并将其导出。我不希望导出任何脸上有洞的模型。如何检测漏洞并报告错误？

我可以访问所有顶点、边、面等。

这是我的意思的图片。

如您所见，脸上有一个洞。我对几何学相当陌生，所以请尝试用外行的方式解释。

Answer 1

如果一个 3D 对象是“简单的”，即它没有孔，则它满足欧拉多面体公式，V - E + F = 2其中V是图中的顶点数，E是边F数，是面数。如果你能很容易地得到这三个数字，你就可以计算出公式V - E + F。如果结果不是 2，则该对象有一个洞（或其他一些病变，如夹伤）。实际上，您可以通过以下方式判断对象有多少个孔V - E + F：如果数字为 0，则它有一个孔；如果数字是-2，它有两个孔；等等

计算V,E和F可能有点棘手，因为顶点通常由两条或多条边共享，而边通常由两个面共享。你不想多算；如果三个边在一个顶点中相遇，您只想计算一次顶点，而不是三次。

不仅如此，当形状有孔（这正是您感兴趣的情况）时，很容易计算错误。避免犯错的最简单方法是使用三角剖分法将图形分解为凸形部分。

该公式不会告诉您哪个面有孔，但如果您知道该图形有孔，您可以将欧拉公式分别应用于每个面，再次使用三角测量。在这种情况下，没有孔的面现在将限制在所讨论的面上V - E + F = 1。V,E,F（如果将面以外的区域算作另一个（无限）面，则与前面公式的差异得到解决）。有孔的面会有V - E + F < 1.

例如，平面上的三角形有V=3、E=3和F=1（由其内部表示的三角形的“面”）给出V-E+F=1。另一方面，内部具有类似形状的三角形孔的三角形，其中连接了内部和外部三角形的相应顶点，将具有V=6，E=9和F=3。V-E+F=0在这种情况下，我将图形分成三个凸四边形。

大多数关于计算机图形学的书籍都讨论了这个主题。

Answer 2

如果我理解正确，您想检测带孔的多边形。现在，带有孔的多边形的表示方式可能因每个软件而异（有些存储单独的内部轮廓列表）。然而，3D 包（包括像 OBJ 这样的格式）中的常见表示使用平面顶点表示，它看起来像这样：

...其中 2,6 和 1,7 将是在同一个多边形中存储两次的相同顶点索引（图中的数字表示面点索引）。请注意，从 1,7 到 2,6 的这条边可以在某些软件中隐藏，但如果软件将多边形顶点存储在索引/指针的平面列表中，即使它不可见，它也存在。

因此，一种快速判断多边形是否具有仅给定面部数据（例如：来自 OBJ 文件）的此类表示的孔的方法是查看它是否具有顶点索引的重复条目。如果同一顶点索引在多边形中重复多次，则它有一个洞。

现在有一种情况，您可以找到空内轮廓的重复顶点，如下所示：

...其中 2,4 是焊接的（相同的顶点）。如果要区分这些情况，可以在连接外轮廓和内轮廓的边只有一个顶点重复而不是两个顶点时检测它们。在这种情况下，内部轮廓是空的，这个多边形只是一个时髦的多边形（可能是通过 CSG/平面切片操作创建的）。

如果您想要一个真正强大的解决方案，则值得编写一个例程，通过将列表拆分为多个内部/外部组，将这些平面轮廓列表“展开”为多个内部/外部组，其中找到将一个轮廓连接到另一个轮廓的重复边。如果内部组的顶点少于 3 个，那么它们可能只是没有视觉上明显的洞的时髦多边形。如果它们有 3 个或更多，则它们满足显示您可以直观看到的孔所需的标准。如果内部轮廓没有形成完整的孔，您可以只折腾内部轮廓并保留外部轮廓（在这种情况下，就像只保留上图中的 3 点三角形外部，同时扔掉那些多余的顶点，

如果您不介意导出未焊接的几何体，只要它不是时髦的（没有孔或内部轮廓），您可以应用的一个简单解决方案是简单地克隆（制作唯一）在多边形中重复的顶点，基本上是拆焊它，像这样：

这比成熟的镶嵌类型的解决方案要容易一些，而且它最终仍然会为您提供没有任何孔或单独内部的多边形。为了演示，我在视觉上将 2 和 4 分开，以强调它们现在是单独的顶点，但您不必这样做（它们可以是重合的）。

如果您有一个不支持孔的镶嵌器，这种拆焊技术也很有用。您可以应用此技术取消焊接多边形，对其进行镶嵌，然后焊接/合并重合顶点以获得最终结果。