基于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所示。……