深入了解网格细分算法，提升模型渲染效果

深入了解网格细分算法，提升模型渲染效果

1.网格细分

1.1.概念

网格细分是指将原始模型上的网格划分为更多的网格，从而使模型更加精细，提高渲染效果，使画面更加美观。

下图是网格细分的示意图。左图是细分前的效果，右图是细分后的效果。

可以看到，细分后的面数更多，模型更精细。

1.2.网格细分算法

1.2.1.循环算法

首先声明一下，Loop是人名，不是循环。 Loop算法的主要流程如下：

(1)将三角形分成四份，如下图所示

(2)计算细分后，新顶点的位置

如上图所示，白色顶点是新顶点之一，其位置由旧顶点的加权平均组成。因为AB距离新顶点更近，所以权重比CD大。

特殊情况是一条边只属于一个三角面（即该三角面位于模型的边上），那么该边上新顶点的坐标可以表示为两个端点的平均值。

(3)计算细分后，旧顶点的位置

上面的公式用数学表达如下：

O表示旧顶点原来的位置，O'表示旧顶点的当前位置，n表示旧顶点的度数（有多少条边连接到这个顶点），β表示与n相关的权重，以下 累计表示周围顶点坐标之和

旧顶点的原始权重为1-nβ。如果旧顶点的度数较大，则意味着周围的顶点较多。那么，当重新调整位置时，旧顶点原来的权重就不再那么重要了。因此，经过1-nβ的计算后，旧顶点的权重会变小。

反之，如果旧顶点的度数越小，则说明周围的顶点越小。那么，当重新调整位置时，旧顶点的原始权重需要很大。计算完1-nβ后，旧顶点的权重会变大

1.2.2.循环分割的结果

1.2.3、-克拉克细分

循环细分算法仅适用于网格全部为三角形的情况。如果出现多边形网格，则循环算法不适用。因此，为了解决多边形网格的细分问题，出现了Clark网格细分算法。

首先根据下图给出两个定义：

非四边形面：网格中所有非四边形的面

奇点：度数不为 4 的点

这里我们以三角形为例

分段规则如下：

在每个面的中心或重心处添加一个新点，并在每条边的中点处添加一个新点以连接新顶点。效果如下

右下角的问题如下：

1.新增两个奇点。如果有几个非四边形，就会有更多的奇点。现在一共有4个奇点。

2、新奇点的次数为3，与原非四边形的边数相同。

3. 一次细分后，所有网格都将是四边形。

因此，完成这次细分后，只要在每个四边形上再添加四个顶点和一个中心点，就可以进行无限细分。

点的类型也分为三种。第一个是曲面点，是四个顶点的平均值，如下图：f

还有边缘点，是两个相邻面点和两个顶点的平均值。

还有一个点与四个面相邻。计算方法如下

-Clark细分算法结果如下

2. 网格简化

2.1.概念

网格简化和网格细分具有相反的效果。它们主要是为了降低渲染效果，加快渲染速度。你为什么要这样做？例如，游戏中有一个头骨。如果无论距离如何都使用相同的模型，那么当模型距离相机很远时，固定点的数量将与很近时相同，渲染速率也将相同。然而，事实上，当距离很远时，就不需要这么精确的模型了。即使是具有 300 个三角形的骨架，从远处看也会产生与具有 3W 个三角形的模型相同的效果，因此需要进行网格简化。

2.2.边缘折叠算法

所谓边折叠算法，就是将一条边的两个顶点合成为一个顶点，从而使一条边变小，合成后最大程度地保持原模型的形状。

为了最大程度地保持原始模型的形状，引入了二次误差测度。这种测量方法的原理是，合并后的新顶点应该是到两个旧顶点周围的三角形合并所在平面的距离的平方和最小。

对于三角形曲面，平面的方程为ax + by + cz + d = 0。对于此类平面方程，空间中任意点到平面的距离是直接点的xyz代入。

因此，距离平方的函数为 d = (ax + by + cz + d)^2。那么所有平面的距离平方和就是将所有三角形面的这个函数相加，最后求最小值。

写成矩阵形式为

之后，对这对进行偏导。如果三个方向的偏微分都为0，我们就可以找出合并后哪两个点的值最小。

将二次式展开后如下

偏导数的矩阵形式如下：

如果左边的矩阵是可逆的

如果矩阵不可逆，则对V1和V2进行插值，找到最优点。如果仍然没有最优点，则直接认为合并点为(v1+v2)/2

上述过程仅针对任意一对点进行计算，最终需要对所有点对进行该过程。

最终算法的伪代码如下

2.3.算法效果

因为每次简化都可以保存简化之前的网格结构，所以可以保存所有这些网格结构，并且在切换相机的远近视图时可以显示不同的网格结构。

参考

Loop细分面（循环）详解，博客附完整代码 - CSDN博客

【图文】网格简化与边缘折叠（Edge）算法博客-CSDN博客

使用错误()

QEM网格简化-()

-现代计算机图形学概论-严令奇

欢迎大家评论交流。作者水平有限。如有错误，请指出。