algorithm - 检测几何中的孔

Question

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

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

这是我的意思的图片。

如您所见，脸上有一个洞。我对几何还很陌生，所以请尝试用通俗易懂的术语进行解释。

Answer 1

如果一个 3D 物体是“简单的”，意味着它没有孔，它满足 Euler's Formula for Polyhedra , V - E + F = 2其中 V是图中的顶点数，E是边数，F是面的数量。如果你能很容易地得到这三个数字，你就可以计算公式 V - E + F .如果结果不是 2，则对象有一个洞(或其他一些病理现象，如捏)。事实上，你可以通过 V - E + F 判断物体有多少孔。 :如果数字为0，则有一个孔；如果数字是-2，它有两个孔；等

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

不仅如此，当形状有孔时(这正是您感兴趣的情况)，计算时很容易出错。避免犯错的最简单方法是将图形分成凸面部分，例如 triangulation .

该公式不会告诉您哪个面有孔，但如果您知道图形有孔，您可以将欧拉公式分别应用于每个面，再次使用三角测量。在这种情况下，没有孔的面将具有 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 .在这种情况下，我将图形分解为三个凸四边形。

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