【GAD翻译馆】游戏编程中的数学——调和函数和中值坐标
翻译：王成林(麦克斯韦的麦斯威尔) 审校：黄秀美（厚德载物）
下午好！很高兴看到在“游戏编程中的数学”主题演讲中看到这么多的观众！我们今天有很多很棒的演讲者，而我的任务是做一些向量微积分将大家吓走！在开始前先提醒几点：首先如果你有手机，请将其设为静音。其次，如果你在进场时扫描了徽章，那么你会收到一封邮件，其中包含一个问卷调查，请填写它。我会收到调查的结果，不过我可能会和去年一样忽视它们！不过有的回答非常好，请大家都好好回答。
好了。我叫Nicholas，今天我要谈谈调和函数以及中值坐标。这个演讲据官方描述包含了很多内容，但是实际上重点是对于形状的理解。形状非常复杂。这里这个CG形状是著名的bunny兔，我们已经见过它很多次了。
问题是，当我们在处理一个形状时，假设你在进行纹理生成，或者建模，或者程序化内容生成——这会是今年的一个热点话题，在下午三点的“程序化”主题会议中会涉及——那么你要懂得如何获取这个形状，以及告诉计算机如何有意义地理解这个形状。你不希望直接这样做，因为对于该形状总体结构的理解需要很多代数拓扑和微分拓扑方面的知识，如果不会这些的话你将无法处理它们。我们今天也不会探讨如何将这些形状存储在计算机上，随后Geno的演讲会讲到。希望你可以看看，那将非常有趣。
好了，以下是今天演讲的主题。我们不通过一个形状含有的三角形以及顶点理解它，而是在三角形网格物体上建立一个函数。我们希望该函数有指定的性质，可以有助于解决我们面临的难题。我们构建函数使其拥有指定特性，将其放在网格物体上。然后我们可以推导出函数。在某种意义上讲函数要比一个随机三角形网格物体更好。那么今天我们介绍用于几何物体处理过程中使用的两个标准工具。这些不是原创的工具，不是我发明的，这些工具是90年代后期产生的，而其数学原理本身要追述到18、19世纪了。不过和我教育生涯中讲过的很多内容一样，它们没有受到游戏社区足够的重视。所以这就是我们今天要讲的内容。我们将介绍两个在形状上建立函数的方法。第一个是调和函数，第二个是中值坐标。
首先第一个，调和函数。
我们谈谈我们想要什么。给定一个三角形网格物体M，我希望在上面放置一个标量函数——即浮点数，不是向量函数，有可能GDC2018会涉及到它。那么现在该形状上有一个标量函数，我希望它是光滑的，目前仅凭直觉理解这个词就好。在网格物体上的一些位置我希望控制函数的数值。所以我定义了一些点的函数值，然后在物体的其它位置平滑地混合。我们考虑以下类比。
这里有两只兔子。假设我有一个维持在低温的物体。我将它放在兔子的耳朵上。假设我还有一个维持在高温的物体，比如它的温度一直是100度，我将它放在兔子的尾巴上。然后我等一下。过了一段时间，高温物体周围区域的温度会更高，而低温物体周围区域的温度会更低，该物体上的热量从高温向低温平滑地转移。这是我们尝试实现的效果。在现实世界中随着时间的推进它会达到平衡状态。这个过程符合热传导方程，它是一个偏微分方程，应该是你的偏微分方程这门课中遇到的第一个例子。在计算机中我们希望在一个三角形网格物体上实现这个效果。
那么首先我们谈谈光滑的定义。因为这是一节数学课，我们使用数学语言来定义这个词。我们希望代表网格物体的函数是连续的，即标准意义下的连续。也许你还记得微积分课上是怎么定义连续的。我们不希望它有任何跳跃，或者有任何不连贯的地方，或者任何奇怪的过渡。我们希望函数的变化也是光滑的，即该函数的导函数存在且连续。我们不希望函数在短距离内有任何巨大的变化。另外我们也不希望函数有任何局部最大值或最小值，例如它可能表示的是一个局部很热或很冷的点，而这不太合理。我们不需要这些局部极值因为我们不能控制它们。
定义的函数不要有突然的变化。关于多变量微积分你可能学过梯度算符。一个向量函数的梯度指向的是函数最大的变化方向。不过对我们而言，我们更关心梯度的长度而不是它的方向。我们不希望函数在某点有巨大的变化，也就是说我们希望将函数各点处的梯度降到最低。那么我们该如何最小化呢？对于函数的每一点，我们希望取梯度的大小，或者梯度平方的大小，都可以。我们将物体分成很小的区域，然后将每个区域上的内积加在一起，结果得到了物体表面的曲面积分。该积分被称为函数f的狄利克雷能量。（这是个德语名字，所以如果我的发音错了请原谅我。）这是变分法早期研究的一个问题。
我们不希望函数有任何局部最大值或最小值，这意味着我们希望函数梯度的散度为0。这是因为如果函数某点的梯度的散度大于0或者小于0，这意味着函数会形成局部最大或最小值。如果我们将梯度的散度写下来，我们会得到这里这个函数各变量二阶偏导之和。该方程被称为拉普拉斯方程，通常人们使用这个倒三角表示它。如果函数f的拉普拉斯算符在其定义域内为0，那么我们称其为调和函数。很明显，如果拉普拉斯为0，那么上一张幻灯片中它的积分会得到一个常数。另外还有一种简单的情况：常量函数也会最小化狄利克雷能量，因为它任意位置的梯度都为0。
狄利克雷能量以及拉普拉斯方程本身都很无聊，我们要加入一些条件使其有趣起来：在我们的三角形网格物体上，我们设置两个点的值，a和b，其中a<b。如果你是数学家或者物理学家，你会将这种情况称为狄利克雷边界条件。我们不是很在乎。我们只是设置函数的几个点来控制它的性质。数学中有一个著名的强极大值原理（Strong Maximum Principle）：如果f在除边界以外的其它区域内为调和函数——在这个例子中函数的边界即为控制点——我们取物体上的任意一个圆盘（你可以画一个小圆圈来代表圆盘），则该圆盘范围内的函数的最大值和最小值一定在圆盘的边界上。所以最大值和最小值不会出现在圆盘中，而是在圆盘的边界上。你可以物体上选择任意圆盘，这个性质都成立。这是关于物体上的函数的一条强有力的定理，它使我们可以通过研究物体上的函数来研究物体本身。具体来讲，在我们这个例子中，如果我们将网格物体边界设为最大值和最小值，那么该函数的最大和最小值只会出现在这些边界上，其余位置则在极值之间平缓地过渡。那么我们该如何建立该函数呢？这是一个连续的函数，意味着它在任意曲面上都有定义，它的拉普拉斯算符应该为0。我有幸参加了去年的演讲，其中我提到了一个离散化的拉普拉斯算符，叫做网格拉普拉斯算符。它的作用是在一个三角形网格物体上建立一个离散函数。最终你会得到一个线性方程组，其中包含很多的方程。你将其输入到常用的线性方程组求解工具中就可以得到答案了。我不会花时间介绍网格拉普拉斯算符的具体推导过程，因为说实话你只需按照指导书上的步骤走就可以了。我们不希望过多涉及推导过程中所用的机制，你只需知道这个算符的存在以及在哪里使用它就足够了。不过我也许会将推导过程放在幻灯片里发布到网上。
推导的方法在这里简单介绍一下：假设已知调和函数f及网格物体各顶点，某一顶点的离散拉普拉斯等于从该点到相邻顶点的距离的加权求和。你要为它选择一个合适的权。去年我讲对于这个应用我们可以使用均匀加权（uniform weight），今年我说应该使用余切加权（cotangent weights）。使用余切加权是因为我们观察到一个底边朝下的三角形的宽高比等于内角的余切。这里我们在构建离散拉普拉斯时取这些宽高比的平均值。
去年我们使用了矩阵形式的拉普拉斯。我们取物体的拉普拉斯算符，构建微分表达式，选取几个定点，然后在定点条件下计算矩阵的逆，然后做一个最小平方优化以创建一个光滑的变形物体。今年我们无需这样做。
不过关于去年的演讲我们要记住在解决最小二乘问题时，假设我有一些线性方程，比如Ax=B，其中A是一个矩阵，b是一个各分量为已知常数的列向量，x为未知数。你希望使b和Ax之间距离的平方和最小化，那么你可以将矩阵A转置，然后在两边分别乘以A的转置，结果得到的线性方程组一定有解。另外还一定是一个对称矩阵，且它还是个正定矩阵（positive definite），意味着你可以使用专用的线性代数包来求解。不要自己写线性代数求解工具，使用现有的工具，如CHOLMOD，TAUCS，以及Eigen库，它和大多数的游戏开发者的许可都兼容。我之前使用它遇到过一些有趣的问题，这个库有很多模板化的内容。好了，回到刚才的话题。我们在给定一些点的情况下尝试求出调和函数。使用以上求解工具不能保证正确处理边界点。它会尝试符合这些边界情况，但是为此它会使箭头分布在各处。因此我们需要拓展最小二乘求解工具以满足限制条件。
对于这个特定问题有两种方法。第一，如果你只构建拉普拉斯和边界的线性方程系统，你会得到一个不需要最小二乘法就可以求解的系统，问题是这样做会造成数值的不稳定，意味着如果你对于该矩阵运行线性代数求解软件，糟糕的条件数会使其产生错误。你会得到一些不知所云的东西。不推荐你使用这个方法。
我们推荐使用另外一名法国数学家的方法。当你想最小化一个受限于一些限制点的函数时，通常人们会使用拉格朗日乘子。也许你听说过这个方法，也许没有。思路是不对受限于某个条件g的函数f最小化，而是引入一个新的变量λ，然后尝试最小化一个有三个未知数x，y，λ的函数，f(x,y)-函数和限制条件之间的距离。如果你有更多的边界点，你需要更多的限制条件，你只需加入更多的λ，不过你的矩阵也会变得越来越大，不过谁在乎呢~反正能得到答案。
如果你采用这个方法，你最终会构造出一个线性方程组系统，它符合两个条件：所有使用之前表达式的离散拉普拉斯均为0。另外，对于每一个符合狄利克雷边界条件的边界条件我都为其添加一个拉格朗日乘子。然后对得到的二次项能量进行最小化：对矩阵A转置，左右两边同时乘以A的转置，将其输入到你的矩阵求解工具中，然后对于网格物体的每一个点它都会神奇地生成一个调和函数。
它实际看上去是这样的。这是我引用的论文中的一个模型。它展示了一些你能够实现的有趣的效果，你可以清楚地看到这个方法是多么有用。这里我们有几个控制点，一个在头顶上，还有一个在雕像的底座上。函数在顶部达到最大值，底部则为最小值。如你所见，函数各处的值在这两个极值之间平滑地过渡。所以你可以创造出一些很自然很直观的效果，你可以使纹理在平面上平滑地过渡，很简单很自然。假设你有一辆坦克，你希望在一些地方加上锈斑，那么你可以将有锈斑的地方设为最大值，没有锈斑的地方设为最小值，然后你将这些输入到求解工具中，然后你会得到一个平滑过渡的整个坦克的纹理。
如果你对这张图的图案不满意，你可以加入更多的限制来得到不同的图案。这里你可以为每个人的头顶加入一个限制，你会发现你得到了同样的限制方式，但是现在所有的条纹都正确了。这是在任意形状的网格物体上创建光滑函数的一个非常实用的方法。
这是计算机图像学中一个常见的应用，它来自于一个问题：假设你有一个网格物体，你希望为其快速创建一个纹理贴图，你该如何做？你可以对其进行裁剪，使网格物体和一个圆盘同胚，意味着如果你将其表面压平，结果的形状可以变形为一个圆盘。它不一定非要参数化圆盘，只需参数化其边部即可。如果你为创建的边设置UV坐标，你会得到边界条件，U和V各有一个。然后你可以得到两个调和函数。这样你通过将整个网格物体限定在要创建的纹理的边界内对其进行参数化。事实上，在这个例子中这个映射为双射。它们之间可以互相映射，不会产生三角形的重叠问题。你可以看到，在骆驼的头部有很多不均匀的网格分布，它们被映射到圆盘的边部，头部的网格要比底部更加密集。所以它并不适用于所有的情况，但是这个方法可以提高你程序的运行速度。这个例子说明了该方法是有局限性的。
今天我想讲的第二个内容是中值坐标（mean-value coordinate）。你们大家都知道重心坐标，事实上如果你是搞计算机图像设计的你肯定也使用过它，因为基本上所有着色都是基于重心坐标的。假设空间内有一个三角形。那么对于三角形上任意一点，你可以将其写作三个顶点坐标的一个线性组合，其中所有的权都大于等于0，且它们相加之和为1。事实上三个顶点的坐标的权正好为1。假设有一个函数在三角形的顶点处包含光照颜色的信息，你可以在三角形表面平滑地混合该函数以得到三角形内部的颜色。所有计算机图像基本都采取的是这个方法。我们希望将其归纳并推广到更多多边形，除了像三角形这样的凸多边形，还有星形多边形（即多边形内存在一点，其和多边形边界上任意一点相连的直线总在多边形内部），以及其它平面多边形甚至那些有洞的多边形，让我们把这些都囊括进来。
这里展示我们想要实现的目标：我们希望保留这个凸多边形的性质，即在多边形内部权重应为正，在外部权重应为负。我们希望平滑地混合诸如颜色等数据，我们希望它可以符合拉格朗日性质，即在顶点处只有一个权且大小为1而其余权应设为0。理想状态下我们希望所有的权相加为1。
首先，如果它和前面的调和函数一样使用余切作为权，我们会发现这些权破坏了图形的凸性。于是我们使用Michael Floater提出的中值坐标。他从我们前面介绍的调和映射中推导得出了一个分段线性近似，然后使用了很多技巧，最终得到了这种加权方式，其中包含了给定顶点相邻的边和角。假设多边形中有一点，而你希望求出多边形另一点关于的权重为，你可以使用这个公式。它的作用和重心坐标一样，你可以使用它对颜色等数据进行线性插值。
如果你稍微推广一下，比如我们要求这里计算的角度要有符号。角度有符号在这里意味着如果你计算两个向量的叉积，在线性代数中你应该学过等于|a||b|sinθ，而它的符号就是角度的符号。我们可以将其推广到任意平面多边形。它的优点在于顶点的权只取决于该顶点及其两个相邻顶点。其它的优点在于你可以使用20行以内的代码搞定它（假设你有一个用于计算三角形面积的函数）。
这里我们有一个平面多边形，它有很多顶点。你为各顶点设置它们的颜色。然后你只需将整个多边形当成一个大的三角形然后使用这个加权公式，就可以在这些颜色之间平滑地插值了。得到的函数保证在除顶点外的各处都是光滑的，你可以控制这些顶点以实现你的预期。
中值坐标的其它应用还包括纹理的参数化。如果你有一个物体，你可以将它的边界以某种方式映射到一个平面上，你可以使用中值坐标将其内部所有的点都投射到平面上，这样你将一块区域从3D空间映射到了2D空间，然后在2D空间内处理这块区域。你还可以推广中值坐标使其处理3D多面体，意味着你可以做基于方盒的变形（cage-based deformation）。使用的公式相同，只不过需要进行更多的计算。如果愿意的话，你可以使用它实现2D多边形的平滑着色。看你的需求罢了。
我希望大家能从今天的演讲理解到，无论你对拉普拉斯算符和中值坐标能够理解多少，这些工具的功能非常强大，可以为一个网格物体创建一个函数。这两个方法是我匆忙之间列举在此的，我不要求大家能够将它们写成代码，而是仔细地思考它们，并能理解到“啊，我需要懂得这些知识才能明白这个道理”，并知道它们的作用：在一个物体上的调和映射非常实用，因为你可以在任何位置定义你的边界条件，如果你懂得线性代数的话实现起来非常简单。它背后的数学推导则非常复杂，来源于18、19世纪数学家们的发现。而实现则相当直接，因为我们使用的是离散的情况，基本上就是矩阵的相加。中值坐标非常简单，你只需使用公式计算出你感兴趣的某一点的权，然后你可以对颜色、纹理数据等在整个平面范围内进行线性插值。下一周我会发布源代码，今年我是认真的！去年的源代码还没有发布……我下周争取连那个一起发。
如果你对这个话题感兴趣，这里有一些参考以及有用的材料。Michael Floater有很多关于中值坐标的论文，他从只有凸多边形的情况开始，到3D中的星形多边形，到广义的重心坐标。对于我们来讲可能最有帮助的一篇叫做 “Mean Value Coordinates for Arbitrary Polygonal Polygons”, 这是他和Hormann联名发表的一篇论文。关于调和场也有很多论文，这是最新的一篇文章，其中探讨了 “快速更新调和场，调和平面以及调和物体的方法” ，如果你希望在实时中实现这些也许对你有帮助。不过它的建立有一些复杂。有一个不错的库，叫做libIGL，作者是Alex Jacobsen，其中包含关于调和映射函数的公开实现。MIT/BSD拥有其版权，其中包含你需要的所有工具，且它是基于头文件的，很容易上手。你可以尝试一下，感受它有多么实用。下一本书是对于拉普拉斯算符的一个很好的介绍，我很喜欢。最后是CRC Press最近出版的一本书，作者是Cohen-Or以及许多其他优秀的作者，其中涵盖了拉普拉斯算符和泊松方程等图像处理用到的知识。我建议你搜一搜这些书并仔细阅读。
有问题吗？
【鼓掌】
这里有一个问题，你可以设置的控制点的数量和总共拥有的点的数量之间的比值有没有一个规定？
唔……有趣的问题。我觉得是这样，你有可能对其进行了过度限制，而限制过度体现在2个方面。首先，你的拉普拉斯矩阵的数值可能会变得不稳定，即如果有过多的点彼此靠近，它的条件数可能过高。这种情况下，直接线性代数求解工具会失灵，而迭代线性代数求解工具……线性代数求解工具分为直接型和迭代型，直接型直接进行数学计算，而迭代型不断地优化解决方法。迭代型最终会得到结果，但是这个过程会很慢。当然，也有可能最终得到一个毫无意义的结果。所以虽然没有一个明确的界限超出它求解工具会失效，但是我还是建议你少设置一些控制点。
好了，谢谢大家！
【版权声明】
原文作者未做权利声明，视为共享知识产权进入公共领域，自动获得授权。