Tutte嵌入算法【网格参数化】

在几何处理中，Tutte嵌入也称为重心嵌入（barycentric embedding），可以通过将网格的边界顶点固定在某个凸多边形上，并与凸多边形边界内部的内部顶点构建无交叉的直线嵌入来进行网格参数化。

NSDT工具推荐：?Three.js AI纹理开发包?-?YOLO合成数据生成器?-?GLTF/GLB在线编辑?-?3D模型格式在线转换?-?可编程3D场景编辑器?-?REVIT导出3D模型插件?-?3D模型语义搜索引擎?

1、Tutte嵌入的实现

为了实现 Tutte 嵌入，我们必须使用两个向量 u 和 v 来存储参数化坐标，另外两个向量 u_ 和 v_ 来存储边界顶点。 对于内部顶点 i，我们可以直接应用以下方程来构建重心映射：

其中 j 表示 i 的相邻顶点。

对于边界上的那些顶点，我们使用下面的方程并设置 aii =1，将它们固定在凸形状上：

因此，我们可以构建以下两个线性系统：

其中 A =(aij) 是存储所有权重 aij 的稀疏矩阵。 我们可以通过求解两个线性系统来找到参数化坐标。

我选择一个圆盘作为固定边界顶点的凸形状，并使用geometry-processing-js库作为网格的数据结构。

2、权重方案

我尝试了三种不同的权重集，即均匀拉普拉斯权重、Laplace-Beltrami 权重和平均值权重。

• 均匀拉普拉斯权重

均匀拉普拉斯（uniform laplacian）权重集最容易构建，但它没有考虑网格的几何特征。 我们可以通过以下方式简单地设置权重矩阵的条目：

其中Di是顶点i的度数，即连接i的边的数量。

• 拉普拉斯贝尔特拉米权重

我们还可以从拉普拉斯贝尔特拉米（ Laplace-Beltrami ）算子导出权重：

其中Ai表示顶点i的Voronoi区域面积，αij和βij分别表示与边(i,j)相对的两个角，如图1所示：

图 1：一个顶点的 Voronoi 区域

为了计算 Ai 的值，我们可以使用：

其中∥xi?xj∥是边(i,j)的长度。

就顶点一环邻域中的一个三角形而言，如图 2 所示，该三角形内部的 Voronoi 区域可以计算为：

图 2：单环邻域的一个三角形的 Voronoi 区域

由于网格的数据结构是基于半边（half-edge），我们可以通过检索某个半边的前一个半边来简单地找到该半边的邻居。例如，在图 2 中，半边 ?j2,i? 是半边?i,j1?的前一个。 因此，通过遍历顶点上关联的出半边，我们可以使用以下代码片段轻松计算其 Voronoi 区域：

let area = 0.0;
for (let h of v.adjacentHalfedges()) {
    let u2 = this.vector(h.prev).norm2();
    let v2 = this.vector(h).norm2();
    let cotAlpha = this.cotan(h.prev);
    let cotBeta = this.cotan(h);
    area += (u2 * cotAlpha + v2 * cotBeta) / 8;
}

• 均值权重

Laplace-Beltrami 权重考虑了网格的几何形状，但对于钝角三角形，它可能为负。 根据中值定理，我们可以推导出均值（mean value）权重，该权重始终为正并生成一对一的映射：

其中∥xi?xj∥是边(i,j)的长度，δij和γij是边(i,j)两侧的两个相邻角点，如图3所示：

图3

在实际实现中，就像我们在计算 Voronoi 区域时所做的那样，我们仍然可以利用半边序列来找到相应的角点：

let delta = h.next.corner;
let gamma = h.twin.prev.corner;

3、结果与结论

Tutte 嵌入的结果如图 4 所示，应用于具有不同权重集的不同对象。

图 4：Tutte 嵌入的结果

从结果中我们可以得出结论，Laplace-Beltrami权重集和均值权重集可以更好地保留原始网格中三角形的形状。 这导致网格的内部孔扩大，这在甲虫中清晰可见。 为了更好地说明此属性，我们可以仔细查看网格（图 5）：

图 5：牛的部分参数化

图 5 从牛对象参数化的屏幕截图中获取了相同的 200×200 像素部分。 结果表明，均匀的拉普拉斯权重可以使参数化上的三角形变得更加规则，但拉普拉斯-贝尔特拉米权重和均值权重的参数化网格上的三角形与原始网格上的三角形更加相似。

此外，Laplace-Beltrami权重和均值权重可以更好地保留网格上的图案。 如图 6 所示，如果我们使用 Laplace-Beltrami 权重或平均值权重，人脸对象上的特征（即嘴和眼睛）会更容易区分：

图 6：面部参数化

我将项目上传到了github，可以去那里看看算法是如何工作的。

---

原文链接：Tutte嵌入参数化 - BimAnt