水密网格的正式定义

在计算机图形学中,水密(watertight)网格通常描述由一个封闭曲面组成的网格。 从这个意义上讲,水密网格不包含孔洞并且内部定义明确。 因此,计算机图形学和计算机视觉中的许多应用通常都需要它们——例如,将网格体素化为占用栅格或符号距离函数时。 但是,我发现很难找到水密性的合适的正式定义。 在本文中,我想讨论我在硕士论文中使用的定义。

作为我硕士论文的一部分,我使用 ShapeNet [4] 中的 CAD 模型——特别是三角网格——来学习汽车的形状完整性。 ShapeNet 中模型的问题之一是它们的复杂性。 如下图所示,这些模型可能非常详细——包含数十万个面和顶点——而且不是无懈可击的(例如,由于缺少窗户)。 例如,为了使用深度神经网络“学习”形状完成,我需要对汽车模型进行体素化——这需要水密网格,并简化网格以提高效率。 图 1 显示了一些复杂模型的示例。

图1 - 非常复杂的汽车模型示例(左)和用于简化的半凸包算法示例(右)

对于水密网格的讨论,我们首先需要正式定义什么构成了适当的三角形网格(例如下面的 [1]):

定义:
三角形网格 M=(V,F) 由一组顶点 V⊆R3 和一组三角形面  F⊆{1,…,|V|}3 定义
使得 f=(f1,f2,f3)∈F 定义了由相应顶点 vf1 、vf2和vf3包围的三角形面, 面也隐含地定义了顶点之间的边 E(F)

邻接(adjacency)和关联(incidency)的概念很自然地延伸到三角网格。 我们注意到三角形网格仅定义对象的表面。 如果没有额外的约束,通常很难推断表面的内部和外部——以及表面是否封闭。 这个问题自然引出了水密网格的概念。 在文献中,例如 [1] 中的示例,水密网格通常被定义为没有边界边的 2-流形网格。

然而,一个确切的定义——尤其是我可以在我的硕士论文中使用的定义——并不是很容易找到。 最后,我补充阅读了[2]和[3]的部分内容,做出如下定义:

定义:
- 自相交是同一网格的两个面的相交。
- 非流形边具有两个以上的入射面。
- 顶点的星形是其所有入射面的并集。
- 非流形顶点是在移除顶点时对应的星没有连接的顶点。
- 如果一个网格既不包含自相交,也不包含非流形边,也不包含非流形顶点,则它是 2-流形的。
图2 - 非流形顶点(左)和非流形边(右)

这些有点抽象的定义的插图可以在图 2 中找到(最初来自 [1])。 一般来说,2-流形网格优于任意网格,因为许多算法和应用程序不适用于非流形网格。 然而,在我们的例子中,2-流形网格的定义只是出于正式定义水密网格(有时也称为封闭网格)的需要。 直觉上,2 流形网格中唯一缺少的约束是“封闭性”的概念——意味着清晰的内部和外部。 当考虑非流形边的定义时,这一点变得很明显,非流形边也允许只有一个入射面的边,即所谓的边界边。

定义:
如果每条边恰好有两个入射面,即不存在边界边,则 2 流形网格称为水密网格。

上述定义虽然看起来抽象,但在实践中也很有用。 在软件中,例如 在 MeshLab 中,可以轻松识别和标记非流形顶点、边以及边界,以帮助设计和使用三角形网格。

从上面的定义中,我们也可以推导出“封闭性”本质上是一种设计选择。 这意味着我们无法通过算法从非水密网格中提取水密网格。 然而,对于我的应用程序,我假设所有网格都应该是“封闭的”,然而,模型中可能包含复杂的细节——例如,被建模为“封闭”外部但也包括内部的汽车。 在这种情况下,我决定通过使用半凸包近似来同时解决简化和水密性问题。 这种近似的结果可以在图 1 中找到。


原文链接:A Formal Definition of Watertight Meshes

BimAnt翻译整理,转载请标明出处