顾及局部特征的机场三维模型边折叠算法

陈雨，张建伟，谭诗瀚

（四川大学视觉合成图形图像技术国防重点学科实验室，成都 610065）

0 引言

虚拟环境沉浸感和逼真度是衡量虚拟现实技术的重要因素，在游戏、仿真等实际应用场景中，三维模型结构复杂且种类繁多，所以三维场景的实时绘制一直是计算机图形学研究的重点。在实际应用场景中，模型的精细度不是越高越好，而是根据实际应用需求，达到模型视觉效果和系统处理时间的平衡才是最重要的。如果三维模型的精度太高，则绘制时需要处理的数据量过大，会加重计算机CPU 和GPU 的负担，轻则渲染延迟，重则可能导致系统瘫痪。

在飞行模拟仿真中，机场三维模型精度要求较高，导致需要处理的模型数据量庞大，因此，在场景切换时会出现较长时间的渲染延迟现象，所以如何平衡现有资源实现场景的高效绘制成为了一个亟待解决的问题。当某一模型距离视点较远时，此时大量的渲染高精度模型就是浪费计算性能，因此，根据视距，在对渲染效果影响不大的情况下，合理地调度不同细节层次的模型，达到渲染效果和渲染性能的平衡才是最重要的。而构建机场多分辨率模型的关键是根据实际需求选取合适的模型简化技术，所以，本文主要是针对机场三维模型简化技术的研究。

1 三维模型简化算法

网格简化通过减少模型点、边和面的数量，减少绘制时模型数据的存储、传输和处理，以此提高三维场景实时绘制的效率。一般三维模型采用几何结构和纹理结构来进行表示，几何结构多采用三角面片表示，所以，在本文中主要研究基于三角网格的简化。

目前，网格简化方法一般可以分为三类：元素删除法、网格重绘法和元素折叠法[1]。元素删除主要是对网格几何点、线和面的删除，该方法在删除时需要考虑对模型的几何特性和拓扑结构的影响，时间复杂度较高。网格重绘法有顶点聚类法，主要思想是利用包围盒对模型所在空间进行划分，然后合并同一小空间中的顶点。该方法虽然速度很快，但是对于细节特征较多的模型误差很大，且容易造成原模型的三角形退化，拓扑结构难以保持。元素折叠法分为了边折叠和三角形折叠，相比于上两者，简化速度更快、适应性更高。三角形折叠对建筑物简化效果较差，为了达到更好的简化效果，本文采取基于边折叠的简化方式。

边折叠算法中有两个关键步骤使得模型的几何网格变动最小、效果最好，一个是最小折叠代价边的选择，一个是新顶点位置的确定。所以，边折叠误差的度量十分的重要，它是保证模型视觉效果的关键。本文通过对网格简化方法的详细研究，在基于二次误差度量的基础上，根据机场三维模型的局部特征区域，提出了一种机场三维模型的网格简化方法，提高了机场模型简化的质量，满足了用户对视觉效果需求的同时，平衡了现有系统的性能。

1.1 边折叠算法

边折叠算法由Hoppe 等人提出，其基本思想是将三角网格中一条满足条件的边，简化为一个顶点，同时将与该边两个端点相邻的所有顶点和新顶点相连，并删除所有退化的边和面[1]。

边折叠算法根据折叠后的新顶点不同分为了半边折叠算法和全边折叠算法。半边折叠的新顶点是原折叠边顶点的其中一个，全边折叠的新顶点是通过误差度量计算新生成的。两者各有各的优势，前者因新顶点就是原顶点，所以存储开销减少了、算法计算量也降低了；后者结合误差度量，生成的新顶点可以使边折叠的代价最小，能更好的保持视觉效果，因此本文选取的是基于全边折叠的。

1.2 二次误差度量算法（QEM）

网格模型简化的根本目的是在减少模型面片数的同时，确保模型整体的几何特征基本不变、主要特征区域保持。因此需要结合实际应用需求来控制几何误差，针对不同领域提升模型简化的质量。

目前，比较常用的几何误差度量有二次误差度量、体积误差度量[2]和豪斯多夫距离度量[3]。二次误差度量是Garland[4]提出的，相比于后两者，二次误差算法计算简单、效率高，因此二次误差及其改进算法是目前使用最为普遍的。

二次误差以顶点到其一阶邻域三角面片的距离作为边折叠简化的折叠代价。该算法可以分为初始化和迭代：初始化时，首先为模型中的顶点都分配一个二次误差矩阵，然后通过点的二次误差矩阵计算出相关边的误差矩阵，最后计算出折叠后新顶点的最佳位置及边的折叠代价；迭代时，依次选择代价最小的边进行折叠操作，同时更新新顶点的位置和新边的折叠代价，不断迭代简化至达到设置的简化率。

1.2.1 点的折叠代价计算

定义：模型中一顶点v，v的初始误差矩阵为Qv，顶点v所关联的三角形集合为Face（v），则顶点v到其一阶邻域三角面片的距离平方和为：

其中：P=[a,b,c,d]T，表示由方程ax+by+cz+d=0所定义的平面，且a2+b2+c2=1。Kp是一个4x4 的对称矩阵，表示如下：

1.2.2 边的折叠代价计算

定义：边（u，v），该边折叠到新顶点m后，点m的二次误差矩阵也即为边（u，v）的二次误差矩阵，等于Qm=Qu+QV，此时边（u,v）的折叠代价为：

Δ(m)可用下面的式子表示：

1.2.3 新顶点的位置计算

在该算法中，折叠代价大小取决于新生成的顶点m的位置。新顶点m存在一个最佳的位置，使得Δ(m)达到局部最小。因误差函数是个二次函数，所以可以通过对式子（1）偏导求最小值，解得m 的最佳位置，式子如下：

关于新顶点m 的位置：

若系数矩阵（2）可逆，则方程的解即为新顶点m的最佳位置；

若系数矩阵（2）不可逆，则新顶点m的位置可以选择三点（包括点u、点v或边（u,v）的中点）中折叠代价最小的所对应的顶点。

2 算法改进

基于二次误差度量的网格简化算法侧重于考虑点对模型简化前后导致的形变量大小，没有考虑模型的局部特征和网格的几何特性，导致简化出来的网格均匀，丢失一些重要的细节特征，特别是在简化率（删除的三角面片数/原模型的三角面片数）比较大的时候。因此，王晓哲等人[5]基于二次误差度量，提出了一种半自动化的网格简化算法，用户通过对感兴趣的区域可以添加权值来自定义简化效果，但是这样可能会导致模型简化效果不佳，因为一般用户是不能预判权值所对应的简化效果。段黎明等人[6]提出了网格细分方法，将体积误差和三角形平展度加入到了误差度量中，但是该方法可能会导致过共顶点的现象，降低模型网格简化的质量。李少卿等人[7]在二次误差度量的基础上加入了对顶点的约束，并对生成新面片的旋转方向进行角度误差控制，提高了模型特征区域顶点的误差度量。

为了提高机场三维模型的简化质量，本文在基于二次误差度量的边折叠算法上，提出了一种顾及局部特征的机场三维模型边折叠算法，算法通过预先对机场三维模型的重要局部区域的顶点进行标记，在折叠代价计算时添加顶点权重来改变简化序列，对机场的特征区域加以保留，提高模型简化的质量，满足用户需求。

2.1 新误差度量机制的计算

本文的改进算法在边折叠时，将误差度量分为了两部分，一是基于二次误差的基础误差度量；二是对机场三维模型特征区域的自定义误差度量。

飞行模拟仿真主要是用于飞行员的模拟训练，在整个场景中需要渲染的模型有：机场三维模型、飞机模型、车辆模型和天空场景等等。其中，最重要的是机场三维模型的绘制，特别是机场模型中的滑行道、跑道和标识牌，所以在模型简化时，需要对重要区域进行保留或者减少简化。

改进算法在读入.obj 模型文件时，根据在3dsMax中设置的区域名，识别顶点是否属于重要特征区域，若是则对顶点进行标记。在折叠代价计算时，对于边若有一个顶点被标记了，则给边的折叠代价加权值w，增加该边的折叠代价，改变简化序列的顺序，使模型重要局部区域的特征得以保持。

2.2 权值w的设置

对于初始权值w的设定，若是直接给出权值常数系数，则可能会导致重要局部区域的简化效果不佳，因为一般无法预知设置的权值所对应的简化效果，可能过小，使得对折叠代价排序的影响微不足道，如将权值设置为10，但如果二次误差的数量级为104，则简化序列不受影响。所以本文中权值w的初始值参考了待简化的机场模型的二次误差范围，即先计算得到所有点的二次误差值，记录其中的最大值和最小值，取最大误差和最小误差的中值作为初始的权值。

在边折叠的迭代中，边的折叠不仅使得一阶邻域中受影响的顶点的二次误差Q需要重新计算，而且顶点的权值w也需要重新计算，使得权值一直传递下去。考虑到机场模型的应用需求是对于这些重要局部区域尽量保留，同时为减少计算量，所以对重要区域内的点赋予初始权值w 后，权值不再改变，使其点相关的边折叠代价一直很大，不被折叠。

3 实验结果分析

本实验是在主频3.40GHz，内存8GB 的硬件环境下完成，高精度机场三维模型由3dsMax 构建并导出.obj 格式，以Microsoft Visual Studio 为编程平台实现该算法。

为了验证本算法的具有较好的性能，实验对比了QEM 算法与本文算法的简化结果。由于机场三维模型数据量太大，实验时选取了部分模型进行实验，选取的模型为天府机场部分机场建筑物和机场滑行道，如图1 所示，选取的原始高精度机场模型中包含了113336 个顶点、147775 个三角面片，其中，网格模型中有颜色的网格为机场建筑物部分，其余白色网格为滑行道部分。

图1

当简化率设置为0.2 时，图2（a）为使用了QEM 算法简化的模型，简化后包含了98558 个顶点，118219 个三角面片；图2（b）为使用本文算法简化的模型，简化后包含了98558 个顶点，118219 个三角面片。

图2

从简化结果可以看出，本文的算法有效地对机场三维模型进行了简化，相比于普适性的QEM 算法，本文算法可以对机场重要局部区域滑行道保留更多的细节特征，更符合飞行模拟仿真的实际需求。

4 结语

本文基于二次误差的边折叠算法，提出了一种顾及局部特征的机场三维模型边折叠算法。该算法不仅能够有效地简化机场三维模型，还能根据飞行模拟仿真的应用需求，较好地保留机场重要局部区域。在现有系统性能的基础上，平衡了渲染质量和渲染效率之间矛盾，满足了用户需求。根据不同领域应用需求来优化简化算法，不断提高模型的简化质量已是未来的发展趋势。为了更好地提升机场实时渲染效率，在由本文简化算法生成的机场多分辨率模型的基础上，还会进一步研究根据不同视点预调度不同层次的模型。