课程链接：GAMES102几何建模与处理
课程讲师：刘利刚
公众号：AlbertLiDesign
Github实现（C#）：https://github.com/AlbertLiDesign/ALDGP
回顾：网格曲面，二维流形曲面的离散
之前我们提到，网格实际上就是二维流形曲面的离散表达，一个观点是网格是从二维到三维的映射，另一个观点是平面图在三维空间中的嵌入。因此网格也是参数型的曲面，只不过是分片线性的。
网格的数据结构种类非常多，没有普适的网格数据结构，要根据具体问题具体分析。要注意，在编程中空间和时间永远互相矛盾，存储越多的信息，访问就会越快，存储的信息越少，节省了内存，但是访问速度就会大大增加，因此要对不同的问题选择不同的存储方式，来高效地解决问题。
局部结构
局部特征度量
在网格中，一个点的信息例如点的弯曲程度，由它周围的点来决定，因此我们使用1-邻域（1-ring neighborhood）信息来考虑，1-邻域指直接与点相连的集合（如图2）。
如果是2-邻域，则考虑的范围更大，每个位于1-邻域中的点的1-邻域将会被考虑进来，如图3所示。邻域越大，考虑的几何信息就会越多，但通常我们就用1-邻域来近似顶点的无穷小邻域。
如图4，在红色顶点的1-邻域中（蓝色顶点），我们可以对红色点的加全平均得到橙色点。如果是使用均匀权重，那么橙色点就位于蓝色点的重心，我们也可以使用Cotangent权，与它们的几何属性相关联。这样我们可以看到，橙色点和红色点之间有一个向量，这个向量越长，红色点越尖锐，因此该向量可以用来度量红色点的属性，像一个伞柄，于是人们就定义这个向量叫做拉普拉斯算子（Laplace operator）。极小曲面的局部迭代法就是不断地让红色点向橙色点位置移动。
拉普拉斯算子
拉普拉斯算子是维欧几里得空间的二阶微分算子（椭圆型算子），对于二元实函数
，它表示为
在笛卡尔坐标系中，为所有非混合二阶偏导数，即分别对各分量取二阶偏导然后求和
从几何的角度来看，拉普拉斯算子是梯度的散度
，梯度是一个向量，散度是向量的三个分量的和。
离散几何中的拉普拉斯算子：
在离散几何中，拉普拉斯算子（也叫Umbrella Operator，伞型算子）表示为：
在一维的差分中很好理解，在坐标系中取三点，求
处的导数，可以表示成
即用与
的斜率来近似导数，这种用后面的点减去前面的点的方法叫做向后差分，当然我们也可以使用向前差分，表示成
对于二维问题，度数为的顶点，二阶偏导有
这里令，则有
在另一个方向上也是一样的，将两个方向上的二阶偏导加起来会发现，我们最后会得到的拉普拉斯算子等于它周围的四个点（两个方向）的和再减去它自身的
倍。因此我们用顶点1-邻域的平均减去自身的度数倍来作为拉普拉斯算子的近似，拉普拉斯算子也叫做拉普拉斯坐标，或微分坐标。
平均曲率流定理
平均曲率流定理是说，如果要求图6中红点邻域的性质，可以在点周围取一个非常小的封闭区域，这个区域的边界记作
因此我们说，拉普拉斯坐标刻画了一个点的平均曲率性质。加权方案有很多，最常用的权是余切权。
局部拉普拉斯光滑
上文解释了拉普拉斯坐标能够刻画一个点的平均曲率性质，点到拉普拉斯坐标的向量越短，曲面越光滑，向量越长，曲面越尖锐，它也可以作为几何细节的度量。
之前我们在局部迭代求解极小曲面中，运用了图8中的方法，这种将顶点沿着拉普拉斯算子移动的方法就称为拉普拉斯光滑（Laplacian Smoothing）。在求解极小曲面的过程中，我们迭代了很多次得到了近似极小曲面，即边界固定的情况下，无穷多次的拉普拉斯光滑即可得到极小曲面。
从信号的角度，拉普拉斯光滑可以看作是一种对这个点处的几何信号不断处理的过程。这一方法可以用于网格去噪，真正的数学上的意义是它是一种滤波（Filter）。滤波就是用一个值的周围的值来平均，也就是卷积。
如图10，执行了拉普拉斯光滑后，模型就变得光滑，但同时模型上的细节也消失了。但是如果过渡去噪，使得模型细节过度缺失就会over-smoothing，如图11所示。因此我们要控制和迭代次数。
前面我们提到了平均曲率流，如图7，我们写出了平均曲率的离散形式，即拉普拉斯算子就等于平均曲率与法向相乘，我们可以依此来进行网格光滑，如图12。当然我们也可以求出一个网格顶点的曲率，如图13。
全局拉普拉斯光滑
根据极小曲面的定义我们知道，如果每个点的平均曲率都为，就能得到极小曲面，我们前面的迭代方法是让每个点都不断地迭代，使每个点的平均曲率趋向于
，在迭代的时候我们发现，迭代过程中会出现局部光滑得过快，或者出现自交的情况。那么有没有好的方法来解决这个问题呢？
我们的目标是希望每个点都满足下面这个关系
这个关系是关于的方程，如果我们把所有顶点的方程联立，就能得到网格曲面的整体Laplacian方程：
这里的矩阵是一个
的矩阵，但是它非常稀疏，因为每一行的数目是顶点数，非零数却只有度数个。我们把拉普拉斯算子
放在等号右边就能得到图14形式，本质上是如图15分别求三个分量
同样，对于一个图，我们求出了每个点的，我们通过求解
就能求出更新后的顶点位置。如果每个
都缩短到它的
就相当于我们前面的迭代方法。这就是拉普拉斯光滑的全局方法。
拉普拉斯矩阵的秩是，多个分离mesh的话就是
，因此它是一个非满秩矩阵，这就需要加条件约束，例如约束边界点。这样我们就得到了生成极小曲面的全局方法，如图17。
