摘 要： 介绍了对传统的实时优化自适应网格算法" title="实时优化自适应网格算法">实时优化自适应网格算法的改进。首先根据金字塔思想" title="金字塔思想">金字塔思想，对大数据量地形及纹理数据进行分层分块预处理，对每块数据进行细节层次处理，并建立统一的空间位置索引，存入磁盘。然后应用缓冲区机制及多线程思想，结合该算法，渲染了北京市怀柔水库三维地形，并进行网络实时漫游，效果理想。
    关键词： 实时优化自适应网格算法  金字塔思想  细节层次

    三维场景的实时渲染技术一直是计算机图形学中研究的热点，其应用领域十分广泛，如GIS系统、飞行模拟系统、VR系统、视频游戏以及数字地球技术等^[1]。特别是随着数字地球概念的提出，大规模数字高程模型的实时可视化技术显得尤为重要。然而，庞大的数据集对于目前的图形硬件设备仍存在极大的压力^[2]。因此，众多学者对细节层次LOD(Level Of Details)这一真正的三维地形渲染技术进行了深入的研究，也得出了许多经典的LOD算法，如：连续LOD(CLOD)、ROAM LOD和分块LOD（Chunk LOD）等^[3]。其中，实时优化自适应网格算法ROAM(Real Time Optimally Adapting Meshes)LOD，以其简单和可扩展性的特点成为地形渲染中广泛应用研究的算法[4]。根据该算法，本文提出基于金字塔思想改进的ROAM算法，以期进一步提高大规模地形实时可视化的效率。
1 传统ROAM算法
1.1 算法思想
    ROAM描述了一个基于二元三角树结构的法则，它包含一个预处理过程和几个实时处理阶段。预处理过程对三角形二叉树" title="二叉树">二叉树从底至顶进行嵌套的、观察依赖的误差范围计算^[4]。其基本思想是：在对地形进行三维渲染时，依据视点的位置和视线的方向等多种因素，对表示地形表面的三角形片元进行一系列的基于三角形二叉剖分的分裂与合并，最终形成和原始表面近似且无缝无叠的简化连续三角化表面^[2]。
1.2 二叉三角树
    ROAM算法中的基本数据单元就是等腰直角三角形片元，通过从其直角顶点到斜边递归" title="递归">递归的二叉剖分，形成具有层次结构的二叉三角树，如图1所示^[5]。其根结点T(V_a,V₀,V₁)定义为最初的等腰直角三角形，此时层次L为0。当层次L为1时，将根结点三角形T分割为T₀和T₁，分割是递归进行的，直至达到希望的细节层次^[5]。二叉三角树采用SBinTree结构保存，同时存储五个最基本的数据，它们构成合并与增加三角形操作的基础，也是LOD得以实现的关键所在。每一个二叉三角树通过这五个元素同它周围的二叉三角树产生联系，只要一个树的结构发生变化，必将影响到整个地形块的变动^[6]，如图2所示。二叉三角树数据结构如下：
    struct SBinTree
    {
        SBinTree *LeftChild;  //左子树
　　    SBinTree *RightChild;  //右子树
　　    SBinTree *BaseNeighbor;  //底邻接区
　　    SBinTree *LeftNeighbor;  //左邻接区
　    SBinTree *RightNeighbor; //右邻接区
    }

1.3 分裂与合并
    评价体系是决定三角形分裂与合并的标准，评价体系与视点的距离和地形本身的粗糙程度两个因素有关。离视点越远、地形越平坦，二叉三角树越浅，就需要对三角形进行合并；反之则进行分裂。
    分裂与合并是实现ROAM算法的基本操作。为了避免在分裂与合并的过程中出现裂缝和T形三角形，在操作时必须记录三角形片元的拓扑关系并动态更新其拓扑关系。图3为二叉三角树的分裂与合并示意图^[5]。图中T被分裂为T₀和T₁，由于其底邻接区T_B与T位于同一钻石形中，因此T_B也被分裂为T_B0和T_B1。

    如果三角形T与其底邻接区T_B不位于一个钻石形中，就不能立即分裂T，必须首先强制分裂T_B，依此递归遍历整个网络，直至找到两个三角形位于同一钻石形之中为止，如图4所示^[5]。

2 基于金字塔思想改进的ROAM算法
2.1 算法基本原理
    传统ROAM算法是根据评价体系将整个地形进行LOD处理，三角形的分裂与合并均是在程序运行中进行的，而且对纹理数据一般都不加处理直接映射到地形数据上，这势必增加内存的开销，影响运行的速度。在大数据量三维地形漫游过程中，距离视点较近时，看到的只是屏幕内的地形，无需处理整个地形；而距离稍远、较平坦的地形，只需用较低的细节层次便可以得到很好的渲染效果，而无需与陡峭的地形用相同的细节层次，即相同的视点距离、不同的地形块，可以使用不同的分辨率加以显示，而且地形数据大，纹理数据也会很大。基于此，本文提出基于金字塔思想改进的ROAM算法，对三维地形数据以及纹理数据依金字塔思想进行数据预处理，预处理分为两步： 数据的分层分块处理和块内的LOD处理。
    首先根据场景数据的大小，确定需要分的层数，上层分辨率小于下层，再从上层到下层进行四叉树剖分，如图5所示^[7]，由此各个不同层将由不同分辨率的地形块组成；然后根据每一层每一块的分辨率大小以及粗糙程度进行LOD处理，直至把每一层的每一块数据写入磁盘，这些处理都是在渲染前完成。此方法相当于建立了三维地形及纹理库，将与特定区域相关的数据有效地组织起来，通过空间坐标将可视范围与其范围内的数据关联起来，并分配统一的空间位置索引，以便快速调度三维库中的数据，从而达到对整个地形的无缝漫游^[7]。这对于地形的层次细节模型的实时建立有着重要的意义。在渲染时，以块为单位，根据视点的位置，调出相应的数据块" title="数据块">数据块。距视点越远的地方，渲染的是层数越高（分辨率小）的块，距视点越近的地方，渲染的则是层数越低（分辨率大）的块。计算出需要渲染的块后，进入渲染管道，最后渲染出三维地形场景。

    此外，为了提高渲染效率，本文还利用了缓冲区机制和多线程调度的方法。因为漫游通常是在某一场景的周边进行的，所以刚刚渲染完的数据不应该立刻卸载，而是存入缓冲区内，当后台线程获得预渲染的数据块，首先查找缓冲区，如果没有则继续搜索磁盘。
2.2 数据的LOD处理
    首先确定一个最大几何误差值δ，即观看最清晰的场景所能接收的误差。如果地形数据分为10层，则第9层数据分辨率最高，此时几何误差不超过δ，第8层几何误差不超过2δ，第7层几何误差不超过4δ，依此类推。
    在计算误差时，并不存储屏幕误差值，而是存储某层可以接收的误差值，即存储的是每个点能接收的层数。这样做的好处就是能节省一定的内存。因为误差的范围很大，而层数是有限的，所以只需很少的字节来存储层数即可。计算层数的公式为：

    Level=|log₂(δ+0.5)|

式中，δ为几何误差，对每个点做完误差处理后，取块数据内点的最大误差作为此块数据能接收的误差值。块数据采用Block结构来保存，其结构如下：
    struct Chunk
    {
　　    int chunkindex;      //块的索引
　　    int  eastindex, northindex, westindex, southindex;  
                             //四个子节点的索引
　　    unsigned char LOD_level;     //所在的层数
　　    short xindex,zindex;          //块在该层中的位置
　　    short min_y,max_y;                //该块的最小高程以
                                            及最大高程
　　    int mesh_pos;               //三角网数据的位置
    }
2.3 应用实例
    根据本文所述算法，在1.7GHz CPU、256MB内存、32MB显卡的计算机上，应用VC++6.0以及OpenGL开发了2 049×2 049的DEM三维地形渲染的ActiveX控件，将此地形数据分为8层，在网络上进行实时漫游，其效果如图6所示。帧率达到83fps，而应用传统的ROAM算法，帧率只有60fps。

    本文提出了一种基于金字塔思想改进的ROAM算法。该算法的创新之处在于对大数据量地形及纹理数据进行分层分块预处理和块内LOD预处理的双重预处理，并存入磁盘中，建立统一的空间索引，而且预处理均是在渲染前完成。当程序运行时只需不断检索加载数据，而且当视点移动很快时，CPU消耗也很低，不会增加系统负担。渲染时又应用了缓冲区机制和多线程思想，进一步提高了渲染效率。为支持超大数据量的地形及纹理数据三维渲染提供了一种思想。目前笔者正在进行此方面的深入研究。
参考文献
[1] 黄超超,凌永顺,吕相银. ROAM动态地形渲染算法研究[J]. 计算机仿真,2005,22(1):216-219.
[2] 周宏伟,杨平,陈琦. 实时地形可视化ROAM算法的分块改进[J]. 测绘通报,2003,(8):61-63.
[3] 江流长. ROAM地形渲染算法的实现[J]. 农业网络信息,2006,(5):42-44.
[4] 涂超. ROAM算法原理及其应用研究[J]. 辽宁工程技术大学学报，2003,22(2):176-179.
[5] DUCHAINEAU M, WOLINSKY M, SIGETI D E. Realtime optimally adapting meshes[J]. Proceedings of the Conference on Visualization, 1997:81-88.
[6] 解志刚,马秋禾,赵金萍. 基于二叉树结构的地形分块实时漫游的研究[J]. 海洋测绘,2004,24(5):35-38.
[7] 刘修国,张剑波. 基于DEM库的地表模型实时简化方法[J]. 小型微型计算机系统,2004,25(2):280-282.