QEM算法

一种基于二次误差作为度量代价的边收缩算法。

特点是计算速度快并且简化质量较高。

算法流程

该方法在选择一条合适的边进行迭代收缩时，定义了一个描述边收缩代价的变量$\Delta$

对于网格中的每个顶点$v$，我们预先定义一个4x4的对称误差矩阵$Q$，那么顶点
$$
v=[v_x\ v_y\ v_z\ 1]^T
$$
的误差为其二次项形式
$$
\Delta(v)=v^TQv
$$
假设对于一条收缩边$（v_1，v_2）$，其收缩后顶点变为$v_{bar}$

我们定义顶点$v_{bar}$的误差矩阵为
$$
Q_{bar}=Q_1+Q_2
$$
对于如何计算顶点的位置有两种策略：

1、一种简单的策略就是在$v_1,v_2$和$\frac{(v_1,v_2)}2$中选择一个使得收缩代价$\Delta(v_{bar})$最小的位置。

2、另一种策略就是数值计算顶点位置使得收缩代价最小。由于$\Delta$的表达式是一个二次项表达式，因此令一阶导数为0，即，该式等价于求解：
$$
\left[ \begin{array}{cccc} q_{11}&q_{12}&q_{13}&q_{14} \q_{21}&q_{22}&q_{23}&q_{24}\q_{31}&q_{32}&q_{33}&q_{34} \0&0&0&1 \end{array} \right]\overline v=\left[ \begin{array}{c}0\0\0\1 \end{array}\right]
$$
其中$q_{ij}$为矩阵$Q_{bar}$中对应的元素。

修改方向：使用牛顿法求解此三元二次型，QEM此处的0，0，0，1是为了快速求解。准确度不高

如果系数矩阵可逆，那么通过求解上述方程就可以得到新顶点$v_{bar}$的位置。如果系数矩阵不可逆，就通过第一种简单策略来得到新顶点$v_{bar}$的位置。

由上所述，可得算法流程：

  1. 对所有的初始顶点计算$Q$矩阵
  2. 选择所有有效的边（这里取的是联通的边，也可以将距离小于一个阈值的边归为有效边）
  3. 对每一条有效边$(v_1,v_2)$，计算最优抽取目标$\overline v$。误差$\overline v^T (Q_1+Q_2)\overline v$是抽取这条边的代价
  4. 将所有的边按照代价的权值房贷一个堆里
  5. 每次移除代价最小的边，并且更新包含$v_1$的所有有效边的代价

如何计算每个顶点的初始误差矩阵Q

最小二乘问题（采用平方误差的和作为目标函数）

在原始网格模型中，每个顶点可以认为是其周围三角片所在平面的交集，也就是这些平面的焦点就是顶点位置，我们定义顶点的误差为顶点到这些平面的距离平方和（距离计算方法为空间中任意一点乘以平面方程即为，点到平面的距离）：
$$
\Delta(v)=\Delta([v_x \ v_y \ v_z 1]^T)
=\sum\limits_{p\in planes(v)}(p^Tv)^2
\=\sum\limits_{p\in planes(v)}(v^Tp)(p^Tv)
\=\sum\limits_{p\in planes(v)}v^T(pp^T)v
\=v^T(\sum\limits_{p\in planes(v)}K_p)v
$$
其中$p=[a\ b\ c\ d]^T$代表平面方程$ax+by+cz+d=0其中(a^2+b^2+c^2=0)$的系数，$K_p$为二次基本误差矩阵：
$$
K_p=pp^T =\left[
\begin{array}{cccc}
a^2 & ab & ac & ad\
ab & b^2 & bc & bd\
ac & bc & c^2 & cd\
ad & bd & cd & d^2
\end{array}
\right]
$$
因此原始网格中顶点$v$的初始误差为$\Delta(v)=0$，当边收缩后，新顶点误差为
$$
\Delta(v_{bar})=v_{bar}^TQ_{bar}v_{bar}
$$
我们依次选取收缩后新顶点误差最小的边进行迭代收缩直到满足要求为止。