基于约束误差判据的动态地形可视化算法

于 萍， 张彩明

（1. 淄博师范高等专科学校信息科学系，山东 淄博 255130；2. 山东大学计算机科学与技术学院，山东 济南 250101）

地形可视化是是虚拟地理环境中不可缺少的组成部分，目前国内外研究地形绘制主要基于层次细节（Level of Detail, LOD）模型技术。但在已有的大多数LOD算法[1-3]中，均隐含着一个相同的假设条件，即假定地形表面各处的高程值和颜色等物理属性，在系统运行过程中是固定不变的。然而汽车等运载工具在松软的地表上行驶会留下清晰的轮胎印迹、炸弹在地面上爆炸会产生弹坑。像这种地形表面各处的高程值和颜色等物理属性在系统运行过程中不断变化的动态地形并不满足假设条件。并且动态地形的实时可视化对构建高逼真度的仿真环境具有重大的现实意义，也是视景仿真领域必须解决的重大问题。

利用LOD绘制大规模地形主要考虑3方面技术：数据组织方式，方便LOD模型生成并避免T-连接和裂缝的产生；误差判据，减少每帧需要绘制的三角形数目提高算法效率并保证地形有较强的真实感；性能优化，帧间连贯性、视锥剔除、三角形条带化等技术优化算法性能提高算法效率。其中，误差判据决定了当前视点下，不同分辨率的地形模型需要绘制的三角形结点。因此，误差判据决定着每帧需要绘制的三角形结点个数，取值的大小直接决定着渲染地形的真实度和算法效率，是LOD中的关键技术。对于动态地形，在地形发生动态形变（即地形的高程值和颜色等属性发生变化）时，更希望通过误差判据能较好的体现地形形变效果，增强形变地形的真实感。目前对于误差判据的研究大致可以分为两类。

一类是考虑视点因素[1-4]。与视点相关的误差计算，常使用屏幕空间误差方法。其主要有两种方法：基于距离及视向的屏幕空间误差计算法[5-6]和只基于距离的屏幕空间误差计算法[4,7]。通过理论分析和实验结果的对比指出：基于距离及视向的屏幕空间误差计算法和只基于距离的屏幕空间误差计算法，采用相同的屏幕误差阈值对同一分辨率地表网格模型进行视点相关的简化时，两种简化方法的简化率相差不大。因此，只基于距离的屏幕空间误差计算，因其计算简单得到广泛的应用[7-9]。

另一类考虑地形粗糙度因素[10-11]。地形粗糙度反映的是地形局部起伏剧烈程度的特征量，是较好的体现地形真实感的重要因素。对于较平坦的区域，可以用较低分辨率的三角网格表示；对于起伏较大的区域，需要用较高分辨率的三角网格表示。文献[10]采用局部误差计算方法，结点误差由结点周围5个结点的误差和结点本身误差的最大值表示，会有一定程度“跳跃”感的产生。文献[11]提出的粗糙度计算方法需要从叶子顶点开始向上递归计算所有非叶子顶点的误差，在地形发生动态形变时，也会增加算法的耗费时间，降低算法效率。

动态地形可视化需要在地形发生形变后能较好的体现地形局部形变效果，但又需满足地形实时绘制的要求。为此，本文利用局部地形的粗糙度构造约束条件，加入视点因素后形成带约束的嵌套误差判据方法。不但可以很好地体现地形的形变效果，刻画局部地形细节，还能隐式的避免T-连接和裂缝的产生，同时降低较平坦区域冗余三角形的产生。从而在保证动态地形有较强真实感的前提下，减少每帧中需要绘制的三角形结点个数，提高算法效率。

1 带约束误差判据的可视化算法

本文算法采用基于DAG的三角形二叉树存储结构，利用带约束的误差判据计算误差，用较少的冗余三角形有效避免T-连接和裂缝的产生。同时利用延迟判断的帧间连贯性，减少每帧的绘制时间提高算法效率。

1.1 基于DAG的三角形二叉树

本文用三角形二叉树[3,8,10]结构存储需绘制的三角形信息。将初始平面的正方形区域划分为两个等腰直角三角形，并把他们定义为位于二叉树的最顶层。对于顶层三角形，连接直角顶点和其斜边的中点，三角形被平分为两个子三角形，定义这两个子三角形位于下一精细层，并称顶层三角形为其父亲。递归执行该操作，可生成层次结构的三角形二叉树。在三角形二叉树的构造过程中，实际上还隐含着严格的顶点引入次序。这种引入次序可用顶点的有向非循环图DAG(Directed Acyclic Graph) 来描述。

1.2 带约束的误差判据

只基于距离的屏幕空间误差计算，虽然计算简单应用广泛，但没有考虑地形本身的起伏状况。并且为避免T-连接和裂缝的产生，通常会增加冗余三角形。为此，利用局部地形的粗糙度，构造约束因子在体现地形本身起伏程度的同时降低冗余三角形个数。

1）约束因子

为了减少冗余三角形个数体现局部地形细节，利用地形粗糙度构造约束因子。考虑到动态地形运行中发生的形变，需要实时计算误差函数，为减少实时计算量，本文提出基于方差的局部粗糙误差函数。所谓局部粗糙度是指误差中方差不是计算整个地形的方差，而是以结点为中心包含周围结点的局部区域方差。主要考虑顶点附近局部区域的高程值对该顶点高程值的方差累计效果。取局部地形M×N，点i处构造局部粗糙误差函数公式如下：

其中，Z(x,y)为局部地形顶点(x,y)的高程值，Zi为该顶点的高程值，n=M×N。利用局部粗糙误差函数，构造值域在(0,1)区间内的顶点约束因子ki，具体计算公式如下：

若地形起伏较大，则fi的值较大，此时ki的值较大接近1。若地形较为平坦，则fi的值较小，此时ki的值较小。但地形平坦到接近平地时，会出现fi的值小于1，甚至为0的情况，此时ki的值反而较大，不能准确表示地形的粗糙程度。为此，在分母上修正fi为fi+1+ξ，以保证分母fi和ki的值不为0，其中ξ为接近0的极小数。如公式（3）所示。

2）带约束的误差判据球

与视点相关的误差计算考虑的是∆ABC在引入斜边AD后所产生的顶点空间误差，用引入斜边前后高程值差的绝对值表示δD=|ZD-(ZB+ZC) /2|。由此得到的只基于距离的屏幕空间误差计算公式为：

其中，λ表示对象空间中的单位长度，τ表示屏幕的空间误差；p，e分别为结点、视点在三维对象空间中的位置；d为视点到屏幕平面的距离；δ表示与结点相对应的对象空间误差。

在给定屏幕空间误差阈值τ后，可以得到结点原始误差判据球半径为：

该式可看作在三维空间中以顶点i为球心,半径为ri的球面, 称之为顶点i的原始误差据球。但 只基于视点考虑的误差判据球没有考虑地形局部粗糙程度，会产生一定的冗余三角形。为减少较平坦地区冗余三角形的产生，同时保留局部起伏较大区域的层次细节，利用地形局部粗糙度构造的约束因子ki约束误差判据球。得到：

但利用带约束的误差判据球，在绘制地形时不可避免的会出现T-连接和裂缝。所谓T-连接是指一个三角形或多个三角形共享另一个三角形的一条边的一部分。T-连接容易在绘制时产生地形裂缝，即使不产生裂缝，在绘制时T-连接出现的地方也会产生不连续的点，给人不真实的感觉。为此，利用嵌套误差判据球将各个顶点间的包围关系隐式的包含在误差评价函数中，从而使所有需要分裂的子结点在绘制前其父结点早已分裂。因此，对与非叶子顶点需计算其嵌套误差判据球，确保孩子顶点要求分裂时父结点都已经分裂。修改后顶点的带约束嵌套误差判据球，球心仍是该顶点的空间位置，半径计算公式如下：

其中，ri为由式（6）所确定的顶点i的带约束误差判据球半径，pi、pj分别为顶点i及其孩子顶点j的空间位置，Ci为DAG中顶点i的孩子集合，Rj为顶点j的嵌套误差判据球半径，称式（7）所定义的误差判据球为顶点的嵌套误差判据球。

3）动态形变后的误差计算

若地形在实时绘制阶段发生动态性变，为尽可能的减少实时绘制中算法的计算量，本文采用与静态地形不同的处理方法。给每个发生形变的顶点增加一位表示地形形变的标志位，当实时绘制中地形发生动态形变时，通过改变标志位状态来确定发生形变的地形区域顶点。对形变区域的顶点重新计算其嵌套误差判据球，并利用预处理时生成的DAG计算其祖先的嵌套误差判据球。在计算形变区域的顶点的祖先嵌套误差判据球时，并不需要计算所有的祖先结点，当重新计算的祖先结点的嵌套误差判据球没有改变时，即可停止其它祖先结点的误差计算。

1.3 帧间连贯性

视点连续移动时，相邻帧间地形的层次细节模型具有很大的连贯性，需绘制的三角形变化不大。因而利用帧间的连贯性[8-9]，对实时显示的地形进行处理。从前一帧中显示的三角形二叉树的结点出发，根据当前视点的变化情况，判定下一帧需要绘制的结点。对视点离开其嵌套判定误差球的顶点进行合并操作，对视点进入其嵌套判定误差球的顶点进行分裂操作，对其它前一帧中显示的顶点可直接显示。考虑到ΔABC，如图1所示，E表示视点位置，当E进入半径为r的误差判据球区域内时，ΔABC才需要分裂，当E离开半径为R的误差判据球区域时，ΔABC才需要合并。而当视点E在两个误差判据球间移动时，ΔABC无需进行视距与误差判据球的判断可直接显示。因此，本文利用延迟因子，预测出顶点在当前视点移动速度下，最长延迟分裂或合并的次数。对上一帧中显示的顶点，若其延迟因子递减后非零则无需判断可直接显示。从而无需判断上一帧中所有显示的顶点，以减少实时绘制时的计算量，提高算法效率。若地形在实时绘制阶段发生动态性变，除了重新计算形变区域的顶点嵌套误差判据球外，还需重新计算形变区域各个顶点的延迟因子。并在计算后对形变区域的各个结点重新判断，确定顶点是否需要判断。

图1 延迟示意图

2 实现和分析

在PC机上实现了算法，并利用实验地形数据进行了相关实验。实验硬件环境为：Intel P4 2.0GHz, 256M RAM, nVIDI2 A GeForce2 400 显卡；软件环境为：Windows 2000, VC6.0和OpenGL。

1）静态地形误差和效果图比较

利用实验地形数据[13]中的crater、island、maui 3个地形，分别对文献[3]、文献[11]和本文方法进行了比较。实验中局部粗糙度因子取3×3局部地形高程值。对每个地形数据分别就其某视点下渲染的三角形个数和全局高程差进行了对比，如图2、图3所示。由图2可以看出在地形渲染过程中本文算法所需绘制的三角形个数在多数情况下能明显的低于文献[3,11]。由图3可以看出全局高程差3种计算方法相差不大。

图2 3种地形下3种方法的三角形渲染个数对比

图3 3种地形下3种方法的全局高程差对比

图4 和图5分别是某视点下，对较陡峭地形和较平坦地形的绘制效果图，依次分别为全部三角形绘制，文献[3]、文献[11]和本文算法的比较，由图4、图5可以看出，虽然本文算法减少了绘制的三角形数目，但仍然能够很好地体现地形地貌。

2）动态形变性能和效果比较

对地形发生动态形变的区域对比了文献[11]和本文方法。图6为文献[11]和本文方法渲染的地形形变效果图，由图可以看出本文方法能很好的用较少的三角形绘制地形的形变效果。图7比较了两种方法在形变时的平均帧速、三角形个数和全局高程差，由图可以看出本文方法在绘制时间和绘制三角形个数上明显优于文献 [11]，而全局高程差两种方法差不多。

图6 动态形变效果比较

图7 动态形变帧速、三角形个数和全局高程误差比较

3 结 束 语

本文利用视点和地形本身粗糙因素，提出一种带约束的误差判据方法。该方法在隐式避免T-连接和裂缝生成的前提下，能有效地减少冗余的三角形结点个数，较好地提高算法效率，并且在地形发生形变时，能较好地体现地形的形变效果。实验结果表明，该方法在保证地形有较强真实感的前提下，能很好地减少三角形个数，提高算法效率。

[1]Lindstrom P, Koller D, Ribarsky W, et al. Real-time continuous level of detail rendering of height Fields [C]//Proceedings of SIGGRAPH’96, New Orleans, 1996: 109-118.

[2]Hoppe H. Smooth view-dependent level-of-detail control and its application to terrain rendering [C]//Proceedings of IEEE Visualization’98, New Caledonia,1998: 135-142.

[3]Duchaineau M, Wolinsky M, Sigeri D E, et al. Roaming terrain：real-time optimally adapting meshes [C]//Proceedings of IEEE Visualization’97, Phoenix, 1997:81-88.

[4]Lindstrom P, Pascucci V. Visualization of large terrains made easy [C]//Proceedings of IEEE Visualization’ 2001, san Diego, 2001: 363-370.

[5]赵友兵, 石教英, 周 骥, 等. 一种大规模地形的快速漫游算法[J].计算机辅助设计与图形学学报, 2002,14(7): 624-628.

[6]陈少强, 朱铁稳, 李 琦, 等. 大规模多分辨率地形模型简化生成方法[J]. 计算机辅助设计与图形学学报, 2005, (2): 273-278.

[7]王林旭, 李思昆, 潘晓辉. 动态地形的实时可视化[J].计算机学报, 2003, (11): 1524-1531.

[8]He Yefei, Cremer J, Papelis Y. Real-time extendibleresolution display of on-line dynamic terrain [C]//Proceedings of Graphies Interface, Calgary, Alberta.2002: 27-29.

[9]Chen Guojun, Zhang Jing. Dynamic terrain LOD with region pres ervation in 3D game engine [C]//Proceedings of the First Inte rnational Conference on E- Learning and Games, LNCS 3942, 2006: 711-715.

[10]RÖttger S, Heidrich W, Slusallek P, et al. Real-time generation of continuous lebels of detail for height fields [C]//Proceedings of the 6th International Conference in Central Europe on Computer Graphics and Visualization, 1998: 313-322.

[11]陈国军, 崔保磊, 陈庆刚. 生成地形细节层次的粗糙度误差判据[J]. 中国石油大学学报, 2009, (10):168-172.

[12]DISCOE Ben Elevation file repository [EB/OL].http://www.vterrain.org/BT/index.html 2007-09-11.