网格简化(QEM)

1 概述与原理

网格简化，通过减少复杂网格数据的顶点、边和面的数量简化模型的表达，在图形学领域，这种技术也叫做Level of details(LOD，多层次细节)。

1.1 网格简化的应用

• 多分辨率渲染：对于投影尺寸较小（远距离显示）的模型，可以渲染它的简化版本替代原本丰富细节的高复杂度网格，提高渲染效率。
• 代理仿真：在简化模型上进行仿真，然后通过插值方法得到原本复杂网格的近似仿真结果，提高仿真效率。${}^{[1]}$

1.2 常见的简化操作

• Vertex Decimation（顶点抽取）

  选择一个顶点进行删除，移除该顶点相邻的面，然后对产生的孔洞重新三角化。

• Vertex Clustering（顶点聚类）

  

  划分原始网格的包围盒成一个grid，将每个cell中的顶点聚类成一个，然后依据聚类后得到的顶点更新网格的面。

• Edge Contraction（边收缩）

  

  $(v_1,v_2)\to \overline{v}$，将一条边收缩为一个点，删除退化的面（上图中阴影所示）。

• Pair Contraction（点对收缩）

  作为边收缩的推广，如果点对$(v_1,v_2)$是一条边，那么等同于边收缩；如果点对$(v_1,v_2)$不是一条边，那么对该点对进行收缩会使原本不相连的部分连接到一起。

1.3 二次误差度量

为了保证收缩后的顶点与原始网格之间的局部距离不要太远，我们选择一种基于二次距离度量的方式寻找最优的收缩点。

根据二次距离寻找最优收缩点

此处公式推导请移步至网格简化 QEM 方法详解，文中讲得十分清晰。

考虑一次边收缩。对于两个点 $v_1,v_2$ ，收缩成一个点 $\bar{v}$ 。定义 plane $\left(v_i\right)$ 表示 $v_i$ 对应的那些原始三角面，则我们的优化目标是
$$\bar{v}=\underset{v}{\mathrm{argmin}}\sum _{p\in \text{ plane }\left(v_1\right)\cup \text{ plane }\left(v_2\right)}\mathrm{distance}(v,p{)}^2$$
下面一步步化简。令平面 $p$ 的表达式为 $ax+by+cz+d=0$ ，其中 $a^2+b^2+c^2=1$ 。 记 $v=[x,y,z,1{]}^T,p=[a,b,c,d{]}^T$ ，可得
$$\mathrm{distance}(v,p{)}^2={\left(v^{T}p\right)}^2=v^{T}p{p}^{T}v=v^T{K}_{p}v$$
其中 $K_p=p{p}^T$ ，则原式简化为
$$\bar{v}=\underset{v}{\mathrm{argmin}}{v}^T\left(\sum _{p\in \text{ plane }\left(v_1\right)\cup plane\left(v_2\right)}{K}_p\right)v$$
此处取约等于
$$\bar{v}\approx \underset{v}{\mathrm{argmin}}{v}^T\left(\sum _{p\in \mathrm{plane}\left(v_1\right)}{K}_p+\sum _{p\in \mathrm{plane}\left(v_2\right)}{K}_p\right)v$$
令 $Q_i={\sum }_{p\in \text{ plane }\left(v_i\right)}{K}_p$ ，则有
$$\bar{v}=\underset{v}{\mathrm{argmin}}{v}^T\left(Q_1+Q_2\right)v$$
初始化时，将 $\mathrm{plane}(v)$ 设为点 $\mathrm{v}$ 周围的三角形面即可。此时上面的约等号并无大碍，因为一个 三角形面至多重复三次 (三个顶点)，不仅不会带来较大的误差，而且简化了计算。
另外， $K_p$ 是对称矩阵，故 $Q$ 也是，所以只需要存储 10 个元素即可。
此时求解 $\bar{v}$ 的坐标变成求解二次函数极值点。${}^{[2]}$

令$Q=Q_1+Q_2$，通过解如下方程求解$\bar{v}$的坐标：
$$\left[\begin{array}{cccc}{q}_{11}& q_{12}& q_{13}& q_{14}\\ q_{12}& q_{22}& q_{23}& q_{24}\\ q_{13}& q_{23}& q_{33}& q_{34}\\ 0& 0& 0& 1\end{array}\right]\bar{v}=\left[\begin{array}{c}0\\ 0\\ 0\\ 1\end{array}\right]$$
上式中，$q_{11}$表示$Q$的第一行的第一个元素的值，这里$\bar{v}$使用的是齐次坐标。如果上式中左侧矩阵可逆，则
$$\bar{v}={\left[\begin{array}{cccc}{q}_{11}& q_{12}& q_{13}& q_{14}\\ q_{12}& q_{22}& q_{23}& q_{24}\\ q_{13}& q_{23}& q_{33}& q_{34}\\ 0& 0& 0& 1\end{array}\right]}^{-1}\left[\begin{array}{c}0\\ 0\\ 0\\ 1\end{array}\right]$$
如果不可逆，则${}^{[4]}$
$$\begin{gathered} v=(1-k)v_1+k{v}_2,\text{where}k\in [0,1] \\ \bar{v}=\underset{v}{\mathrm{argmin}}{v}^T\left(Q_1+Q_2\right)v \end{gathered}$$
如果还是不行，就选择端点$v_1,v_2$或者中点$\frac{v_1+v_2}{2}$三者中误差（$\Delta (v)=v^{T}Qv$）最小的作为$\bar{v}$ ${}^{[3]}$。

2 算法流程

图源自：QEM网格简化 - 简书 (jianshu.com)

2.1 逐步分析

• 计算所有初始顶点的$Q$矩阵

  令平面 $p$ 的表达式为 $ax+by+cz+d=0$ ，其中 $a^2+b^2+c^2=1$ 。记$p=[a,b,c,d{]}^T$。由此，我们定义$Q_i$（4x4，顶点$v_i$的$Q$矩阵）如下：
  $$Q_i=\sum _{p\in planes(v_i)}p{p}^T$$

• 选择合法点对

  一个顶点对$(v_i,v_j)$是合法点对的条件为：

  • $(v_i,v_j)$是一条边；
  • $\Vert v_i-v_j\Vert <t$，$t$为阈值参数。

  以上条件满足其一即可。

• 计算每个合法点对$(v_i,v_j)$的最小收缩误差$cos{t}_{ij}$，以及最佳收缩点$v_{opt}$的位置

  首先计算$v_{opt}$对应的$Q_{opt}$：
  $$Q_{opt}=Q_i+Q_j=\left[\begin{array}{cccc}{q}_{11}& q_{12}& q_{13}& q_{14}\\ q_{12}& q_{22}& q_{23}& q_{24}\\ q_{13}& q_{32}& q_{33}& q_{34}\\ q_{14}& q_{24}& q_{34}& q_{44}\end{array}\right].$$
  定义$cos{t}_{ij}$如下：
  $$cos{t}_{ij}=v^T{Q}_{opt}v$$
  最小化收缩误差，得到$v_{opt}$。具体计算参见上一节[二次误差度量](#1.3 二次误差度量)。

• 将所有合法点对按其对应的$cos{t}_{ij}$的顺序放置在一个堆中，最小$cos{t}_{ij}$对位于顶部

  一般使用小根堆进行排序。

• 移除最小$cos{t}_{ij}$对应的点对，收缩$(v_i,v_j)\to v_{opt}$，更新所有包含了$v_i$或$v_j$的合法点对的$cost$

  这一步是迭代进行的，结束的标志为达到了设定的简化率或者堆空了${}^{[5]}$。

3 Python代码实现

代码实现方面，推荐直接学习该项目：Mesh_simplification_python: An implementation of mesh simplification algorithm using python，其中代码注释很全，条理清晰，值得学习。

3.1 测试结果

输入模型网格（9397 vertices, 18794 faces）：

$t=0,ratio=0.5$（4698 vertices, 9396 faces）：

$t=0,ratio=0.1$（939 vertices, 1878 faces）：

4 总结

• 代码功能优化

  在原论文中还提到了如下两个细节：

  • 保留边界

    对于一些在简化过程中需要保持边界的模型网格，我们在点对收缩时判断点对是否为边界边，如果是，我们可以给该点对cost加权一个较大的惩罚因子，阻止收缩。

  • 防止面片翻转

    直接使用QEM算法进行网格简化，可能会导致一些面片翻转。所以我们需要在计算点对收缩cost时，同时判断点对的每一个相邻面片是否发生了翻转。可采用收缩前后面片法向量的夹角大小进行判断。同时，我们也对其代价进行惩罚。

参考

[1] GAMES102:几何建模与处理
[2] https://zhuanlan.zhihu.com/p/411865616
[3] Michael Garland and Paul S. Heckbert. 1997. Surface simplification using quadric error metrics. In Proceedings of the 24th annual conference on Computer graphics and interactive techniques (SIGGRAPH '97). ACM Press/Addison-Wesley Publishing Co., USA, 209–216. https://doi.org/10.1145/258734.258849
[4] https://www.jianshu.com/p/2bf615c38165
[5] https://github.com/AntonotnaWang/Mesh_simplification_python