ROAM实时地形染算法研究
杨立群
(南京证券股份有限公司江苏南京210008)
算法分析
摘要：同前，计算机图形学技术长足发展，国内外对地形演染技术已经有大量的研究,产生了大量地形生成和演染算法，目前所主流的有ROAM,四叉树等面向CPU算法，也有MipMap等面向GPU算法。各种算法各有优缺点。本文通过对相关算法技术文献的学习，着重介绍ROAM地形淀染算法。
关键词：地形淀染ROAM地形算法分割中图分类号：TP391.41
1ROAM地形潼染算法
1.1ROAM算法思想
文献标识码:A
在ROAM算法中，算法思想可简单描述为：地形块被一分为二形成2个等边直角三角形。然后对每一个等边直角三角形的顶点到它对面边的中点进行分割，再形成2个新的等边直角三角形。这种分割是递归进行的，直到达到希望的细节等级，如图1：
对于每一个三角形，如果达到最高精度，则退出，如果目标地形不在视好中，则退出。ROAM算法使用二元三角树来保存三角垒标。用基于树的结构来控制随着深度而成指数增长的内存这些分割而成的三角块逻辑上看就像一组相连的邻居一样。使用这种思想进行分割存储，每个三角块就是各自树的根节点，每个三角形节点有5个指针，分别指向左孩子，右孩子，左邻居，右邻居和下邻居。
1.2ROAM算法的实现
在算法实现的过程中，网格的基本左三角和基本右三角分别作为树的根节点，叶子节点存储最终需要谊染的三角形.ROAM算法实现步骤如下：
(1)设置二元三角树基本左三角节点和基本右三角节点的左右和下邻居。(2)对现有的二元三角树按照计算所得的细节阀值进行分割，如果节点三角形大于阀值，则对其进行再分割，直到小于阅值为止。(3)重新遍历整棵树，根据二元三角树中叶子节点所保持的数据，把所需要的图像道染到屏幕上，
在ROAM算法中，每一个三角形的信息被存储在~个二元三角树的结构中，二元三角树被TniTreeNode所保存，其结构如下：
struct TriTreeNode
TriTreeNode +LeftChild: TriTreeNode +RightChild;
TriTreeNode +BaseNeighbor; TriTreeNode +LeftNeighbor; TriTreeNode +RightNeighbor;
该结构保存了ROAM算法实现中所需要的5个最基本数据。图 K
图1分割过程
收稿日期：20151015
文章编号：1007-9416(2015)11-0121-01
形谊染中，我们需要根据不同的精度需求往二元三角树中增加或者删除节点，TriTreeNode结构需要被多次建立和销毁。
在算法实现中，怎样确定每个三角形的分割的精度是关键的步骤，Variance方法是确定分割精度的优秀方法，我们将需要它来决定分割一个节点的时候将要分割到什么程度。Variance方法对二元三角树节点中正三角形斜边中点在高度图中的不同高度进行插值：
triVarianoe = abs(centerZ - (leftZ + rightZ) / 2)); 为了算法实现，需要一个和二元三角树一个协同工作的Vari-
ance树。Variance树是-一个二元树，填充了高度值，用一个连续的数组来表示。根据树中各个节点的插值，当值非常大时，我们把二元三角树中的对应的节点分割成小块直至满足需求。在完成地形谊染 LOD功能时，在计算完视点的距离以后，调整当前节点的Variance 值。距离的计算使用
distance = 1.0f + sqrtf( SQR((float)centerX - camera. Position.x/TERRAIN_MULTIPL)+
SQR((float)centerY-camera.position.z/ TERRAIN_MULTIPL) ):
这个简单的平方根计算。距离比较近的地形使用较多的三角形进行显示，距离较远的则使用的较少。对于地形三角形分割块，需要获得当前三角形的所有坐标设置，三角的Variance值。在计算时，选择每一个需要计算的点的X和Y坐标。首先得到三角形料边中点的高度值，该三角形的Variance值其实就是斜边中点的高度值减去两顶点的高度值的平均值。一个节点的最终的Variance值是它和它的
子节点中的最大值。最后存储这个新的Variance值。 2结语
本文介绍了ROAM算法这种比较成熟应用比较广的地形渡染算法，这种方法采用树形结构来存储节点数据，在流染前对地形数据做预处理，适合于基于已知静态高程数据的地形殖染。每一种地形渡染算法各有优劣，在实际应用过程中，我们需要根据实际情况，选择合适的地形滨染算法，适当时还可以基于算法的基本思想作相应的改进，充分考虑谊染的高效性，使谊染算法得到合适的应用。参考文献
[1]孙芳,载舞,周太平.地形演染算法的研究[J].测绘与空间地里信息,2009(1).
[2]唐先辉.基于ROAM的大规模地形潼染研究[J].代计算机,2009(7)
[3]黄超超,凌永顺，吕相银.ROAM动态地形潼染算法研究[J].计算机仿真，2005(1)
作者简介：杨立群(1988一),男，江苏张家港人,本科，助理工程师，研究方向：信息技术。
万方数据