GAMES301课程笔记07-参数化应用2(网格生成)

这个系列是GAMES301-曲面参数化(GAMES 301: Surface Parameterization)的同步课程笔记。课程内容涉及曲面参数化的基本理论与问题描述、面向离散网格的参数化、基于基函数表示的连续参数化、共形参数化、曲面参数化的应用等。本节课主要介绍曲面参数化在网格生成中的应用。

Meshing

网格生成(meshing)是指利用多边形或是多面体来近似三维模型的几何。在有限元分析和CFD等工程问题中都大量使用了网格生成的技术。

重新网格化(remeshing)则是指对已有的网格模型进行更新来获得一个更合适的网格。以三维重建为例，扫描得到的点云模型往往不够均匀，这时候就需要使用remeshing的技术来得到一个更高质量的模型。

根据类型的不同，常用的网格模型包括三角形网格、四边形网格、四面体网格以及六面体网格等。其中三角形网格和四边形网格只能表达模型的表面，而四面体和六面体网格则包含模型内部的实体。

Quality Metrics

如何衡量网格的质量取决于实际任务的需求。常用的度量包括采样密度、大小、朝向、对齐、单元形状、拓扑性质等。

Local Structure

以单元形状为例，在大多数任务中我们都希望三角形网格上每个三角形都接近于一个正三角形。这种情况下的网格称为是各向同性(isotropic)的，反之则称为是各向异性(anisotropic)的。

对于单元密度，如果网格在整个表面都有接近的密度则称是均匀(uniform)的，而如果网格在一些高曲率的地方比较密低曲率的地方比较稀疏则称是非均匀(nonuniform)或自适应(adaptive)的。

在很多CAD问题中模型往往会有一些比较尖锐的边缘，在生成网格时我们需要对网格进行对齐从而保留这些边缘。而在很多CAE或是CFD问题中还需要根据求解的PDE来控制网格的朝向。

Global Structure

除了上述的一些局部信息外，很多时候我们也需要考虑一些全局的信息。比如说每个顶点相邻的顶点数为valence，对于三角形网格当valence等于6时称此时的网格是规则(regular)的，否则称网格是不规则(irregular)的。在大多数情况下我们都希望网格能够尽可能规则，不过在实际中这非常难以做到，绝大多数的网格都介于规则和不规则之间。

Parameterization-Based Meshing

如何对模型进行网格化已经有非常多的研究，比如说经典的Delaunay三角化、在工程中常用的advancing front方法等。在本节课中我们主要介绍基于参数化的网格生成算法。

基于参数化的meshing和remeshing算法的主要流程如下：

将原始网格参数化到二维平面上
在参数平面上进行meshing和remeshing
将参数平面上的网格重新映射回三维空间中

和其他meshing算法相比，基于参数化的算法只需要考虑二维平面，这往往要比直接在模型表面进行处理要容易很多。

对于meshing这样的下游任务我们要求参数化需要有低扭曲的性质，同时对于封闭曲面还需要满足一些额外的条件保证处理后的结果仍然能够拼接成一个封闭的曲面。

Isotropic Triangular Meshing

对于生成各向同性规则网格的任务，传统的网格简化算法往往会过滤掉原始网格上一些相互接近的三角形。这会导致重新生成的网格丢失一些重要的几何信息。

在这种情况下就可以考虑基于参数化的网格生成方法，我们只需要在参数平面上进行各向同性的remeshing即可。这种做法的本质是在参数平面上使用欧式距离来近似原始曲面上的测地距离，而为了保证remeshing后仍然能够得到封闭的曲面一般还需要控制边界点不动。

整个基于参数化的各向同性规则网格的生成算法流程如下：

Anisotropic Remeshing

对于各向异性的网格生成任务，我们需要引入一个度量场(metric field)\(M(\mathbf{x})\)来描述网格在不同位置的密度、朝向等几何信息。

度量场实际上就是网格上的度量函数，需要满足非负、同一、对称以及三角不等式等条件，而在离散情况下度量场表现为一个正定矩阵。得到度量场之后就可以进一步定义网格上的内积、范数以及长度等几何量。

在很多任务中度量场还可以结合实际的需求来进行定义。

因此各项异性网格生成本质是要求网格在度量场的作用下满足各向同性。具体来说，我们先对度量场进行特征分解：

\[\mathbf{M} (\mathbf{x}) = \mathbf{U} (\mathbf{x}) \Lambda \mathbf{U}^T (\mathbf{x})\]

然后定义变换矩阵\(\Phi\)：

\[\Phi = \Lambda^{-\frac{1}{2}} \mathbf{U}^T (\mathbf{x})\]

此时网格上的距离函数可以表示为：

\[\begin{aligned} d(\mathbf{x}, \mathbf{y}) &= \sqrt{(\mathbf{x} - \mathbf{y})^T \mathbf{M} (\mathbf{x} - \mathbf{y})} \\ &= \sqrt{(\mathbf{x} - \mathbf{y})^T \Phi^T \Phi (\mathbf{x} - \mathbf{y})} \\ &= \sqrt{[\Phi (\mathbf{x} - \mathbf{y})]^T [\Phi (\mathbf{x} - \mathbf{y})]} \\ &= \sqrt{(\mathbf{\tilde{x}} - \mathbf{\tilde{y}})^T (\mathbf{\tilde{x}} - \mathbf{\tilde{y}})} \end{aligned}\]