10-22 08:04 阅读 136

GAMES101 - 网格细分和简化 Mesh Subdivision & Simplification

网格细分

网格细分 (Mesh Subdivision) 就好像把一个图像增大它的分辨率一样，让模型拥有更多的细节。因此网格细分需要用到各种算法以引入更多的三角形。但是如果只将一个大三角形拆分为更多的三角形，是不能让三角形的形状发生变化的。因此网格细分实际是两个操作：第一，使三角形的数量增多，即分出更多三角形；调整三角形的位置三角形位置发生变化，使得原来的模型变得更光滑。

卢氏细分

卢氏细分 (Loop Subdivison) 是针对三角形面的一种曲面细分算法，其命名并不是真的和 “循环” 有什么关系，而是发明这种算法的人的 Family Name 就是 Loop。

任何细分都要分为两步，卢氏细分只针对三角形面进行细分和更新顶点位置的操作。而 Loop 细分 首先对一个三角形连接其三条边的中点，即可细分得到四个三角形。然后将三角形的顶点的种类区分开，即分为新的顶点和老的顶点。这是因为 Loop 细分 会对两种不同的顶点，使用不同的规则来改变他们的位置。

新顶点的更新

一般情况下一定存在两个三角形，共享一条边（边界处的三角形就是特殊情况）。则两三角形再共线上会有一个相交的点 $P$ 。假设共线的边设为 $A, B$ ，其他顶点设为 $C, D$ 。然后对四个顶点进行加权平均操作。例如取 $A, B$ 的坐标的 $3 / 8$ ， $C, D$ 坐标的 $1 / 8$ ，相加后得到点 P 的新位置。因为我们认为距离点 P 近的顶点贡献大，距离远的贡献小。

$8^{*}(A+B)+1 / 8^{\star}(C+D)$

旧顶点的更新

一般情况下，一个旧顶点会连接很多三角形（如图所示六个三角形）。Loop 细分在更新旧顶点时，一部分由周围的旧顶点决定，一部分由自己决定。设顶点的度为 $n$ ，则 $u$ 为一个和 $n$ 相关的数值。通过一系列的加权计算出更新后的旧顶点。

$P_{o} +\mathrm{u} · P_{sum(n)}$

Catmull-Clark 细分

如果模型的网格不是三角形而是四边形的网格，则可以使用 Catmull-Clark 细分。在 Catmull-Clark 细分 中我们定义四边形面 (Quad Face) 、非四边形面 (Non-Quad Face) 、度不为 4 的顶点为奇异点 (Extraordinary Vertex) 。

首先 Catmull-Clark 细分 对每条边都取其中点，每个面也要去一个点，这个点可以是重心或者是其他的店。然后将边上的点和面中心的点连起来。我们可以发现经过一次细分后两个度为 5 的奇异点没有变化，并且引入了两个新的度为 3 的奇异点。只要我们在一个非四边形内选择一个点，与其所有边上的点（中点）相连，那么一定会得到一个新的奇异点。而非四边形面经过一次细分操作后却都被我们消灭了，也就是说当我们继续进行细分后，奇异点也不会再增加了。

顶点的更新

和 Loop 细分 有所不同的是 Catmull-Clark 细分 将顶点分为三类进行更新。

在面中心的点 (Face Point)
在边中心的点 (Edge Point)
旧顶点 (Old Vertex Point)

Catmull-Clark 细分 并按顺序对三类顶点进行加权平均计算，

网格简化

对于一个非常复杂的网格，当处于很远的地方时，实际上我们是不需要渲染这么精细的网格的。这时就需要对模型进行网格简化 (Mesh Simplification) 。

在不同的情况下，我们需要选取不同复杂度的模型，这一点有些类似 Mipmap 划分了很多层级的精细度，层次结构的几何和层次结构的图像在这方面来说含义是一样。但是几何的层次结构是很难做的，这是因为不同层级的几何在切换时没有像图像一样的三线性插值等方法可以实现平滑的层级过渡，因此需要考虑在切换时会不会影响观感。

边坍缩

边坍缩 (Edge Collapsing) 是网格简化的一种方法，正如其字面上的意义，减少网格的边或顶点，使得周围的面形成坍缩的现象，以实现网格简化，但边坍缩的实际应用没那么容易。

边坍缩需要判断哪些边是重要的哪些边是不重要的，因此需要引入二次误差度量 (Quadirc Error Metrics) 这一方法进行判断。

如下图所示的将面退化为点的一维情形，有一个五个顶点四条线段所构成的形状，我们需要将其简化成由三个顶点构成的蓝色三角形，并且保证蓝色三角形和原本的形状基本一致。

可以看出，三角形的上的新顶点和要减去的三个顶点有很大的关系，也就是说新顶点应该是旧顶点的某种加权平均的结果。但如果只是简单的加权平均，会发现新顶点无论如何都会比原来的突出部分小了一圈。

如何坍缩边

针对这种情况，人们引入了误差度量的概念，这里采用了二次误差。我们希望新顶点处在的位置，可以最小化误差度量，即新顶点到原本的几个点的距离的平方和达到最小。

如何选取边

回到实际的三维空间中，当要进行边坍缩时，我们可以假设每一条边都要进行坍缩，并计算出每一条边坍缩后的最小二次度量误差，然后从结果中选取误差最小的边开始坍缩。

但是当坍缩了一条边后，显然周围的边便也发生了变化，因此需要更新这个误差集合。也就是说我们需要一个数据结构对误差进行排序并动态更新，因此可以使用优先队列或堆来维护该误差集合。

我们需要的是一个在全局的物体简化轮廓表示，但现在的算法寻找的却是任意的局部最优解。显然这是典型的贪心算法，并不能保证能找到一个全局最优解。

网格规范化

对于三角形面的网格，其网格上的三角形有大有小，如细长型状的三角形，这实际上会对渲染造成一些不便。

对于这种情况，我们通常要对模型进行网格正规化 (Mesh Regularization) ，使三角形面更像正三角形。但是在改进三角形的质量的同时，不能丢失模型本身的质量。

作者：田错
链接：https://juejin.cn/post/7021831337547923470

GAMES101 - 网格细分和简化 Mesh Subdivision &amp; Simplification