GAMES301课程笔记01-曲面参数化介绍
这个系列是GAMES301-曲面参数化(GAMES 301: Surface Parameterization)的同步课程笔记。课程内容涉及曲面参数化的基本理论与问题描述、面向离散网格的参数化、基于基函数表示的连续参数化、共形参数化、曲面参数化的应用等。本节课主要介绍曲面参数化的概念及其应用。
曲面参数化及其应用
曲面参数化
曲面参数化(surface parameterization)是几何处理中的重要内容。在日常生活中曲面参数化最常见的例子是世界地图，尽管地球是一个三维球面我们仍然可以使用一张二维的地图来表示地球的表面。
类似地，艺术家可以在橘子的表面进行切割，展开后可以形成各种各样的艺术图案。
对于一些复杂的几何形状直接对表面进行展开可能是比较复杂的，此时可以通过对表面进行分片的方式来分别进行参数化。
从上面的例子可以看出，曲面参数化的直观解释是把三维空间中的曲面展开成二维的平面。从数学上讲，曲面本质是二维的平面(流形)嵌入到三维空间的结果，而参数化的目标是寻找三维到二维的映射。
曲面参数化的应用
参数化最常见的应用是各种各样的世界地图。在大量的工程实践中人们设计出了不同的地图绘制方法以满足不同类型任务的需求。
在CG行业，参数化最广泛的应用是各种贴图。我们可以把物体表面的各种信息记录到二维的贴图上，这样在进行渲染时只需要对贴图进行查询即可。
纹理地图同样是参数化的一种应用。当物体的模型比较复杂时可以通过分片的方式把整个表面划分成若干个区域，然后把它们汇总到一张贴图上就得到了纹理地图。
曲线和曲面的拟合同样可以视为参数化的过程，它们的本质是把连续的曲线曲面通过离散点来进行表示。
在游戏行业中，游戏画面的渲染就大量应用了参数化的技术来保存场景或人物的各种信息。
实际上曲面参数化是很多几何处理算法的基础，许多在三维空间中难以直接处理的问题通过参数化到二维平面后可以相对容易地来进行求解。
曲面参数化的表达及度量
曲面参数化
根据曲面的表达方式不同，曲面的参数化方法大致可以分为连续映射和分片映射两大类。
连续映射方法是把函数空间视为基函数的线性组合，通过寻找基函数的映射来实现参数化。
对于更加复杂的曲面则可以考虑分片映射方法。在分片映射方法中原始定义域会分解为一些比较简单的几何对象(三角形)，通过寻找每一个几何对象映射到二维平面的结果来实现全局的参数化。
参数化的度量
那么如何度量参数化算法的效果呢？显然我们希望曲面在参数化后能够保持原来的一些几何量，如角度、面积或是距离等，通常情况下会根据实际任务的需求来选择合适的几何度量。
函数\(f\)的局部几何形变可以使用其Jacobian矩阵(Jacobian matrix)来进行度量，实际上Jacobian矩阵的行列式度量了曲面上每一点局部有向面积的变化。
根据参数化所保持的几何性质，参数化算法也可以分为保角的共形映射(conformal mapping)、保面积的等积映射(authalic mapping)以及同时保持角度和面积的等距映射(isometric mapping)。
共形映射可以理解为曲面在参数化前后任意点上两个方向的夹角保持不变。
以球面到平面的映射为例，不同的参数化方法会得到不同的结果。
共形映射有许多非常良好的几何性质，同时它也与Yamabe方程存在深刻的联系。这些内容会在课程的后续部分进行介绍。
对于等距映射，它要求曲面上每个点在映射前后局部的角度和面积保持一致。可以证明处处等距的曲面具有恒为0的高斯曲率，这样的曲面也称为可展曲面(developable surface)。三维空间中的可展曲面只有三种，分别为柱面、锥面以及切线面。
几何形变/扭曲
对非可展曲面进行参数化时会不可避免地产生几何上的形变和扭曲。以二维仿射变换为例，仿射矩阵\(J_t\)的奇异值描述了局部的几何扭曲。如果两个奇异值相等则说明映射是保角的，如果它们的乘积为1则说明映射是保面积的，而如果两个奇异值都是1则说明映射是等距映射。
一个好的参数化要求是(局部)一个双射，而且具有比较小的扭曲。这里双射表示参数化后平面不会出现重叠的情况。
可以证明只要保证参数化在任意点上的Jacobian矩阵行列式大于0就可以实现局部双射，这表示曲面在参数化后不会出现翻转的情况。
当然需要注意的是，参数化满足局部是双射也不一定能够保证全局是双射。
目前很多主流的参数化算法都定义了一些distortion metric来描述曲面的扭曲情况，通过最小化distortion metric来保证参数化算法不会出现过大的扭曲。
总结一下，一个理想的参数化算法需要保证有尽可能小的扭曲而且不会出现翻转的情况。
曲面参数化的主要方法
目前主流的曲面参数化方法主要包括Tutte参数化、基于几何优化的参数化方法以及保证无翻转的参数化方法等。
Tutte’s Method and Its Variants
Tutte参数化是经典的线性参数化方法。它的思想是把开放曲面的边界映射到一个凸多边形上，然后通过求解线性系统的方式来获得参数化。Tutte参数化可以严格保证不会发生翻转，但它可能会产生比较大的几何扭曲。
Geometry Based Optimization Methods
另一大类参数化方法的思想是把参数化的问题转换为几何上的优化问题来进行求解。
不过需要注意的是这类方法无法保证不出现翻转的问题，因此往往需要结合一些后处理算法来检测和消除可能出现的翻转。
Foldover Free Guaranteed Optimization Methods
保证无翻转的参数化是最近几年非常流行的参数化方法，其特点在于可以在理论上保证不会出现翻转。这类方法的基本流程是从一个无翻转的参数化(如Tutte参数化)开始通过不断地优化来减少几何扭曲，同时在每一步优化中都保证不会出现翻转。
在设计优化目标时为了防止出现翻转可以添加一个几何碰撞的障碍函数，如果出现翻转则会产生一个巨大的惩罚项。
另一种设计思路是添加一个几何形变的障碍函数，当三角形趋向于退化时产生一个巨大的惩罚项。
我们可以使用Jacobian矩阵的奇异值来设计优化函数，其对称Dirichlet能量(symmetric Dirichlet energy)可以防止优化时出现三角形退化的情况，当然还需要添加奇异值大于0的约束条件来防止翻转。这样参数化的迭代过程就转换为了一个约束优化问题。
优化问题的求解
在大多数情况下我们构造的优化问题都是一个非凸的约束优化问题，因此需要高效的求解器来进行求解。最基本的优化方法是使用梯度下降的策略，通过计算梯度方向和步长来逐步寻找到局部极小值。
根据计算梯度方向以及步长的方法不同，优化算法可以分为一阶方法、伪牛顿法以及二阶方法等。
First-Order Methods
除了调用标准求解器之外还可以把几何上的先验知识结合到优化算法中从而更高效地进行处理。
Quasi-Newton Methods
Second-Order Methods
Other Methods
广义参数化及数据降维
球面参数化
除了常见的参数平面外我们还可以使用其它形式的目标区域进行参数化。比如说我们可以把参数的定义域设置为球面，这样可以把封闭曲面映射到球面上，这样的过程称为球面参数化(spherical parameterization)。
相容性网格
更进一步我们可以把一个网格参数化到另一个网格上，即构建两个曲面上的一一映射。这样的过程称为相容性网格(compatible mesh)，在计算机动画中有着重要的应用价值。
体参数化
除了物体表面外我们也可以考虑物体的体积，此时的参数化过程称为体参数化(volumetric parameterization)。
几何映射
从更高的视角来看，只要是从一个域到另一个域的映射都可以看做是某种参数化过程，称为几何映射(geometric mapping)。
以参数曲面为例，尽管曲面上的点都是在三维空间中进行观测的，它们本质上仍然是二维流形上的数据。因此我们可以在二维平面上来处理这些三维空间中的点。
因此参数是数据的本征维度(intrinsic dimension)，曲线曲面的本质都是低维结构在高维空间中嵌入的结果。
不过遗憾的是高维到低维的映射一般会存在信息的丢失，而且寻找数据的本征维度仍然是非常困难的。
高维数据的参数化
在机器学习和数据科学中人们很早就发现很多高维的数据都存在低维的结构。
尽管直接寻找本征维度是比较困难的，我们仍然可以通过一个神经网络来主动将高维数据映射到低维中，这样的过程称为流形学习(manifold learning)或降维(dimension reduction)。
实际上数据降维的过程也可以理解为一种参数化。以自编码器(autoencoder)为例，网络的编码器(encoder)将高维数据映射到低维，即寻找一个参数化；而解码器(decoder)则将低维数据映射回高维，这个过程可以理解为函数拟合。和几何处理中的参数化过程相比，自编码器的特点在于参数化的过程与下游任务密切相关，参数化是与下游任务共同进行训练的。
