GAMES301课程笔记05-全局单射参数化方法
这个系列是GAMES301-曲面参数化(GAMES 301: Surface Parameterization)的同步课程笔记。课程内容涉及曲面参数化的基本理论与问题描述、面向离散网格的参数化、基于基函数表示的连续参数化、共形参数化、曲面参数化的应用等。本节课主要介绍全局单射参数化方法。
在前面的课程中介绍了无翻转曲面参数化的常用思想和技术。除了没有翻转外，我们往往还会对参数化的过程引入更多的约束。比如说我们希望参数化是一个全局单射(global injective)，此时参数平面上不会出现任何自交和相互覆盖的情况。
类似于初始无翻转情况的参数化，计算全局单射时往往也会从Tutte’e embedding出发。此时的初始化结果是无翻转也没有重叠的，然后通过优化几何扭曲的方式来获得所需的参数化。当然在迭代的过程中除了保证没有翻转外还需要保证在边界上没有自交。
Barriers
为了保证参数化的结果没有翻转和自交，我们可以为优化目标函数设置一个障碍函数(barrier function)。当网格上趋向于出现自交时会产生一个巨大的惩罚项从而避免三角形进一步退化。由于全局单射是由参数化后的边界控制的，因此我们可以为网格边界设置一个障碍函数。当边界上出现自交时一定存在顶点\(U_i\)穿过了三角形的一条边\(U_1 U_2\)，因此我们可以利用点到直线的距离作为障碍函数：
\[E_{ev} (\mathbf{b}_j, \mathbf{x}_i) = \max \bigg( 0, \frac{\varepsilon}{D(\mathbf{b}_j, \mathbf{x}_i)} -1 \bigg)^2\]其中函数\(D(\mathbf{b}_j, \mathbf{x}_i)\)度量了顶点到边的距离，而参数\(\varepsilon\)则控制了二者之间的最小间隔。
此时整体的优化目标函数可以表示为几何扭曲项\(E_d (\mathcal{M}, \mathcal{\hat{M}})\)与障碍函数\(E_b (\mathcal{B})\)之和。我们可以使用前面介绍过的各种优化求解器来进行求解。
Scaffold
scaffold方法的思想在于为原始网格\(\mathcal{M}\)设计一个辅助网格\(\mathcal{S}\)，通过对整个网格\(\mathcal{G} = (\mathcal{M}, \mathcal{S})\)构造无翻转的参数化来保证原始网格\(\mathcal{M}\)不会出现自交。这样相当于去掉了无自交的约束，只需考虑整体网格上无翻转即可。
在优化整体网格\(\mathcal{G}\)上的扭曲时有时还会同步更新辅助网格\(\mathcal{S}\)上的连接关系。这样可以避免辅助网格出现退化，也能够提升参数化后原始网格\(\mathcal{M}\)的质量。
Combined
上面介绍的两种方法在计算上都存在一些局限性。比如说barrier函数需要考虑所有边界可能出现的自交情况，计算时会非常的繁琐，同时一些实践表明使用通用求解器的效率不是很高；scaffold方法需要更新辅助网格上的连接关系，而当Hessian矩阵的非零元发生改变时需要重新进行符号分解，使得整个求解过程非常的缓慢。
Nonzero Structure
显然我们希望Hessian矩阵可以有固定矩阵的非零元结构，这样可以避免很多重复的符号分解计算。由于scaffold方法需要更新网格的连接关系，我们几乎无法避免对Hessian矩阵的重复计算；但对于障碍函数则可以通过一些手段来进行加速。
首先对网格节点进行分组，把边界上的顶点和内部顶点分开。对于内部顶点我们无需考虑障碍函数，因此其非零元结构是固定的；而对于边界上的顶点则还要继续考虑只与边界顶点相关的\(H_{BB}\)以及考虑相邻内部顶点的\(H_{IB}\)两部分。其中\(H_{BB}\)只与障碍函数有关，而且在不发生自交情况时函数值恒为0，其Hessian矩阵也恒为0。如果发生了自交的情况，则需要更新Hessian矩阵相应位置上的元素。
为了避免更新Hessian矩阵同时固定非零元结构，我们可以考虑每一对边界边可能出现的碰撞情况。此时对于不碰撞的边也需要在Hessian矩阵相应的位置上填上0，这样就可以避免反复计算符号分解。
不过需要注意的是在这种情况下Hessian矩阵的稀疏性会比较差，求解稀疏线性系统的效率仍然很低，甚至比直接更新Hessian矩阵并重新计算的情况还要低。
因此要提高求解效率就必须要降低Hessian矩阵的density。注意到所有可能边界边对的数量约为边界边数量的平方，如果可以降低边界边的数量就能够极大地提高求解效率。在这种思想下我们可以结合scaffold方法的思想，在参数化平面上为网格套上一层稀疏的壳(shell)从而极大地减少边界点和边的数量，进而提高计算效率。
Convex Approximation
除此之外我们还可以对障碍函数进行调整。原始障碍函数使用了点到边界的距离：当顶点\(\mathbf{x}_i\)位于边界\(\mathbf{b}_j\)定义的区域\(\Omega_2\)时等于点到直线距离；而当\(\mathbf{x}_i\)位于外部\(\Omega_1\)和\(\Omega_3\)时则使用了\(\mathbf{b}_j\)到边界两个端点的距离。实际上这样定义的障碍函数仅是\(C^1\)连续的，在端点附近的半圆上计算Hessian矩阵可能会出现奇异的问题。为了改进距离函数可以使用如下定义的\(C^\infty\)连续函数：
\[D(\mathbf{b}_j, \mathbf{x}_i) = \frac{1}{2} \bigg( \Vert \mathbf{x}_{j,1} - \mathbf{x}_i \Vert_2 + \Vert \mathbf{x}_{j,2} - \mathbf{x}_i \Vert_2 - \Vert \mathbf{x}_{j,1} - \mathbf{x}_{j,2} \Vert_2 \bigg)\]不难发现上式实际上就是三角不等式，当\(\mathbf{x}_i\)与\(\mathbf{b}_j\)趋于碰撞时函数值会趋于0；而它的等值面则是\(\mathbf{x}_{j,1}\)和\(\mathbf{x}_{j,2}\)为焦点所定义的椭圆。
接下来对新的障碍函数计算Hessian矩阵。注意到新的距离函数可以分解为凸函数与凹函数的和，利用凹凸分解就可以直接对Hessian矩阵进行正定化。
结合上面介绍的两种技巧就可以构造出一个有固定非零元结构且低density的Hessian矩阵，这样在进行优化时就可以获得非常高的计算效率。
Positional Constraints
在很多应用中我们还会指定网格上一些顶点的位置，这相当于为参数化引入了更多的约束。在这种情况下可能是无法使用Tutte’s embedding进行初始化，而且那些固定位置的顶点还可能产生网格的自锁现象。
此时我们仍然可以使用scaffold的思想来进行处理。首先使用任意全局单射方法来获得一个初始参数化，并且结合scaffold生成一个内部无翻转、边界无自交的参数化。然后我们直接将所需的顶点移动到指定位置，这会导致参数平面上出现各种翻转的三角形。最后使用存在初始翻转情况下的无翻转参数化方法方法来修正这些三角形即可。
