面向飞行仿真的四叉树多分辨率地形实时优化
开篇：润墨网以专业的文秘视角，为您筛选了一篇面向飞行仿真的四叉树多分辨率地形实时优化范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要：为实现大规模复杂地形的实时绘制，提出1种消除四叉树多分辨率地形裂缝问题的实时优化方法. 该方法将不同分辨率过渡区域的地形进行重新构网，并针对飞行仿真距离地面较高、下视角较大的特点对四叉树顶点误差估计和几何光滑过渡算法进行优化，在保证地形准确性的范围内提高计算机实时处理速度. 同时，在Vega平台下对某典型飞行训练项目进行仿真并与由LINDSTROM提出的简化公式而制订的解决方案进行比较，结果表明对地形进行优化是1种见效较快的方式.
关键词：飞行仿真；多分辨率地形；四叉树；实时优化；顶点误差；Vega
中图分类号：TP391.9 文献标志码：A
Real-time optimization on quadtree multi-resolution terrain for flight simulation
CHEN Yijun1，SAI Yin2
(1. Eng. Research Center of Container Supply Chain Tech. of Ministry of Edu.，Shanghai Maritime Univ.，
Shanghai 200135，China；2. Air Force Representation in Beijing，Beijing 100074)
Abstract：To implement the real-time rendering of large-scale complex terrain，a real-time optimization method is proposed to eliminate the split for quadtree multi-resolution terrain. The method reconstitutes the triangles in different multi-resolution transition region and optimizes the quadtree vertex error estimation and geometry smooth transition algorithm with the scheme based on the characteristics of higher distance to ground and bigger downwards angle of visibility in flight simulation. The render speed of computer is enhanced while ensuring the veracity condition of the terrain. The simulation on a typical flight training project is done in Vega and compared with the scheme based on the simplified formula solution proposed by LINDSTROM. The result indicates that the optimization on terrain is an efficient way.
Key words：flight simulation；multi-resolution terrain；quadtree；real-time optimization；vertex error；Vega
0 引 言
地形是1类特殊的三维模型[1]，地形建模被广泛应用于城市规划、数字地球、飞行模拟以及地形结构分析等诸多领域[2].对复杂三维地形的绘制，依据视点变换进行多分辨率层次细节简化是目前提高虚拟场景实时绘制能力的主要方法[3，4]，其基本思想是：在绘制中根据对象与视点的距离、视锥体的范围或者对象在屏幕空间投影所占的像素大小选择适当分辨率LOD(Level of Detail)模型，当视点远离对象或者不在视锥体范围内时，选用较粗糙分辨率的LOD地形，当视点靠近时选用细节丰富的LOD地形.目前，对地形进行多分辨率层次细分的模型有二叉树结构模型和四叉树结构模型：二叉树结构模型通过连接地形三角形顶点到基边中点将三角形分裂为2个三角形，通过迭代细分得到更高层次的三角形；四叉树结构模型将地形的高度场分成正方形块，用四叉树结构组织地形数据，四叉树的根节点表示整个地形表面，把根节点分成相同大小的4个块，每个块表示1/4地形表面，如此细分，直到满足所需的地形分辨率为止.基于四叉树结构的地形绘制方法见图1.
1 基于四叉树实时地形简化
对地形进行绘制时，遍历四叉树结构，在地形的不同区域选择不同子节点的地形块.使用四叉树结构对地形表面的简化一般通过2步实现：(1)对每一地形层次细节块通过基于顶点的简化方法删除顶点；(2)用基于块的简化方法确定地形的层次细节(选择子节点).
1.1 基于顶点的简化顶点简化开始时，四叉树块内的所有顶点都被考虑，只要简化条件满足，1对邻近的三角形被融合成单一的三角形.融合后的三角形如果满足简化条件，再与其他位于同一层次的三角形融合，依次递归迭代，直到块内所有顶点满足给定的误差阈值.三角形对的融合准则通过融合后顶点的屏幕空间误差确定，为简化误差矢量的计算，LINDSTROM等[5]假设误差矢量中点位于视点中心，由于透视变化的影响，该假设引起的误差矢量计算值小于实际值.在该假设下，所推出的误差计算公式为
式中：d为从视点e到投影平面的距离；λ为世界坐标系中单位向量覆盖的像素；δ为世界坐标系中顶点的误差；τ为用户定义的误差阈值；如果顶点v的屏幕空间误差满足δscreen≤τ，则对三角形对进行融合变换.
1.2 基于块的简化地形的高度场数据可能包括数百万个顶点高度值，如果采用顶点简化的方式实现分辨率网格简化，计算代价相当大，不能对每帧图像进行实时处理，因此首先需要划分简化范围.可以对四叉树层次结构中的每一块进行误差估计，判断是否需要对该地形块范围内的顶点进行简化，这样能有效降低实时简化的计算量.当四叉树中4个子节点表示的子块被其父节点替代时，每隔一行一列的顶点被删除.设被删除顶点的最大误差为δmax，给定块b可以被确定一包括该块的边界盒.在给定视点e和误差阈值τ的情况下，可以给出块的误差估计区间[δl，δh]，如果顶点误差δ值≤δl，则其屏幕空间误差不会超过τ；如果顶点误差值δ>δh，则其屏幕空间误差大于τ.当顶点误差位于区间内时，必须计算顶点的屏幕空间误差.设δ*max为块b所有子块对应δmax的最大值，若δ*max>δl，则块b所覆盖的地形块被删除的顶点误差超过阈值，因此需要用块的子块代替.对每一子块将δ*max和δmax与δl比较，如果δ*max>δl，则需要用高分辨率的块替代该子块，否则用其父块代替该子块.由于不确定误差区间的估计视点相关，对地形绘制的每帧图像的地形块都需要计算其误差区间，因此应尽可能减少其计算代价.LINDSTROM等[6]提出的误差区间计算式为
其中，f=(ex-vx)2+(ey-vy)2(ex-vx)2+(ey-vy)2+(ez-vz)2(4) 基于四叉树的连续多分辨率地形简化面临2个主要问题：(1)具有不同分辨率层次细节的地形块之间会存在网格裂缝；(2)不同层次细节地形区域转换时，因三角形顶点改变会引起视觉上的突变现象.
2 地形四叉树实时优化
针对采用四叉树表示地形时不同分辨率层次细节的地形块之间存在网格裂缝问题，提出基于过渡三角形有限融合方式的多层次细节LOD实时地形简化模型，见图2.
图2中：1表示低分辨率的四叉树地形网格；2表示高分辨率地形网格与低分辨率地形网格过渡时产生地形裂缝；3表示通过过渡三角形有限融合方式重新构网之后的四叉树形状.基于过渡三角形有限融合方式实现多层次细节LOD实时地形简化的关键问题是如何确定需要进行融合操作的较高精度和较低精度三角形.可以通过如下算法实现：(1)建立地形四叉树层次结构的同时计算节点的位置、颜色、层次和深度等信息，并存储在临时空间中；(2)遍历地形四叉树所有节点，根据存储的节点信息判断所有三角形是否包含多余顶点，设此判断为Bool变量A，如果A的属性为FALSE，则此节点连接的三角形无须进行融合操作，如果A的属性为TRUE，需要进一步判断；(3)根据存储的节点信息，判断该节点是否为地形边缘，设此判断为Bool变量B，如果B的属性为TRUE，则此节点连接的三角形也无须进行融合操作，如果B的属性为FALSE，此所有与次节点连接的三角形都需要进行融合操作.确定需要融合的三角形后，需要打破原有地形网格并重新构建新的地形网格.本文采用的方式是：移动A属性为TRUE和B属性为FALSE的三角形顶点到较低分辨率三角形长边的中点，该中点的所有属性为较低分辨率三角形长边包含的两个顶点的均值，在算法上很容易实现.
3 顶点误差估计优化
顶点误差指地形块细分前后顶点高度差的值，是多分辨率层次细节LOD实时地形简化的重要判断指标，顶点绘制误差过大将降低地形的实时简化模型精度.仿真地形顶点的误差主要与地形表面的起伏程度和视点位置距该点距离的大小有关，在进行地形实时简化时，具有较大误差概率的顶点应被细分，当两个顶点误差概率相同时，离视点更近的应被细分. LINDSTROM等[5，6]和DUCHAINEAU等[7]采用屏幕空间误差估计方法对实时三维地形顶点进行误差估计.但该方法具有以下缺陷：(1)当视点方向垂直于地面时，顶点误差并不可见；(2)忽略纹理透视误差和深度缓冲误差，即使顶点在平面空间没有运动，只是沿视点方向运动，顶点视空间的z值也会影响透视矫正和深度缓冲.
4 几何光滑过渡优化
采用多层次细节地形简化方式能有效提高大规模复杂地形的绘制速度，但由于不同层次细节的地形模型复杂度有较大差别，地形顶点的位置也有较大不同，从一个层次细节过渡到另一个层次细节时，会发生地形网格顶点位置的突变，造成视觉上难以接受的失真.为了减缓这种地形模型转换带来的突变效应，FERGUSON等[8]提出的解决方法是对存在突变的前后两帧地形进行几何过渡，LINSDTROM等[5，6]提出的解决方法是根据每个顶点在当前视点下简化的误差确定顶点是否需要过渡及过渡所需的参数.根据地形顶点误差估计的方式进行优化：定义两个顶点误差阈值τmin，τmax(τmax>τmin)，当顶点误差估计值处在两者之间时，顶点不是一步变化到实际的高度位置，而是进行逐渐光滑过渡.首先根据顶点的简化误差模型定义过渡参数Иt=ρv-τminτmax-τmin(6)И式中：τmin，τmax分别表示用户给定的两个顶点误差阈值；ρv表示顶点在当前视点下的误差估计值.当ρv≥τmax(即t≥1)时，新插入的顶点无须过渡；当τmin≤ρv≤τmax(即0≤t
5 试验与结论
采用式(9)与LINSDTROM等[6]提出的简化公式，针对某典型飞行训练环境绘制地形时的高程误差见表1.
为便于对比分析，从地形规模和实时绘制帧率两方面进行比较.用于比较的机器硬件配置情况是：CPU为P4双核3.0 GHz；内存2 GB；显卡Gerforce 6800，128 MB；硬盘容量160 GB，转速7 200 r/min.地形情况为：整体DEM分辨率为30 m间隔；纹理分辨率为15 m，每50 km×50 km范围内包含一典型飞机场；机场5 km×5 km范围内纹理分辨率为1 m；15 km×15 km范围内纹理分辨率为5 m.比较对象是基于Vega平台的典型虚拟现实仿真环境.地形规模和实时绘制帧率变化情况对比见表2.
大规模复杂地形的实时绘制是当前飞行模拟器领域的主要研究内容之一，地形绘制的真实感和实时性直接影响到飞行仿真的沉浸感和交互性，因此模拟器对地形的仿真要求永无止境.根据仿真内容的不同有针对性地优化地形是1种见效较快的方式，但该方式的缺点是通用性不强，在此基础上研究各种关键参数的自适应优化，根据仿真地形的不同特点自动进行调整是下一步的工作.
参考文献：
[1]MOURANT R R，REFSLAND D. Developing a 3D sound environment for a driving simulator[C]// Proc Ninth Int Conf on Virtual Syst & Multimedia，Montreal，Canada，2003：711-719.
[2]DESBRUN M，MEYER M，ALLIEZ P. Intrinsic parameterizations of surface，meshes[C]// Proc Eurographic 2002：434-440.
[3]BLOW J. Terrain rendering at high levels of detail[C]// Proc 2000 Game Developers Conf，2000.
[4]AI Jixi. An approach to generate 3D animation by integrating building model into site pictures[C]// CAADRIA2000.
[5]LINDSTROM P，PASCUCCI V. Visualization of large terrains made easy[C]// IEEE Visualization 2001，2001：363-370.
[6]LINDSTROM P，PASCUCCI V. Terrain simplification simplified：a general framework for view-dependent out-of-core visualization[C]// IEEE Trans Visualization & Comput Graphics，2002：329-336.
[7]DUCHAINEAU M，WOLINSKI M，SIGETI D E，et al. ROAMing terrain：real-time，optimally adapting meshes[C]// Proc Conf on Visualization’97，1997：81-88.
[8]FERGUSON R L，ECONOMY R，KELLEY W A，et al. Continuous terrain level of detail for visual simulation[C]// Proc 1990 IMAGE V Conf，Tempe，Arizona，1990：144-151.
“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文”