飞行模拟系统、VR系统、3D游戏及数字地球等都离不开大规模地形的实时渲染技术。快速而高效地渲染地形是计算机图形学的研究热点，也是三维系统建模的一个关键技术。

    近年来，真实感DEM数据来源丰富、数据量庞大、精度高，全分辨率显示地形可行性已变得简单易行。因此，模型简化技术、多分辨率表示和LOD(Level of Detail)技术成为近年来研究的热点[1]。基于多层次细节的实时优化自适应网格动态地形渲染算法ROAM(Real—time Optimally Adapting Meshes)凭借其简单性和可扩展性成为解决海量高程数据地形可视化的常用方法[2]; 基于分块的ROAM算法在处理大规模数据时取得了较好的渲染效率[3];基于金字塔思想的ROAM算法对大数据量地形及纹理数据进行分层分块预处理和块内LOD预处理，提高了渲染效率[4]。这些，都是基于传统的ROAM算法进行的改进。传统意义上的ROAM算法使用Triangle-Bintree实现存储三角形坐标[5]。
    基于钻石节点ROAM算法的基本数据结构是钻石节点。基本数据结构的不同，使基于钻石节点的ROAM算法在实现上与传统ROAM算法存在极大的差异；数据结构的更加对称，使算法拥有更快的渲染速度，在三维系统建模中，有利于提高三维系统的运行效率。本文研究了实现钻石节点的基本数据结构及算法的关键技术，并将视点与地形复杂程序的节点误差公式应用到算法中，提升了算法渲染速度。
1 基于钻石节点的ROAM算法介绍
1.1钻石节点数据结构
1.1.1基本数据结构
    基本钻石节点包括唯一一条用于区分的对角线(对角线将钻石节点划分为2个共斜边的等腰直角三角形)、一个中心顶点C及其包围球半径R[6],如图1所示。同时，每个钻石节点有4个父钻石节点和4个孩子钻石节点，如图2、图3所示。

      对于每个钻石节点来说，父钻石节点指那些与当前钻石节点重叠，且细节层次较低的钻石节点。父钻石节点分为两种：一种是位于对角线上的钻石节点(图2中的a0和a2),称为祖先节点；另一种是只包含当前钻石节点的一部分，细节层次只比当前钻石节点的细节层次低一级，称为父亲节点。图2中虚线标注的a1和a3即为这类节点，其中a1为右父亲，a3为左父亲。


    如果当前钻石节点有孩子，则需要对其孩子递归地执行以上删除操作[7]。
1.2 算法描述
1.2.1 地形数据管理
　　在基于钻石节点的ROAM算法中，为使地形更快、更准确地渲染，高程数据大小要求为(2N+1)×(2N+1)。
　　本文使用原始数据大小为1025×1025的DEM高程数据，每个高程点均可视为一个钻石节点的中心点。根钻石节点的中心点位于(512，512)，且4个父节点位于地形块的4个角。事实上，地形块4个角上的节点并不是完整意义上的钻石节点，称为“伪钻石节点”。引入“伪钻石节点”只是为了体现算法的完整性。根钻石节点的4个孩子钻石节点中心点坐标为(0,512)、(512,0)、(1 024,512)、 (512,1 024)。根钻石节点位于0级细节层次，4个孩子位于1级细节层次。随着渲染深度的增加，使得细节层次增加，需要渲染的钻石节点数也增加。
    每一个L级细节层次的钻石节点在L-1级有2个父亲节点，在L+1级有4个孩子节点。如果等级L的钻石节点的对角线与坐标轴平行/垂直，则等级L+1的钻石节点的对角线就与坐标轴形成45°夹角。在处理地形边界时,将不存在的父钻石节点指针设置为空。
1.2.2 双队列优先
　    分裂与合并优先队列的引入，避免了ROAM算法每次渲染时都必须从根节点开始分裂，并且很好地利用了帧与帧之间的相关性，极大提升了ROAM算法的渲染速度[5]。基于钻石节点的ROAM算法,在合并队列与优先队列中保存的是钻石节点的指针，并为每一个钻石节点保存一个优先级，优先级最高的钻石节点位于队列的最前端[6]。
　    当细节层次低于要求时，寻找分裂优先队列里优先级最高的钻石节点d，并分裂d，分裂操作如图5所示。当细节层次高于要求时，寻找合并优先队列里优先级最高的钻石节点d，并合并d，合并操作如图6所示。

1.2.3 节点误差
　    传统ROAM算法中，分裂与合并优先级根据节点的空间误差来确定，空间误差越大，分裂优先级越高，合并优先级越小。参考文献[5]和参考文献[8]提出了一种基

其中MapSize为整个地形的尺寸;C为可调因子，可根据实际调节，以达到最佳渲染效果。
1.2.4 视锥体裁剪
    包围球的计算基于三角形面片，每个钻石节点包括2个三角形。为每一个钻石节点计算包围球半径时，需要计算钻石节点中点分别到4个父亲顶点的距离，选出最长的距离作为其包围球半径[6]。测试可见性时，将每个钻石节点包围球与视锥体6个平面进行测试，当钻石节点的包围球位于视锥体内时才进行渲染，以提高渲染速度。
2 算法实现流程
　 地形初始化之后，首先根据当前视点渲染地形。渲染过程中,当钻石节点可见性发生变化时，需要根据节点误差确定已变化的钻石节点优先级，并放入相应的优先队列。当判断地形细节层次没有达到要求时，将进行相应的分裂或合并操作，由此产生新的钻石节点并同样需要判断其可见性，然后根据可见性更新需要渲染的三角形列表，最后将所有需要渲染的三角形渲染到屏幕，渲染过程如图7所示。

3 实验及分析
　本文算法采用VC6.0++和OpenGL来实现。实验仿真的DEM数据量大小为1 025×1 025。计算机配置为：Intel Celeron CPU 1.73 GHz处理器，1  GB内存,ATI RADEON
XPRESS 200M Series集成显卡，Windows XP操作系统。
    图8所示为只考虑视点，不考虑粗糙度的地形时，钻石节点在平坦和粗糙的地方均匀分布。图9、图10所示为使用了节点误差公式之后的地形，当粗糙度大或者距离视点近的地形采用更多的钻石节点渲染。在节点误差公式中可调因子C取值不同，而视点相同的情况下，地形显示的细节层次不同。由结果可以看出，渲染当前地形C取值为0.001时较为理想。
    图9所示地形每秒渲染的三角形数目为5 049个，比图8所示的10 893地形减少了一半左右，渲染帧率从110帧左右提高到200帧左右，并且所示地形基本保持一致。因此，综合考虑视点与地形粗糙度，可以在提高地形渲染效率的同时，保持原有的地形地貌不变。

    本文详细阐述了钻石节点数据结构，对基于钻石节点的ROAM算法实现过程中的关键技术进行了分析，并根据钻石节点结构特点，综合考虑视点与地形粗糙度，提出了合理的节点误差计算公式，最后用OpenGL和VC6.0++进行了算法和公式有效性验证。实验结果表明，在使用本文提出的节点误差公式计算之后，渲染效率大幅提高，完全满足交互式漫游的需求。
    基于钻石节点的ROAM算法与传统的ROAM算法相比，钻石节点更加对称的数据结构更适于程序渲染。将其应用到灌区三维系统建模中，实现三维地形地貌的快速渲染，是进一步研究的重点。
参考文献
[1] 曹敏，杨长兴，杨炼.大规模地形漫游中动态LOD算法研究[J].计算机技术与发展，2008,18(10):187-189.
[2] 魏楠，江南.ROAM算法及其在地形可视化中的应用[J].计算机工程与科学，2007,29(2):66-68.
[3] 侯能，黎展劳，韦婷. 基于分块ROAM算法的设计与实现[J]. 科学技术与工程, 2011,11(26):6459-6462.
[4] 杨冠军，陈洪，朱德海.基于金字塔思想改进的ROAM算法[J].电子技术应用,2007,33(8):130-132.
[5] DUCHAINEAU M,WOLINSKY M,DAVID E,et al.ROAMing Terrain: real-time optimally adapting meshes[C]. Proceedings of the Conference on Visualization 97,1997.
[6] POLACK T. Focus on 3D terrain programming[M]. Premier Press, 2002.
[7] LOK M, MARK A. MEMBER D, et al. Realtime optimal adaptation for planetary geometry and texture:4-8 tile hierarchies[J]. IEEE Transactions on Visualization and Computer Graphics, 2005,11(2):6-8.
[8] LOSASSO F, HOPPE H. Geometry clipmaps: terrain rendering using nested regular grids[C]. ACM Siggraph, 2004.
[9] 王金， 杨克俭. 基于ROAM的实时动态地形可视化研究[J].计算机与现代化，2011(5):57-60.