浅谈曲面参数化-算法和理论（II）

时代的要求

二十世纪九十年代，计算机图形学技术异军突起，特别是GPU技术的发明和普及，使得CG电影工业和电子游戏产业蓬勃发展。在GPU中，曲面数据处理被分成两条流水线，一条处理曲面的几何数据和几何变换，例如曲面的平移旋转，射影变换等等；另外一条处理曲面的纹理信息，例如颜色、法向量场、局部几何细节鳞片结构，局部材质特性BRDF等等。几何数据结构一般是多面体三角网格，纹理数据结构一般是平面图像。在图形渲染过程中，两条流水线的处理结果相互融合，将平面的二维纹理粘贴到弯曲的三维曲面上，这一技术被称为是纹理贴图。

Fig 1. 曲面参数化。

Fig 2. 曲面纹理贴图。

纹理贴图技术在数学上等价于求从曲面到平面区域的一个光滑双射，这被称为是所谓的曲面参数化问题。如图1所示，我们将各种曲面映射到平面区域，然后在平面参数区域上贴上纹理图像，通过逆映射将纹理图像拉回三维曲面。如图2所示，我们将大理石纹理贴在米开朗基罗的大卫王头像上面，从而获得了大理石雕像的质感。

Fig 3. 保角参数化。

参数化不可避免地会带来畸变。通常，映射的畸变可以归为两类：角度畸变和面积畸变。角度没有畸变的映射，被称为是共形变换，或者保角变换；面积元没有畸变的映射，被称为是保面积变换。图三显示了一个保角参数化的实例。这一映射将一三维人脸曲面映射到平面圆盘上。我们在人脸曲面任意画两条相交曲线，这两条曲面上的空间曲线被映射到平面上的两条曲线，空间曲线的交点被映成平面曲线的交点，在交点处，空间曲线的夹角等于平面曲线的交角。这两条空间曲线任意选取，其交角被映射完美保持。

Fig 4. 保面积参数化。

图4显示了保面积参数化的一个实例。同样的人脸曲面被映射到平面圆盘，通过整体缩放变换，人脸曲面的总面积等于平面圆盘的总面积。我们在人脸曲面上任选一个子区域，映射将映射到平面一个区域，则曲面上的区域面积等于平面区域的面积。曲面参数化的一个长期目标就在于寻求严格而实用的算法，计算保角和保面积的映射。

在纹理贴图技术被发明之前，计算机图形学所需要的较深数学技巧包括矩阵求逆、旋转群的四元数表示（quaternion）和渲染算法背后的积分方程、不动点理论；纹理贴图技术出现之后，曲面参数化需要更为深入的代数拓扑和微分几何的理论支撑。但是，绝大多数计算机科学系的基础课程都不包括代数拓扑和微分几何，这为年轻的学生理解跟踪曲面参数化领域的研究增加了难度。

研究的范式

在过去的二十年间，曲面参数化领域蓬勃发展，各种算法层出不穷，出现了百花齐放、百家争鸣的局面。海量的研究成果既有极其具有原创性的突破，也有拾人牙慧的跟风之作，更有人为运作的学术泡沫。这方面的工作需要长久的时间来蒸馏，二十年时间依然太短。我们试图在各种流派中寻求统一的研究模式，并且对于各种研究范式加以比较。

第一种研究范式比较工程化：首先将映射的质量要求表述成数学公式，然后通过积分这些公式来设计出相应的能量，运用常见的优化方法来优化能量，从而得到曲面参数化结果，最后选择几个算例和其他方法比较来彰显所提出算法的优越性。这种方法基于经验，简单直观，容易实现，绝大多数的工作遵循这一范式。这种方法无法保证解的存在性，唯一性和光滑性，缺乏全局拓扑观点，无法揭示几何现象的深刻层面。

第二种研究范式基于连续理论的离散逼近：首先深刻理解相应的经典几何理论；将光滑曲面、光滑映射进行离散逼近，将光滑情形的偏微分方程用离散解来逼近，或者将光滑情形的变分问题转化成离散能量优化问题，求得离散解；然后估计逼近误差，证明收敛阶。这种方法具有严格性，但是需要应用数学方面的训练，例如有限元方法，偏微分方程理论等等。并且，这种方法比较适用于线性椭圆型偏微分方程，对于几何理论中出现的大量非线性偏微分方程，传统的有限元方法依然无能为力。

第二种研究范式直接建立离散的几何理论，传统的几何理论是建立在光滑流形基础之上的，需要曲面的微分结构，离散几何理论建立在多面体网格之上，然后证明离散曲面无限细分之后，离散理论导出光滑理论。这种研究范式对于非线性几何偏微分方程非常有效，同时给出了经典理论的一种全新理解方式。但是，因为缺乏成熟的数学工具（例如第二种范式中的伽辽金方法），这种研究具有很大的挑战性。

目前来看，在现实生活中，第一种研究范式的成果被工程类学术界广泛接受，并在工业界被广泛应用。但是因为缺乏严格性会被数学领域所拒绝；第二种研究范式和第三种研究范式的成果会被数学界接受，但是因为内容艰涩，逻辑曲折，很少会被工业界直接采纳。许多计算机科学家认为，那些被大型公司所采纳的算法会日渐胜出；许多数学家坚信，从长远来看，依随岁月流逝，大浪淘沙，具有普适性和严格理论保证的方法会被保留下来。

工程化的研究方法

计算机只能表示离散数据，光滑的曲面一般用分片线性的多面体网格（Piecewise-linear Polyhedron）来逼近，又称三角网格（Triangle Mesh），离散曲面（discrete surface），曲面之间的映射，用分片线性映射（Piecewise linear mapping）来逼近。这种表示方法是自然的，并且具有理论依据。在代数拓扑中有一条单纯逼近定理（Simplicial Mapping Approximation），大意是说任何连续映射，都可以在适当的三角剖分下，用单纯映射来逼近。给定任意的逼近精度要求，我们可以动态加细三角剖分，使得单纯映射满足精度要求。在理论和算法层面，几何逼近论着重研究下列问题：对于给定的光滑曲面和逼近精度要求，如何选取相应的三角剖分，构造离散的三角网格，使得在不同的度量意义下离散曲面和光滑曲面之间的“距离”小于给定阈值。这方面已经具有成熟的结果，例如Normal Cycle理论。但是对于给定光滑曲面间的光滑映射，并不存在统一系统的理论结果，绝大多数情况下依赖于所采用的方法，有各种各样的理论估计。

线性映射 工程上对于曲面参数化问题研究的思路如下：曲面到平面区域的映射被表示成分片线性映射，通过对每一片线性映射进行分析，我们可以掌控整个映射。因此，我们首先来分析两个（欧式）平面三角形之间的线性映射，。源欧式平面的坐标记为，内积为

,

目标欧式平面的坐标记为，内积为

。

通过平移，线性映射可以用矩阵来表示：

。

如果映射非退化，则矩阵满秩，；如果映射保持定向，则矩阵行列式为正，。下面的讨论中，我们假设满秩，具有正值行列式。对于线性映射的细致分析，我们通常用矩阵的奇异值分解。

QR分解 给定矩阵，则为对称正定矩阵，因此存在分解

,这里为正实数。由此，我们可以定义的平方根：

。显而易见：

,

这里，同时。我们直接计算

,

因此矩阵是旋转矩阵。因此矩阵被分解为对称正定矩阵和旋转矩阵的乘积，这被称为矩阵的QR分解。

由矩阵的QR分解，我们直接得到矩阵的奇异值分解

,

即矩阵可以被分解为旋转阵，对角阵，旋转阵的乘积。这里被称为是奇异值，为正值实数。

线性映射分类 根据矩阵奇异值，我们可以将线性映射分类：

1. 等距变换，如果，则矩阵为旋转阵，线性映射保持内积不变，换言之，。

2. 相似变换，如果，则矩阵为旋转阵乘以一个标量，。相似变换保持形状不变，因而可以被视为是共形变换的特例；相似变换保持角度不变，又被称为是保角变换的特例。相似变换并不保持面积，其面积元变化率为，

   ，

   相似变换诱导的内积变换为

   。

3. 保面积变换，如果，则矩阵为

   ,

   面元保持不变， 。

   我们可以看到，等距变换必为保面积变换；如果一个线性映射既是相似变换，又是保面积变换，则此变换必为等距变换。

4. 拟共形变换，一般情况下矩阵奇异值不等，源平面上取一个标准圆，我们考察其像，

   ,

   我们进行坐标变换

   ，

   则标准圆的像为一椭圆

   

   椭圆的偏心率由奇异值所决定。如果椭圆为圆，则拟共形变换为共形变换。

5. 变换的极分解，矩阵的QR分解具有更为深刻的理解。假设，这里矩阵是旋转矩阵，可以视作是保面积映射。构造映射，

   ,

   则。
   

   是一个正定矩阵，它代表了一个最优传输映射（Optimal Mass Transportation Map），，

,

        更进一步，变换是某个凸函数的梯度映射，这里凸函数

。

        可以证明，1）映射将面积元映成面积元

,

        同时，在所有满足条件1）的映射中，极小化如下的传输代价：

,

        这里是任意一个紧凸集。

非线性推广 以上线性映射的分类结果可以（非平庸地）推广到曲面映射情形，基本想法如下。假设给定带度量的曲面间的光滑映射，局部上，非线性的映射可以用其一阶近似，切平面间的线性映射来逼近，所谓的导映射（derivative map）

，

会带来各种畸变，这些畸变的测量需要用到黎曼度量。线性映射的分类可以利用上述线性映射分类的想法，例如：如果对于任意一点，都是等距（或者保角，保面积，拟共形），则整体上是等距（或者保角，保面积，拟共形）。但是，最优传输映射（Optimal Mass Transportation Map），映射的极分解，极值拟共形变换等等，本质上是整体的，局部上的理解无法诠释其内在实质。相应的共形几何（保角映射），最优传输（保面积映射），泰希米勒理论（极值拟共形映射），我们会在后继的博文中阐述。

直接变分法 在计算机图形学的曲面参数化领域，有许多工程化的研究方法，可以归为第一类研究范式。这种方法的基本思路如下：我们用分片线性映射来表示从三角网格到平面区域的映射， 。固定一个三角形 ，我们将其铺到平面上，我们用来表示顶点的平面坐标，用来表示顶点像的平面坐标，则线性映射矩阵可以直接写出：

,

这一映射和保角映射的差距可以定义为：

,

如果 为0，则限制在此三角形上的线性映射为保角变换。整个映射和等距变换的差距定义为：

,

这里代表相应三角形的面积。然后，我们运用非线性优化方法来优化这个能量，并将所得结果作为全局保角变换的近似：

。

如果我们的目的是寻求保面积变换，我们可以如法炮制

。

如果目的在于等距变换，那么我们可以定义局部能量

,

等价地

。

在实际探索中，如何定义能量和如何优化能量成为研究的着力点。在理想情形下，我们希望能量为凸能量。

优缺点分析， 这种工程化的研究方法比较简单直观，只需要线性代数的知识，很多时候也确实有效因此在工程领域被广泛承认。同时，这种方法在理论方面存在缺陷：如果能量非凸，如何保证优化方法达到全局最优？即便是我们能够达到全局最优点，我们能够判定光滑情形的保角变换是否存在？如果真正存在光滑的保角变换，如何给出定量的误差分析？这种方法对于映射边界的控制如何，是否可以处理复杂拓扑曲面，对于所求映射的存在性，唯一性和光滑性，这种工程化的方法无法给出严格的答案。

从某种角度而言，线性代数的工具使得我们可以精确地描述问题，提出问题。爱因斯坦曾经有一句名言，大意是对于一个真正有意义的问题，绝不可能在提出问题的层面解决，换言之，解决问题的层面要比提出问题的层面更为深刻。因此，曲面参数化需要更为严密而深邃的理论支撑。

我们将在下一讲解释第二种研究范式，包括调和映照理论，及其几何有限元方法的近似。这种方法具有严格的理论基础，但是无法涵盖更为复杂的非线性现象。

---