这个系列是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}\]
这样我们只需让变换后的距离在网格上尽可能相等即可，各向异性网格的生成就转换为了各向同性网格的生成。当然这样的做法在原始网格上直接进行处理是非常困难的，但借助于参数化可以相对容易地进行处理。针对这种问题常用的参数化包括共形映射以及高维等距嵌入两种方法。
Conformal Mapping
共形映射的一致化定理(uniform theorem)指出，任意曲面结合一个给定的黎曼度量得到的新曲面与原曲面共形等价。因此我们可以首先利用共形映射对原始网格进行参数化，然后在这个新的网格上进行各向同性的remeshing，最后通过共形映射的逆映射来得到各向异性的网格。
High-Dim Isometric Embedding
根据Nash embedding theorem，任意曲面都可以通过等距映射嵌入到一个高维的欧式空间。因此我们可以把原始网格先嵌入到一个更高维的欧式空间上，然后在高维空间里进行各向同性的remeshing。
把网格嵌入到高维空间的过程本质上是求解一个优化问题。由于我们要求嵌入是等距映射，优化目标需要包含刚性变换度量以及光滑性度量两部分，而其求解过程则类似于ARAP。
Quad Meshing
除了三角形网格外，四边形网格在工程中也有着大量的应用。我们希望四边形网格能够尽可能规则，即每个顶点上都只有四个邻域。
对于四边形网格最简单的参数化方法是把网格映射到一个均匀的二维格点上，此时网格上每个顶点都是规则的。对于原始网格上的奇异点，可以把它和网格上的另一点相连来将网格切开。而在参数平面上这条割线会分成两部分，并且在奇异点上相互垂直。
目前这种映射到二维均匀格点上的四边形网格参数化方法以及在工程中取得了非常广泛的应用。
All-Hex Meshing
对于六边形网格我们需要考虑物体的内部，此时可以借助体素化的形式来进行参数化。
在这种思想下PolyCube的做法是首先把四面体网格转换成grid形式，然后再把grid映射为六面体网格。
High-Order Meshes
除了常用的网格外我们还可以使用更高阶的网格来表达弯曲的单元。
这样的高阶网格可以对有限元分析等工程问题提供更高的精度。
而生成高阶网格的基本思路是首先构造一个低阶的线性网格，然后把这个线性网格变形为高阶网格。
