图形学——网格简化
上一篇博客讲了网格的相关内容，也提到了一些网格简化的算法。但是实际上网格简化是网格中很大的一个块，因此这次单独拿出一篇文章来介绍简化的相关内容。
话说到前面，网格简化有很多方法，这里介绍的多种方法，我也不是都明白，以后有机会的话会对其进行各个算法复现。对于一些复杂的算法，可能需要查阅相关论文才能明白其中的数学道理，在本文也会给出一些复杂的简化算法的论文链接。
网格简化更宽泛，具体的细节一般为层次细节简化（LOD：Level of Details）。它主要用于简化采样密集的多面体网格，以及三维场景的存储，传输和绘制。它主要目标是在不影响画面视觉效果的条件下，通过逐次简化景物的表面细节来减少场景的几何复杂度，从而提高绘制算法的效率。
在层次细节简化时候，我们会对一个原始的多面体模型建立几个不同逼近程度的几何模型。从近处观察物体，采用精细模型，从远处观察物体，采用较为粗糙的模型，当视点连续变化时，在两个不同层次的模型间会有明显的跳跃，为了追求完美应该要一个平滑的过渡，因此还需要几何形状过渡。
因此层次细节简化技术的研究主要集中在：
- 建立不同层次细节的模型。对任意给定的复杂多边形网格\(M\)，由精细到粗糙建立一系列模型序列：\(M_0,M_1,…,M_n, M_0 = M\)。
- 建立相邻层次的多边形网格\(M_i,M_{i+1}\)的几何形状过渡：\(\Phi: M_i \rightarrow M_{i+1}\)。
层次细节简化第一步说到底就是不同程度的网格简化。下面介绍几个简化的基本操作，和上篇文章相似。
- 顶点删除操作L删除网格中的一个顶点，对它的相邻三角形形成的空洞做三角剖分
- 边压缩操作：网格上一条边压缩为一个顶点，与该边相邻的两个三角形退化为边
- 面片收缩操作：网格上的一个面片收缩为一个顶点，该三角形本身退化为点，其相邻的三个三角形都退化为边
下面会介绍几个具体的算法，他们策略不同，但是最后都是上面3种操作的组合。
基于长方体滤波的多面体简化
基于长方体滤波的多面体简化是最简单的一种简化方法，它的思想是，将多个聚集在一起的顶点聚合为一个顶点，这个操作实际上是采样的一种。具体步骤如下：
- 给定一个多面体\(M\)，记\(K\)为其拓扑，假设\(M\)已三角化。算法首先建立\(M\)的长方体包围盒，并将该包围盒所包围的空间均匀剖分成一系列的小长方体子空间，然后将各个子空间中的顶点聚合为一个代表顶点，如果子空间中无顶点则不考虑。一般来说聚合的这个顶点位于子空间的中心，子空间也是被均匀分割的。这些代表顶点为原多面体所示景物的重新采样。基于原多面体的拓扑结构和这些采样点可以重新产生多面体，所得多面体即为保持一定层次细节的模型。剖分的子空间越小，得到的层次模型就越逼近原多面体。
在二维空间中，长方体滤波的示意如下：
长方体滤波的主要缺点是会导致一些重要的高频细节的丢失。
下面两个算法是利用顶点删除技术的代表。顶点删除技术比较难的部分在于，删除哪些顶点？随机采样不能得到很好的效果。在网格中，近似平面的顶点可以删除，而对于尖锐部分的顶点删除后会使得模型大大折扣。因此下面介绍两个局部判别准则，用来决定删除哪些顶点比较合适。
基于相邻面片和边界的局部平坦性原则
由Schroeder提出。该判别分两种情况：
- 对于网格内部顶点\(V\)，记其周围相邻面片集为\(S\)，则该点的平坦性标准由下述的距离来描述：
\[d = \vert\mathbf N \cdot(v - C)
\vert\] 其中\(N\)为向量\(\frac{\sum_{f\in S}\mathbf n (f)A(f)}{\sum_{f\in
S} A(f)}\)的单位向量，\(C =
\frac{\sum_{f\in S}c(f)A(f)}{A(f)}\),这里\(A(f),c(f),\mathbf{n}(f)\)分别为三角面片的面积，中心和法向量。
这种度量方式某种程度上反映了该顶点的突出程度。 - 对于边界顶点\(v\)，记与它相邻的两个边界顶点为\(v_1,v_2\)，则其平坦性标准定义为\(v\)到\(v_1v_2\)连线的距离。
采用等距面来限定简化模型顶点的变化范围
由Cohen提出，这个算法相对于上述会更复杂一点。
首先介绍一个概念，叫包络（envelope）。多边形网格表面\(P\)可以看作一张分片线性参数曲面： \[ r(u,v) = (r_x(u,v),r_y(u,v),r_z(u,v)) \] 其单位法向量为： \[ \mathbf n(u,v) = (n_x(u,v), n_y(u,v),n_z(u,v)). \] 对于给定的\(\epsilon > 0\)，\(P\)的三维\(\epsilon\)等距面定义为： \[ r^{\epsilon}(u,v) = r(u,v) + \epsilon \mathbf{n}(u,v) \] 近似定义原始多边形网格\(P\)沿正负发现的\(\epsilon\)等距面\(P(+\epsilon),P(- \epsilon)\)。\(\epsilon\)等距面\(P(+\epsilon)\)和\(P(-\epsilon)\)上对应顶点\(v_i^+,v_i^-\)及其法向量可表示为： \[ v_i^+ = v_i + \epsilon\mathbf{n}_i, v_i^- = v_i - \epsilon \mathbf{n}_i, \mathbf{n}_i^+ = \mathbf{n}_i^- = \mathbf{n} \] 上述方法产生的\(P_{\pm \epsilon}\)可能出现自交的现象。
我们用解析法计算\(\epsilon\)。现在来考察\(P\)上任意三角形\(\triangle v_1v_2v_3\)：
对\(P\)上每个与三角形\(\triangle v_1v_2v_3\)不相邻的三角面片\(\triangle_j\)，判断\(\triangle_j\)是否与\(\triangle v_1v_2v_3\)的基本柱体相交。可计算得到\(q_j\)到\(\triangle v_1v_2v_3\)的距离\(\sigma_j\)。
这两个等距面构成了表面的包络。Cohen顶点删除的过程如下：
- 利用贪婪搜索策略，将原表面\(P\)的所有顶点列入带处理的顶点队列。
- 对当前待处理顶点队列中的一顶点，算法尝试从\(P\)上删除该顶点及该顶点直接相邻的三角面片，并试图用某种类型的三角剖分法来填补顶点删除后在表面\(P\)上形成的空洞。
- 若空洞位于\(P\)的包络内且能成功地被填补，则从当前队列中删除该顶点，简化表面\(P\)模型并重构原来与该顶点相连接的各顶点的拓扑关系，否则，该顶点从当前的待处理队列中退出，表面\(P\)保持不变。上述过程知道待处理顶点队列变空为止。
这个算法的相关论文为：envelopes。
Hoppe-渐进的网格简化技术
由Hoppe提出。这个算法比较难以理解，定义了很多新的东西去讲解这个算法。在渐进网格算法中，任一网格\(\hat M\)可表示为一粗网格以及\(n\)个逐步细化网格\(M^i(i=1,…,n)\)的变换，且有\(\hat M = M^n\)。一张网格可以定义为一个二元组：\((K,V)\)。其中\(K\)是一个单纯复形（simplicical complex），它表示了\(M\)的顶点，边和面的邻接关系。
\(V = {v_i \in R^3\vert i=1,…,m}\)是\(M\)的顶点位置向量集，它定义了网格\(M\)在\(R^3\)中的形状。而单纯复形\(K\)由顶点集以及称之为单形的非空子集组成：
0-单形\(\{i\} \in K\)，即为顶点，1-单形\(\{i,j\} \in K\)是一条边，2-单形\(\{i,j,k\}\in K\)为一个面。需要注意的是单纯复形\(K\)并不包含\(V\)的所有成员，只包含了构造网格\(M\)所需要的所有面，边和顶点的子集。为了在结构上刻画单纯复形，我们引进拓扑实现(topological realization)\(\vert K\vert\)的概念。
若将顶点\(\{i\}(i=1,2,…,m)\)看成为\(R^m\)中的基向量\(e_{i} = \{0,…,0,i,0,…,0\}\)，则定义在\(R^m\)中的集合\(\vert K \vert\)为\(K\)的拓扑实现： \[ \vert K \vert = \bigcup_{s \ in K}\vert s\vert \] 其中\(s\)为\(K\)的一个单形，\(\vert s \vert\)为s在\(R^m\)空间中的顶点的凸包。
我们记\(\phi_v = \phi_{\vert K\vert}\)，称为\(\triangle v_1v_2v_3\)在\(R^3\)中的几何实现（geometric realization）。若\(\phi_v(\vert K\vert)\)不自交，则\(\phi_v\)为1-1映射。此时，\(\phi_v\)为一嵌入映射，即对\(\forall p \in \phi_v(\vert K \vert)\)，存在唯一\(m\)维向量\(b \in \vert K\vert\)，使得\(p = \phi_v(b)\)。我们称\(b\)为\(p\)关于单纯复形的重心坐标向量。实际上，\(b\)可表示为： \[ b = \sum_{i=1}^mb_ie_i \] 容易知道，当\(M\)为一三角网格时，\(\phi_v(\vert K\vert)\)上任一点的重心坐标向量\(b\)中至多只有三个分量非零。
有了上述定义，Hoppe采用显示能量函数\(E(M)\)来度量简化网格与原始网格的逼近度： \[ E(M) = E_{dist}(M) + E_{spring} (M) + E_{scalar}(M) + E_{disc}(M). \] 上式中，\(E(M)\)为\(M\)的距离度量，定义为点集\(X = \{x_1,…,x_n\}\)到网格\(M\)的距离平方： \[ E_{dist}(M) = \sum_{i=1}^n d^2(x_i,\phi_v(\vert K \vert)) \] \(E_{spring}\)为\(M\)的弹性能量，这相当于在\(M\)的每条边上均匀放置一条弹性系数为\(k\)的弹簧，即： \[ E_{spring} (M) = \sum_{(i,j) \in K}k\Vert v_i,v_j \Vert^2 \] \(E_{scalar}(M)\)度量M的标量属性的精度，而\(E_{disc}(M)\)则度量了\(M\)上视觉不连续的特征线（如边界线，侧影轮廓线等）的几何精度。
Hoppe利用边收缩变换来逐步迭代计算上述能量的优化过程。下面是一个边收缩变换的例子：
因此，初始网格\(\hat M = M^n\)可经过\(n\)组的边收缩变形后简化为\(M^0\)： \[ \hat M = M^n\rightarrow ... \rightarrow M^0 \] 边收缩变换的逆变换被称为顶点分裂变换，也就是将顶点分裂成一条边。
这个简化技术的过程我不是很清楚，而老师上课的时候说的也不清楚，很多符号之前并没有定义。我去查找了这篇文章，把链接放在这里，如果想要详细了解请戳：Progress Meshes
基于二次误差度量的简化技术
Hoppe的边收缩操作可推广为一般的顶点合并变换来描述\((v_1,v_2)\rightarrow v\)。而Garland和Heckbert引进了二次误差度量来刻画每一个顶点移动后引起的误差，对表面上的每一个顶点\(v_a\)均有许多三角面片与之相邻，记\(plane(v_a)\)为这些三角形所在平面所构成的集合，即： \[ plane(v_a) = \left\{(a,b,c,d)\vert ax+by+cz+d = 0,(a^2 +b^2 +c^2 =1) \text{is the coefficients of the adjacent plane of v_a} \right\} \] 我们采用如下的二次函数来度量\(v_a\)移动\(v\)时产生的误差: \[ \Delta(v_a \rightarrow v) = \sum_{p \in plane(v_a)}(pv^T)^2 \] 其中\(v = (x,y,z,1)\)为齐次坐标，展开上式可以得到： \[ \begin{aligned} \Delta(v_a \rightarrow v) &= \sum_{p \in plane(v_a)}(pv^T)^2\\ v \left(\sum_{p \in plane(v_a) K_p}\right)v^T = vQ(v_a)v^T \end{aligned} \] 式中： \[ K_p = p^Tp \begin{bmatrix} a^2 & ab &ac & ad\\ ab & b^2 &bc & bd\\ ac & bc & c^2 & cd\\ ad& bd & cd & d^2 \end{bmatrix},\\ Q(v_a) = \sum_{p \in plane(v_a)} K_p \] 这样，每一顶点\(v_a\)，在预处理时，可以用上述方法计算矩阵\(Q(v_a)\)，从而计算移动误差。而合并顶点每次需要移动两个顶点，因此需要考虑同时移动后形成的误差。而Garland和Heckbert简单地采用加法来刻画多点移动形成的误差，对于\((v_1,v_2) \rightarrow v\)，其误差为： \[ \Delta (v) = \Delta (v_1 \rightarrow v) + \Delta (v_2 \rightarrow v) = v(Q(v_1) + Q(v_2))v^T = vQv^T。 \] 因此应该选取\(v\)使得误差达到最小。一般想法是采取优化方法如梯度下降等等，但是在这个式子里，一般\(v\)的值是有解析解的，正如线性回归一样，我们可以得到唯一解，或者伪逆技术(pseudo-inverse)求出解。如果伪逆技术失败，简单选取\(v\)为\(v_1,v_2\)或者\(\frac{v_1 + v_2}{2}\)。
二次误差度量简化算法的论文是：Surface Simplification Using Quadric Error Metrics。