网格参数化，Mesh parameterization processing

前言

多边形网格的类型多种多样。本文所实现的网格多边形参数化是指三角多边形。
不同的表示被用来编码三维物体的几何形状。选择一种表示方式取决于在上游的获取过程和下游的应用程序。然而，最容易重建的表示是在大多数情况下不是应用程序的最佳情况。参数化的概念是指为对象附加了一个“几何坐标系统”。
本文介绍了计算这种参数表示的方法对于给定的多边形网格。这有助于从一种表示转换为另一种表示。例如，可以转换网格模型变成一个分段的样条曲面，也就是这种类型的表示法用于计算机辅助设计（CAD）软件包。在某种意义上，这是提取了几何的“方程”，或者构造了几何的抽象几何：一旦几何被抽象，将其重新实例化为可选的表示变得更容易。
一个参数化的例子如下：通过对空间几何的重新建模，构造新了二维参数化对象。其作用在于完成了对三维mesh的参数化过程，这对于一些问题，如在三维mesh进行一些复杂操作时，我们可以将其转化为对二维对象，在其参数空间进行处理。最后将处理的结果转化到三维mesh。

下面阐述了3中parametrization mapping 的方式。

1.Barycentric mapping

Mapping 步骤

Reference: W. Tutte. “Convex Representation of Graphs.”
他描述了一种方式，从Mesh 几何空到参数空间的映射方式，可以通过下式构建。

这里的i是指顶点的序列i，共有N个顶点。
该问题也被考虑为（对于坐标$x_j,y_j$）,系数矩阵C决定了参数空间网格的形状：

同时也给出了$\lambda$的取值：

在上述的参数下，可以完成整个参数化的过程，定义为：

在文中证明该结论：给定一个与三角形曲面，如果边界顶点处的（u, v）坐标位于凸多边形上，如果内部顶点的坐标是其相邻顶点的凸组合，则（u, v）坐标形成有效的参数化，即无自交的参数化。并建议${\lambda }_{ij}=1/d_i$,他表示了质心mapping的参数化过程。具体取值如下：

具体求解过程考虑为对一线性系统的求解，但对于大型mesh而言，这并不适用。可以考虑采用高斯赛德尔迭代求解。Gauss-Seidel更新方程如下：

实例

这里通过一个实际算例展示其mapping 过程。
该图为一个三维狮头mesh，red lines represent the boundary edge.

This gif describes the algorithm update process, using the barycentric mapping.

2.Laplace mapping

拉普拉斯变换，或拉普拉斯算子，是多元函数二阶导数的推广。二维的Discrete Laplace 过程可以写为：

根据其形式，可以考虑为对 函数x，y，G2变化的一种描述。他也经常被应用在图像处理等一些应用中，被简化为laplace operator。
对于三维mesh case， the equation can be define as:

A是指点i的邻域空间。省略其推导过程，这里直接给出结论（Ref: M. Eck, T. DeRose, T. Duchamp, H. Hoppe, M. Lounsbery, and W. Stuetzle. “Multiresolution Analysis of Arbitrary Meshes.”）：

因此，其A矩阵值可以表示为：

依旧采用Gauss-Seidel algorithm, 对1中问题求解如下：

3.Laplace improvement

由二中解决方案，可以看出，Laplace 对该三角mesh的参数化过程并不如barycentric mapping. 究其原因是因为钝角三角问题。导致矩阵A值出现部分负值。这个问题一般可以通过对mesh 的细分处理，替换掉所有的钝角mesh，然后再带入LapLace mapping 过程。而在在一些改进方案中从新定义不同的系数值如下：

算法更新:(由下图可以看出算法解决了Laplace-Beltrami operator的缺陷，不再有self-interesct mesh)

4.Coding

待续…