面向VR建模的网格简化算法优化研究

张文静，刘茵，张孟，李明亮

（1.北京农业职业学院信息技术系，北京，102442；2.河北地质大学信息工程学院，河北石家庄，050031; 3.河北省智能传感物联网技术工程研究中心，河北石家庄，050031）

0 引言

随着VR技术的飞速发展，三维模型逐渐精细化，文件的数据量过于庞大，这使虚拟现实系统的实时响应机制缓慢，不利于进行人机交互[1]。为了优化虚拟现实系统引入网格简化思想。网格简化的关键是找到并删除对模型外观影响较小的三角面片，保留明显反映模型外观特征的三角面片。Garland提出了二次误差测度的概念（QEM算法）来控制简化误差[2]，但此种方法无法保留模型原始信息，简化质量不高；而Hoppe则提出了渐进网格(Progressive Mesh，PM)算法进行迭代简化[3]，但该算法计算量大、对机器性能要求太高，普适性不高。本文将PM算法简化思想与二次误差测度方法相结合，提出一种新的可保留模型外观特征的简化方法。

1 PM算法简介

PM算法主要内容为渐进网格思想。通过递归迭代实现边塌缩与点分裂的过程，通过不断地进行边塌缩操作使网格简化，并在简化过程中记录原始顶点和新顶点的位置信息，以及顶点间连接关系的变动情况。

Hoppe在其思想中提出边塌缩概念：三角网格中有一条三角形边uv，u和v分别是三角边的两个端点，A和B是以uv为公共边的两个三角形。当边uv为塌缩边时，用顶点v来替换顶点u，并使其它邻居顶点与新顶点连接，然后把顶点u及相关信息删除。这就完成了一次目标三角边塌缩。进行一次三角边塌缩，可以删除一个顶点、三条边和两个三角形面片。通过反复选择删减，最终就会得到一定要求的简化网格。

2 基于边塌缩的改进算法

2.1 误差公式的选择与新顶点的确定

本文采用Garland提出的二次误差测度方法(QEM方法)作为基础误差控制。在模型的三角面片网格中，质量最好的网格面片为等边三角形，一个三角形正则度越高，越接近等边三角形。为了优化简化网格质量，避免在网格简化过程中出现狭长三角形，本研究在二次误差测度的基础上引入三角形正则度作为调节因子，来调节塌缩误差。三角形的正则度表示为:

其中l1、l2、l3分别为三角形由短到长的三条边，当re=1时，三角形正则度最好，此时该三角形为等边三角形。当re=0时，三角形的正则度最差，此时三角形退化成为了一条直线。根据三角形正则度的判定，将误差调节因子设为边塌缩后，选取的新顶点邻域中所有生成三角形的正则度的平均值，即

基于二次误差测度与三角形正则度判定，确定一个新的误差计算方法，即

式(3)中Q为传统的三角形边二次误差，当边塌缩后生成的三角形的正则度越大时，简化误差越小，那么其在简化过程中的优先级越高。对于新顶点的选取，本研究选择塌缩边e的两个顶点中使Error最小的顶点作为三角边塌缩后的新顶点。相比于传统的边折叠方法，无需计算塌缩后新顶点的位置，减少了算法的计算量，不会导致网格拓扑结构错误。

2.2 边界保持

传统的二次误差测度方法会对开放边界网格的边界特征产生较大的影响，所以对于三维网格的边界顶点本研究采取了直接将边界点作为边塌缩后的新顶点位置的方法，能够很好保证模型简化后的整体质量。而对于边界边的处理，在其塌缩误差的基础上加入一个阈值C0，使其塌缩代价变大，塌缩优先级降低，较为方便简单的保持模型边界处的细节特征。

2.3 算法主要步骤

改进算法主要步骤为:（1）输入目标简化精度并初始化，计算误差矩阵；（2）计算每条边的塌缩误差Error，并判断是否需要进行边界处理；（3）选取塌缩代价最小的边进行塌缩简化，并在最小堆内更新数据；（4）若简化后三角面片数大于所求目标面数，则转步骤3继续进行简化，反之则算法结束。

由于本算法中第1、2步计算量较小，可在常规时间内完成，所以本算法的时间复杂性主要与最小堆操作有关，即本算法的时间复杂度为O(nlogn)。

3 实验结果

对本文优化算法与QEM算法和PM算法进行运行效率比较。实验环境为Visual Studio 2019，基于Intel Core i5-4210U处理器，选取bunny模型。

表1 bunny模型不同简化率下算法运行对比

由对比实验可以看出，由于优化算法时间复杂度为O(nlogn),QEM算法时间复杂度为O(n2)，所以优化算法时间效率较QEM算法有了大幅度提升。而PM算法，由于其复杂的误差控制方式，导致其运行时间明显长，可知原始的PM算法并不满足虚拟现实系统对算法运行高效率的要求。

然后将本文算法与QEM方法进行模型简化质量的对比实验，实验环境同上文。图1为bunny模型经本文算法在不同简化率下的简化质量对比。图2展示的是在80%简化率下模型细节的对比。

图1 bunny模型本文算法简化图

图2 bunny模型80%简化后细节对比图

对比知本文算法在模型简化的同时能使网格模型保持较好的外部形态特征，删减网格主要集中在兔子毛发等细节部位，对模型整体的形态几乎没有影响。由于引入了误差调节因子和边界处理，优化算法简化后的模型网格过渡更为平滑，对细节特征的保持也更为优秀，这表明本文算法完成了在快速运行的基础上保持良好的网格模型质量的目标。

4 结论

本论文得到北京农业职业学院科技创新项目基于VR技术的360全景展示设计及实现(No.XY-YF-20-13)、北京市职业院校教师素质提升计划专业创新团队培养项目（设施农业与装备（智慧农业）专业创新团队）支持。本文根据虚拟现实对网格模型质量高、数据量小的要求，提出了一种可快速运行的、能够较好保持三维网格特征的网格简化算法。本文优化算法满足了虚拟现实系统对网格简化算法运行速度快、简化质量高的要求，三维模型在简化后不会影响到用户的观看体验与交互体验。