按：目前“大数据”、“3D数字化”、“人工智能AI”、“深度学习”、“AR/VR”是数字智能领域的热点研究方向 ，层出不穷的新概念让一般人看的眼花缭乱。

其实，“万变不离其宗”！本【3D智能十八篇】系列共分十八篇，作者吴怀宇（中科院博士、北大博士后）为中国3D科技产业联盟副理事长。每一篇都力求仅以一页纸的篇幅，来系统完整地介绍十八个主要方向 ，深入浅出。以下内容摘自吴怀宇博士2017年新出版的《3D打印：三维智能数字化创造》（第3版）一书，完整内容及详细目录详见链接：点击查看完整目录列表（含购书链接）

往期回看（点击查看）：

【3D智能十八篇之一】形状分析：优化3D打印形状的表现力

【3D智能十八篇之二】立体视觉重建：将照片转成3D数字模型

【3D智能十八篇之三】众里寻她千百度：海量3D模型的形状检索

【3D智能十八篇之四】3D降维攻击：上帝如何优雅地拍扁你！参数化

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

【3D降维攻击：上帝如何优雅地拍扁你！参数化与平滑】

看过《三体》这本科幻巨著的同学都知道，三体世界有一种终极的攻击形式叫做“降维攻击”，是宇宙中的高等文明攻击低级文明的一种方法——硬生生地直接把对方拍扁！

试想：如果有一天，高等级的外星人或者万能的上帝决定对人类做一次毁灭性的惩罚，他极有可能采用今天谈到的“降维攻击”！因为这是一种非常“优雅”的方式，非常贴合他们高逼格的身份，主要体现在三点（简称：“上帝拍扁三定律”）：

1、上帝应当将立体的3D世界完全拍成扁平的2D画面，以体现“世界是平的”这一神谕。

2、拍扁后的你在局部细节与之前的3D形状应该是形状保持（Shape-Preserving）的，比如你的脸被拍扁后仍然要看着像你，不能有扭曲和变形（Distortion），以便上帝想你的时候能够随时睹物思情。

3、拍扁后的形状不能有局部的翻转（Flip）和折叠（Fold），这样上帝把你拍扁挂在墙上时，可以保证迎面看到的都是你白润的皮肤，而不会有血糊糊的东西流露在外面；同时你的单眼皮也不会被拍成叠在一起的双眼皮甚至三眼皮，仍是那完美的单眼皮。

OK。今天我要告诉你的是，上帝在实施这一宏伟计划前，他会努力先学会的一种重要数学工具，它的名字叫：参数化。

A、  3D网格的参数化

一个曲面的参数化（Parameterization）可以看作是该曲面到一个合适域（如平面，盘面、球面，柱面）的一一映射[139]，如图1-9所示。以平面域为例，参数化就是将曲面展平到一个平面，最直接的应用就是CG领域的纹理贴图（如图下边所示的黑白棋盘贴图）。

图1-9  参数化（图片来源：[139, 143]）

典型地，同胚于盘（Disk）的曲面都可以被映射到平面域。而亏格为零的曲面可以被映射到球面域。更一般地，曲面也可以映射到另一个曲面，这时就被称为交叉参数化。几乎所有的参数化都会引入角度或面积上的扭曲误差，因此一个好的参数化应该谋求某种与原始网格之间几何度量的扭曲最小化。其中，最理想的参数化为等长映射（Isometric Mappings，又称保长、保距），即没有任何扭曲，但该映射只在可展曲面的情况下成立。另外两种参数化的目标分别为保角映射（Conformal Mappings）和等积映射（Equiareal Mappings、Authalic Mappings）。注意如果同时满足保角映射和等积映射即为等长映射。

由于等积映射解的不唯一性，人们更多地关注保角映射，因为根据黎曼映射定理（Riemann Theorem)，任何两个拓扑相同的光滑曲面之间都能够满足保角映射（但此定理在离散网格模型上不成立，因为对于三维网格曲面来说，每个顶点相邻的三角形角度之和小于，而在平面上此角度之和一定等于），也即从盘状曲面到固定的单连通平面域几乎一定存在一个（满射）保角映射。

保角映射与调和映射（Harmonic Mappings）紧密关联，因为满足拉普拉斯方程的保角映射即为调和映射。调和映射具有易于计算（其为线性系统）的重要优点。此外，调和映射对于凸区域可以保证是一一对应的。不过，虽然在理想的光滑连续曲面上拥有以上好的性质，但在处理真实的离散曲面上时调和映射却会出现不保角、不保面积、三角形翻转情况。

目前离散调和映射一种比较好的权重为基于均值坐标（Mean Value Coordinates） [140]。该权重基于如下事实：调和函数（或调和映射）满足均值原理（Mean Value Theorem）。类似于三角形的重心坐标，均值坐标是重心坐标在多边形上的扩展。均值权重可以保证为正的，且具有形状保持、低角度扭曲、以及光滑连续依赖顶点位置的良好性质[141]。除了均值权重，还有调和（Harmonic）权重（也被称为Cotangent权值）也比较常用，但在三角形有钝角时该权值可能是负值，从而导致参数化结果不是双射的。

在构造离散调和映射时，需要事先固定边界映射且最好映射到凸边界上。考虑到这些局限性，也有方法直接考虑保角映射（如建立在角度空间上的基于角度平展的线性参数化Linear ABF：Linear Angle Based Flattering），而无需将边界映射到事先固定的凸边界上（但仍需手工选择两个顶点）。这些方法通过将边界也考虑进优化约束之内，即参数域的形状是由方法动态地决定。然而对于 曲率比较大的三维模型，线性ABF可能会导致面片翻转。

除了ABF，还有最小二乘保角映射（LSCM：Least Square Conformal Maps），这是一种准保角（Quasi-Conformal）的算法。通过对柯西-黎曼方程的最小二乘逼近，定义一个使角度变形取得最小值的能量函数，相应得到一个线性方程组。LSCM方法的最优解具有存在性和唯一性，这样避免了局部最优解，且能够比较好地保持原始网格的面积。相对于线性ABF方法能够得到更小的角度扭曲，在保角方面的效果更好。 但LSCM在有钝角的情况下，会出现面翻转的情况；此外，为了使最小化问题有唯一的和非平凡解，必须固定至少两个顶点。

前面提到的参数化方法都需要在约束边界（比如LSCM需要固定至少两个顶点），这样会容易引入形状的扭曲误差（distortion-prone）。而频谱保角参数化（Spectral Conformal Parameterization）是一种自由边界的方法，通过最小化一个离散化的带权重的保角能量，最终数值过程为求解稀疏对称矩阵的最大特征值和特征向量，虽然不是线性系统但运算速度还是很快的，仅比线性算法LSCM慢2～3倍。频谱保角参数化对网格的采样率鲁棒，特别是扭曲比LSCM更小，其结果是保角参数化所能达到的极限。缺点是和LSCM等一样，这种方法也不能保证局部形状不被翻转和折叠（fold-free）。

此外还有局部全局（Local/Global）参数化算法[178]，思路是先把每个三角形“局部地”映射到平面，然后再对所有三角形进行“全局”的缝合，尽可能减少扭曲，包括尽可能相似（ASAP：As-Similar-As-Possible，等 同于LSCM参数化）和尽可能刚性（ARAP：As-Rigid-As-Possible）。把这些“打散的”每个三角形没有扭曲地映射到平面之后，再通过一个稀疏线性系统把所有三角形重新“粘合”连接到一起即可，在这个过程中需保持三角形变换的相似性（Similarity，即保角映射）或者更严格的刚性（Rigidity，即只允许旋转Rotation变换，以获得等距映射和保面积映射）。 为了防止三角面片翻转，可用“凸虚拟边界”算法进行后处理。

除了上面介绍的线性参数化算法之外，还有一些参数化算法是非线性的，例如尽可能保面积的参数化算法MIPS（Most Isometric Parameterization）、基于扭曲受限的参数化、里奇流（Ricci Flow）参数化、基于圆模式（Circle-Pattern）的参数化等等。

提示：

里奇流（Ricci Flow）是哈密尔顿（Richard Hamilton）提出的一种曲率流，被成功用于证明大名鼎鼎的庞加莱猜想（Poincaré Conjecture：单连通的闭三维流型同胚于三维球面）。庞加莱猜想有助于确定宇宙的形状：是零曲率的平坦平面、或是正曲率的球面、还是负曲率的马鞍形双曲面？（根据单值化Uniformization定理，宇宙只会归类于这三种形状，这也从理论上保证了各种曲面的全局参数化）。

       首先我们在流形曲面上任选一个黎曼度量（通过黎曼度量可以计算高斯曲率），然后我们将这个黎曼度量进行连续形变，则高斯曲率也会连续变化且与形变的速率成正比。这个过程和热传导类似，最终高斯曲率达到所有点都一样的（热）稳定状态，成为一个常值曲率。而根据高斯-博内定理，无论如何变形，总的高斯曲率是不变的。
       也即：里奇流共形（保角）地改变黎曼度量，使之最后的目标度量诱导的高斯曲率是常数。因此，里奇流可以“根据目标高斯曲率来设计目标黎曼度量”，给定一个目标高斯曲率，通过改变黎曼度量来调整高斯曲率 ，以便将当前形状保角地映射到目标曲面（比如平面）。
       里奇流的公式：，其中是曲面上的黎曼度量，是高斯曲率。可以看出，里奇流公式和热传导公式类似，随着时间的增加，表面上的温度（高斯曲率）越来越趋向一致，变成常值。

上述方法主要针对平面参数化。目前也提出了许多球面参数化的方法。许多方法尝试构造类似于平面参数化中的保角（或调和）映射，但此时一些线性方法已变成非线性的。此外，根据Gu和Yau[142,143]所提到，从一个封闭亏格为零的曲面到一个单位球面的调和映射是保角的。即对于封闭球面而言，调和映射等同于保角映射。事实上，平面参数化中正是由于边界映射导致了保角和调和映射的不同。而正因为球面没有边界，所以此时两者等价。

更进一步，基于曲面微分几何中最根本的单值化定理（所有封闭曲面都可保角地变换成三种标准常曲率曲面中的一种：欧几里得平面、单位球面、和双曲圆盘，归一化到标准空间分别对应0、+1、-1这三个常数值曲率），里奇流参数化方法可以把三种拓扑映射（针对平面的欧几里得空间、球面的球形空间、孔洞亏格的双曲几何空间）统一到一个框架里面，只要映射前后的高斯曲率之和不变。

B、  3D网格平滑与去噪

上帝在拍扁你之前， 追求完美的他应该会再进行一个额外的辅助步骤：为了保证更完美的观瞻效果，他可能会决定先对你做一个3D平滑，比如将脸上坑坑洼洼的小痘痘之类的滤除掉——是的，上帝内心一直在渴求着那种我就是认真的工匠精神。

为什么要3D平滑？在数据获取过程中，人为的扰动或者扫描仪本身的缺陷使得生成的三维数据带有噪声。网格去噪（Denoising）就是消除三维数据表面的局部几何突变，并在局部范围内保持形状变化的连贯性，如图1-4所示。网格平滑（Smoothing）是在剔除噪声获取离散曲面更高阶光滑性的同时，保持网格模型的拓扑信息和几何特征不变性。网格去噪和平滑等操作可统称为网格光顺（Fairing），字面意思即为使网格表面更好看（Fair）。当然，除了使网格表面更好看，还需满足一定的要求，比如不能破坏数据的精度，这对于医学应用或文化遗产保护来说是必要的。

为了进行网格光顺，我们首先需要定义光顺的度量。光顺能量（Fairness Energies）用来对形状光顺程度进行量化的度量。由于评价曲面外观的内在主观因素以及不同的应用背景，找到一个能普遍接受的光顺度量标准是一项复杂的工作。尽管如此，我们还是可以定义一些具有通常意义的标准，例如光顺能量应该独立于曲面的参数化，在刚体变换和伸缩变换下应保持不变等等。

目前已经提出了不少光顺度量。我们把这些度量按照曲面特征的最高阶导数进行分类。一阶度量为曲面的面积。但因为面积在伸缩变换情况下不能保持不变，Delingette[101]提出使用等周率（Isoperimetric Ratio）作为（封闭曲面的）一阶尺度不变光顺度量，其中代表面积，代表封闭曲面的体积。二阶度量与曲率相关，如曲率项平方的积分。重要的二阶度量有弯曲能量（Bending Energy），总曲率（Total Curvature），以及Willmore能量等等，其中，代表主曲率，代表平均曲率。三阶度量的例子为Moreton和Sequin[102]提出的曲率变分能量。该能量的Euler-Lagrange方程是六阶的，方程的最小化求解变得非常困难。

图1-4  网格平滑与去噪（图片来源：[109]）

提示：

3D曲面的曲率（Curvature）是三维曲面不平坦程度的衡量（直观而言，几何中的曲率就是物理中的力。比如，我们沿着一条空间曲线以恒定速度地开车，所感受到的力就是曲线的曲率）。在欧几里得空间中，曲面的曲率可以通过曲线的曲率来推导。因为经过曲面上的一个点可以有无数个不同方向的曲线，因此曲面上的点在不同方向上有不同的曲率。主曲率为其中的最大值和最小值，记作和，而且曲面上每个点的两个主曲率方向总是互相垂直的。

       高斯曲率为两个主曲率之积，因此高斯曲率的正负反映了曲面上点在不同方向上弯曲方向是否相同。平均曲率是两个主曲率的平均值，也是所有曲率的平均值。高斯曲率与平均曲率的本质差别在于：高斯曲率是3D模型的内蕴曲率，不需要（更高维度的）外部的嵌入空间就可以计算得出；而平均曲率表示了3D模型在外部嵌入空间里的弯曲程度，因此可用于网格平滑等几何操作，如降低平均曲率可使3D模型变得更光滑。
       高斯-博内定理（Gauss-Bonnet Theorem）是微分几何学中的一个经典定理，阐述了曲面局部和全局特征之间的关系。我们知道，高斯曲率是个内蕴的局部特征，而欧拉示性数（见6.4.3节）是3D模型的全局拓扑特征，高斯-博内定理给出了两者间的关系：任何曲面上的高斯曲率之和等于乘以这个模型的欧拉示性数，即任意曲面的高斯曲率之和由欧拉示性数决定。以离散的三角曲面为例，该公式可表示为：
                         
其中，表示内部节点不除以面积的高斯曲率，表示边界节点不除以面积的高斯曲率，是曲面的欧拉示性数。

在已经定义了光顺度量之后，下一步的目标就是要如何提高网格表面的光顺程度，即如何演变（Evolving，或称为扩散）曲面使其不断单调地减低光顺能量。整个变化的过程可以看做是热传导的过程，也就是三维模型上的曲率变化和热传导的过程类似，从大的地方向小的地方传递，随着时间的推移，慢慢整个三维模型上的曲率趋向于一致。该过程通常需求解非线性抛物线偏微分方程（Parabolic Partial Difftial Equation）。演变或扩散的一般形式为，其中为Laplace-Beltrami操作符。基于该形式的平滑方法一般统称为Laplace平滑。

一般的Laplace平滑方法有Taubin的经典方法[103]，还有平均曲率流[104]，即面积函数的梯度流使网格的每一个顶点沿着法线方向进行扩散，因为扩散的速度与平均曲率（Mean Curvature）相等，故被称为平均曲率流。在具体的数值计算中，可以采用显式欧拉（需要多次迭代）或者隐式欧拉（需要求解线性方程组）的方法得到稳定的数值解。

提示：

客观世界的物理量一般是随时间和三个维度空间位置等多个变量而变化的，因此几乎所有物理规律的终极形式都是偏微分方程，现代三维几何中的基本定理也是依赖于偏微分方程。偏微分方程（Partial Differential Equation，PDE）：即微分方程中出现多元函数（如时间、温度、密度、三个维度的空间等）的偏导数（若未知函数只含一个自变量则叫做常微分方程）。

       PDE一般包括椭圆型偏微分方程、抛物型偏微分方程、双曲型偏微分方程三大类，基本类型有拉普拉斯Laplace方程（椭圆型PDE，其解称为势函数或调和函数）与泊松（Poisson）方程、位势方程（椭圆型PDE）、热传导方程（抛物型PDE）、波动方程（双曲型PDE）等。就物理现象来说，各个具体问题的特殊性就在于研究对象所处的特定条件，就是必须考虑PDE方程的（柯西Cauchy）初始条件和边界条件（包括狄利克雷Dirichlet边界条件、纽曼Neumann边界条件、以及两者的线性组合即罗宾Robin边界条件）。
       绝大多数PDE的解不能以解析形式来表示，因而数值解法就显得尤为重要，包括有限差分法（即数值微分，有显式方法与隐式方法）和有限元法（即函数插值，属于变分法），都是将连续的PDE方程进行离散，采用适当形式将其转为线性方程组，并求出数值解。此外，数值解法还有谱方法、边界元法、有限体积法（数值积分）等。
       以黎曼流形曲面上的热传导为例，数学上采用一个偏微分方程来描述：，其中：表示温度，是Laplace-Beltrami微分算子（参见本章6.6节）。热传导方程具有将初始温度平滑化的性质，即随着时间将热从高温处向低温处平滑扩散。
       这里，我们可采用热核（Heat Kernel）函数[183]函数来表示在时间时从点（经过各种随机行走路径，实际上热扩散可看成是曲面上各向同性的布朗运动）传递到点的热量总和，热核有如下的特征分解形式：
                     
其中,,…是Laplace-Beltrami算子的特征值，,,…是对应的特征向量，满足。基于热传导方程，热核函数可以描述一个点周围的局部几何信息，也可通过调大扩散时间来获得全局的几何信息，具有等距不变性（Isometry）、多尺度性、信息存储性（局部形状的辨识区分性）、稳定性等优良特性。
       当时间很小时，点的热核函数的值与该点的高斯曲率的值直接相关，由此可以看出热扩散的一个特点：如图1-5所示，曲率越大、热量就扩散得越慢，即热量集中在曲率较高的区域；热量在正曲率的点附近扩散得慢些，而在负曲率的点附近扩散得快些。因此我们可以利用这些特点来检测物体外形的凹凸特征或确定特征点。

图1-5  利用热核函数来检测形状的特征（图片来源：[183]）

Laplace平滑的缺点在于它会快速地将几何特征（如尖角）平滑掉。而各向异性扩散（Anisotropic Diffusion）[105]通过抑制高曲率方向上的扩散来对尖锐特征进行保持甚至增强。各向异性扩散由图像处理中的Perona Malik滤波演化而来。另一种相关的技术，双边（Bilateral）滤波，也已被引入到网格平滑当中。

另一大类重要的光顺算法为基于约束的光顺（Constrained Fairing）。为了评价一个光顺方法，除了光顺程度（即光顺能量尽可能小）之外，还有一个重要的标准是结果曲面与原始曲面的偏离误差，比如Belyaev和Othake[106]使用平方距离的积分和法线的均方差来比较不同平滑方法的结果好坏。为了减小偏离误差，还需要对光顺进行一定约束，即基于约束的光顺。Sorkine等人[107,108]提出最小平方网格（Least-Square Meshes），该方法最小化两个二次能量的加权和，一个为双调和（Biharmonic）能量，另一个能量为每一个顶点与初始位置距离的加权平方之和。Hildebrandt等人[109]提出了一种基于离散弯曲能量的组合约束方法，并通过活动集牛顿法（Active Set Newton Method）进行有效求解。

好了，今天的话题就到这儿，相信您以后在迎接上帝的“如来神掌”拍扁时届时一定会更加从容。