GAMES301课程笔记02-面向离散网格的参数化概述

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

Mesh-Based Mappings

Discrete Meshes

离散网格由顶点(vertex)、边(edge)以及面(facet)组成，其中顶点的位置描述了网格的几何而顶点之间的连接关系则描述了网格的拓扑。

常见的离散网格包括三角形网格、四边形网格、四面体网格以及六面体网格。其中三角形网格和四边形网格只包含物体的表面，而四面体网格和六面体网格则填充了物体的内部。

Mappings

离散网格上的映射是指网格到网格的映射。理论上网格的几何和拓扑都可以称为映射的对象，不过在大多数情况下我们都不会改变网格的拓扑关系，因此这里假定网格上的映射是改变顶点坐标的函数。

对于线性网格(三角形网格)，映射在每个面片上都是一个线性映射，此时整个网格上的映射是一个$C^0$连续的分片线性映射。这里需要注意的是四边形网格和六面体网格都不是线性网格，对应的映射也不是线性映射。

在本课程中我们大多数情况下只考虑线性网格和线性映射。以二维平面上的映射为例，假设平面上的三角形$t$经过$f_t$映射为三角形$T$。由于映射是线性的，三角形的顶点坐标变换可以表示为线性函数：

$$f_t(\mathbf{x})={\mathbf{J}}_t\mathbf{x}+{\mathbf{b}}_t$$

实际上变换矩阵${\mathbf{J}}_t$即为映射的Jacobian矩阵：

$${\mathbf{J}}_t=\left[\begin{array}{cc}\frac{\partial u}{\partial x}& \frac{\partial u}{\partial y}\\ \frac{\partial v}{\partial x}& \frac{\partial v}{\partial y}\end{array}\right]$$

我们可以通过构造线性方程组的方式来求解${\mathbf{J}}_t$：

$${\mathbf{J}}_t=\left[\begin{array}{cc}{u}_j-u_i& u_k-u_i\\ v_j-v_i& v_k-v_i\end{array}\right]{\left[\begin{array}{cc}{x}_j-x_i& x_k-x_i\\ y_j-y_i& y_k-y_i\end{array}\right]}^{-1}$$

而且${\mathbf{J}}_t$的行列式恰为映射后三角形$T$的面积除以映射前三角形$t$的面积。

对于四面体网格同样有类似的结论：

Distortion

我们希望映射前后三角形的各种几何量不要发生太大的扭曲。能够保证三个夹角保持不变的映射称为共形映射，保证面积不变的映射称为等积映射，而同时保证夹角和面积的映射则称为等距映射。

为了描述线性映射的行为我们需要引入SSVD，它是SVD的推广。SSVD说明线性映射可以分解为旋转和缩放的复合。

利用SSVD对${\mathbf{J}}_t$进行分解，两个奇异值刻画了线性映射的性质。如果两个奇异值都为1则说明映射为等距映射，如果两个奇异值相等则说明映射是共形映射，而如果两个奇异值的乘积为1则说明映射是等积映射。

更进一步，几何扭曲也可以使用映射的奇异值进行描述。很多参数化算法的本质都可以理解为使用两个奇异值来构造优化问题。

Constraints

我们要求映射前后三角形不能发生翻转，因此Jacobian矩阵${\mathbf{J}}_t$的行列式必须恒为正。

除了没有翻转之外，映射还需要满足局部单射(local injective)的条件。这里需要说明的是局部单射与没有翻转是不完全相同的概念，局部单射要求对于边界上的顶点其内角和需要小于$2\pi$。

类似地，我们希望映射能够满足全局单射(global injective)的条件。这表示映射后每一点都满足局部单射，不会出现自相交的情况。

这样求解几何映射就可以表示为带约束的优化问题，其目标函数包括几何扭曲以及一些额外的度量，而约束则包括基本约束(无翻转、无自交)和实际问题的约束(位置约束、边界约束等)。

而优化问题在求解上的困难在于在大多数情况下它都是一个非凸非线性的优化问题。

Mesh Parameterizations

回到曲面参数化的问题上，参数化可以理解为三维到二维的一一映射。对于网格上的每个顶点，其三维坐标使用$(x_i,y_i,z_i)$来表示，而参数化后的坐标使用$(u_i,v_i)$来表示。

参数化在整个CG行业有着非常多的应用，纹理映射、计算机动画、重新网格化等许多任务都依赖于参数化的结果。

显然对于参数化我们也希望它具有低扭曲和无自交(全局单射)的性质。

Tutte’s Embedding

Tutte参数化是最常见的参数化方法。可以证明对于拓扑同胚于圆盘的网格，如果我们把网格的边界按顺序映射到一个凸多边形上并且内部顶点坐标是相邻顶点的凸组合，那么网格映射到平面后就是一个无翻转、无自交参数化。

通过求解(稀疏)线性方程组就可以得到参数化后的网格。当然Tutte参数化没有考虑任何形式的几何扭曲，因此Tutte参数化可能会出现各种挤压和扭曲的情况。

Representative Methods

为了解决几何扭曲严重的问题，人们开发了各种不同的参数化方法。这里介绍三种经典的算法ABF、LSCM以及ARAP，需要注意的是这些算法都没有考虑全局单射的要求。

Angle-Based Flattening

ABF是基于三角形内角的参数化方法。如果我们已知三角形的三个内角以及任意一条边，那么就可以恢复出三角形的形状。因此ABF的核心思想在于计算参数化后每个三角形上三个内角的大小，再通过内角来实现参数化。

因此ABF的优化目标如下：

而对应的约束包括：

• 任意内角大于0：${\alpha }_i^t>0$
• 同一个三角形上内角和为$\pi$：${\alpha }_1^t+{\alpha }_2^t+{\alpha }_3^t=\pi$
• 参数化后内部顶点的内角和为$2\pi$：$\sum _{t\in \mathrm{\Omega }(v)}{\alpha }_k^t=2\pi$
• 重建约束，可以由正弦定理导出：$\prod _{t\in \mathrm{\Omega }(v)}\sin {\alpha }_{k\oplus 1}^t=\prod _{t\in \mathrm{\Omega }(v)}\sin {\alpha }_{k\ominus 1}^t$

显然重建约束是非常难以进行处理的，因此在linear ABF中使用了线性化的技巧来进行化简。首先对参数平面上网格的内角进行分解：

$${\alpha }_i^t={\gamma }_i^t+e_i^t$$

其中${\alpha }_i^t$为参数化后的内角，${\gamma }_i^t$为原始网格上的内角，$e_i^t$为估计误差。通过对对数函数进行泰勒展开可以得到：

$$\log (\sin {\alpha }_{k\oplus 1}^t)\approx \log (\sin {\gamma }_{k\oplus 1}^t)+e_{k\oplus 1}^t\cot {\gamma }_{k\oplus 1}^t$$

线性化之后就可以把原始优化问题转换为线性约束下的凸二次优化，存在解析解。

求解优化问题后就需要通过角度来恢复参数化，一般有两种方法来实现。

在贪心方法中我们首先需要选择网格上的一个三角形，然后固定其中一条边来确定整个三角形的位置。然后以它的任意一条边作为已知量，通过DFS的方式来恢复相邻的三角形直到网格上所有的三角形都确定了位置。需要注意的是这种方法存在数值上的累积误差，得到的网格质量一般都比较差。

另一种恢复参数化的方法是通过构造一个最小二乘问题来进行处理。根据正弦定理可以构造出三角形顶点坐标需要满足的约束条件：

$${\mathbf{M}}^t({\mathbf{P}}_k-{\mathbf{P}}_j)+{\mathbf{P}}_j-{\mathbf{P}}_l=\mathbf{0}$$ $${\mathbf{M}}^t=\frac{\sin {\alpha }_k}{\sin {\alpha }_l}\left[\begin{array}{cc}\cos {\alpha }_j& -\sin {\alpha }_j\\ \sin {\alpha }_j& \cos {\alpha }_j\end{array}\right]$$

对网格上所有三角形进行遍历就可以构造出一个线性系统，其最小二乘解即为所需的参数化顶点坐标。除此之外，我们还需要固定具有公共边的两个相邻顶点来避免出现奇异的情况。

Least-Square Conformal Mapping

LSCM是基于共形映射的参数化方法。对于二维平面的情况，当映射为相似变换时Jacobian矩阵${\mathbf{J}}_t$可以分解为缩放因子$s$乘以旋转矩阵：

$${\mathbf{J}}_t=s\left[\begin{array}{cc}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right]=\left[\begin{array}{cc}\frac{\partial u}{\partial x}& \frac{\partial u}{\partial y}\\ \frac{\partial v}{\partial x}& \frac{\partial v}{\partial y}\end{array}\right]$$

因此有：

$$\{\begin{array}{l}\frac{\partial u}{\partial x}=\frac{\partial v}{\partial y}\\ \frac{\partial u}{\partial y}=-\frac{\partial v}{\partial x}\end{array}$$

上式即为复变函数中的Cauchy-Riemann方程(Cauchy-Riemann equation)。

由于几何扭曲的存在，我们很难严格保证Cauchy-Riemann方程的成立。因此可以构造出共形能量：

$$E_{LSCM}=\sum _t{A}_t[(\frac{\partial u}{\partial x}-\frac{\partial v}{\partial y}{)}^2+(\frac{\partial u}{\partial y}+\frac{\partial v}{\partial x}{)}^2]$$

通过最小化$E_{LSCM}$来实现共形参数化。当然为了避免奇异的情况，我们同样需要固定网格上的两个顶点。

As-Rigid-As-Possible

ARAP的思想是希望Jacobian矩阵${\mathbf{J}}_t$尽可能接近于一个旋转矩阵或是相似矩阵，因此可以直接利用${\mathbf{J}}_t$来构造优化目标函数：

$$E(u,L)=\sum _t{A}_t\Vert {\mathbf{J}}_t-{\mathbf{L}}_t{\Vert }_F^2$$

ARAP在进行优化时需要同时考虑二维参数化坐标以及目标变换矩阵${\mathbf{L}}_t$，因此需要使用交替迭代的方式来进行求解。整个优化过程可以分为local step和global step两步，在local step中固定二维参数化坐标来求解目标变换矩阵，而在global step中则固定${\mathbf{L}}_t$来求解参数化坐标。其中global step可以表示为一个凸二次优化问题，只需要求解线性系统即可。

而local step还需要一些额外的处理。首先需要构造一个最接近于${\mathbf{L}}_t$的Jacobian矩阵。利用SSVD，${\mathbf{L}}_t$可以近似为：

$${\mathbf{J}}_t=\mathbf{U}\left[\begin{array}{cc}s& 0\\ 0& s\end{array}\right]{\mathbf{V}}^T$$ $$s=\frac{{\sigma }_1+{\sigma }_2}{2}$$

因此ARAP的求解步骤可以理解为首先为网格上的每一个三角形构造一个刚体变换，然后再为每一个顶点赋予坐标来实现参数化。

从奇异值的角度来看，ARAP的总体优化目标函数取决于${\mathbf{L}}_t$所对应的映射形式。

Reference

• Lecture 02：面向离散网格的参数化概述