基于Diamond的ROAM算法研究*

王智利，宁 芊

（四川大学 电子信息学院，四川 成都 610065）

飞行模拟系统、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为左父亲。

孩子钻石节点是那些与当前钻石节点部分重叠，并且细节层次比当前钻石节点高一级的钻石节点，如图3所示。当前钻石节点的4个孩子钻石节点逆时针方向顺序为 c0、c1、c2、c3。

钻石节点与其父亲与孩子之间用指针连接,表示为：d→ai,d→ci(i=0,1,2,3)。

1.1.2 访问关键技术

渲染过程中经常需要访问相同细节层次的邻居钻石节点。假设d和d0是同一细节层次的钻石节点，并且它们同时是d的右父亲节点a1(指针表示为d→a1)的孩子。假设 d是d→a1第 i(i=0,1,2,3)个孩子，索引表示为a1i，则按照逆时针方向，d0将是 d→a1的第(a1i+1)mod4个孩子。

算法实现过程中，相同细节层次的钻石节点之间的访问操作十分频繁。为了提高访问性能，可以将d作为其右父亲 d→a1的第a1i个孩子和d作为其左父亲d→a3的第 a3i个孩子的索引,将 a1i、a3i存储在 d的数据结构中。则：

通过c0对角线所在的边访问d0可以表示为：

细节层次增加时，需要为当前钻石节点增加孩子节点。为d增加孩子节点c=d→c0时，首先要判断c的另外一个父亲d0是否存在，如果不存在，则需要递归地将d0添加到其父亲节点d→al的孩子节点中。新添加的孩子c有两个父亲 d和 d0，d是左父亲还是右父亲与 c的祖先a0的确定有关。由图4可以看出，c的祖先有d→a0和 d→al,考虑到 c的父亲 d的连接关系(d→a0)，c→a0取d→a1。接下来，按照逆时针方向，确定出 c的连接关系如下：

当删除一个钻石节点时，如果当前钻石节点没有孩子，则只需要将其左右父亲中指向该钻石节点的孩子指针置为空，表示如下：

如果当前钻石节点有孩子，则需要对其孩子递归地执行以上删除操作[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]提出了一种基于嵌套的世界空间范围的节点误差计算方法，该方法虽然精确，但计算复杂、速度慢。本文使用了一种基于视点与地形粗糙度的节点误差计算方法。在基于视点的LOD算法中，节点的误差主要由两个因素决定：一是节点到视点的距离;另一个则是地形本身的粗糙程度[9]。

在基于钻石节点的ROAM算法中，基本的数据结构为钻石节点，视点到观察节点的距离可以用钻石节点中心点的距离到视点距离来表示：

地形粗糙度采用钻石节点中心点实际高程值与左右父亲实际高程值的平均值计算。用公式表示如下：

实际渲染过程中，对地形的细化与地形粗糙度成正比，与视点到节点的距离成反比。同时本文还考虑到地形尺寸的影响，得到一个误差计算公式：

其中MapSize为整个地形的尺寸;C为可调因子，可根据实际调节，以达到最佳渲染效果。

1.2.4 视锥体裁剪

包围球的计算基于三角形面片，每个钻石节点包括2个三角形。为每一个钻石节点计算包围球半径时，需要计算钻石节点中点分别到4个父亲顶点的距离，选出最长的距离作为其包围球半径[6]。测试可见性时，将每个钻石节点包围球与视锥体6个平面进行测试，当钻石节点的包围球位于视锥体内时才进行渲染，以提高渲染速度。

2 算法实现流程

地形初始化之后，首先根据当前视点渲染地形。渲染过程中,当钻石节点可见性发生变化时，需要根据节点误差确定已变化的钻石节点优先级，并放入相应的优先队列。当判断地形细节层次没有达到要求时，将进行相应的分裂或合并操作，由此产生新的钻石节点并同样需要判断其可见性，然后根据可见性更新需要渲染的三角形列表，最后将所有需要渲染的三角形渲染到屏幕，渲染过程如图7所示。

图7 算法实现流程

3 实验及分析

本文算法采用VC6.0++和OpenGL来实现。实验仿真的DEM数据量大小为1025×1025。计算机配置为：Intel Celeron CPU 1.73GHz处理器，1GB内存,ATI RADEON XPRESS 200M Series集成显卡，Windows XP操作系统。

图8所示为只考虑视点，不考虑粗糙度的地形时，钻石节点在平坦和粗糙的地方均匀分布。图9、图10所示为使用了节点误差公式之后的地形，当粗糙度大或者距离视点近的地形采用更多的钻石节点渲染。在节点误差公式中可调因子C取值不同，而视点相同的情况下，地形显示的细节层次不同。由结果可以看出，渲染当前地形C取值为0.001时较为理想。

图8 使用节点误差公式前的地形

图9 节点误差公式C=0.001的地形

图10 节点误差公式C=0.003的地形

图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.