EN中文

Journal of Geo-information Science >

2018 , Vol. 20 >Issue 9: 1209 - 1215

DOI: https://doi.org/10.12082/dqxxkx.2018.180050

A New ROAM Algorithm and Its Application in Terrain Modeling

  • LI Chaokui , 1, 2, * ,
  • WANG Ning 1, 2 ,
  • WU Baiyan 1, 2 ,
  • FANG Jun 1, 2 ,
  • YANG Wentao 1, 2 ,
  • CHU Nan 1, 2
Expand
  • 1. National-Local Joint Engineering Laboratory of Geo-Spatial Information Technology, Hunan University of Science and Technology, Xiangtan 411201, China
  • 2. Hunan Province Engineering Laboratory of Geospatial Information, Hunan University of Science and technology, Xiangtan 411201, China
*Corresponding author: LI Chaokui, E-mail:

Received date: 2018-01-15

  Request revised date: 2018-06-22

  Online published: 2018-09-25

Supported by

The National Natural Science Fund, No.41571374

National Key Research and Development Plan, No.2017YFB0503802

The Key Project of the Hunan Provincial Department of Education, No.16A070

Hunan and Xiangtan Joint Natural Science Fund, No.2017JJ4037

The Open Fund of the Key Laboratory of Hunan province for Special Environmental Road Engineering, No.kfj150502.

Copyright

《地球信息科学学报》编辑部 所有
Fold

Abstract

Terrain modeling is important in the digital terrain analysis. Real-time adaptive mesh algorithm (ROAM algorithm) is a commonly used terrain modeling method. However, applying ROAM algorithm to real-time rendering of terrain visualization requires the original data to be square and cracks often occur after rendering, so this method is greatly restricted in the practice of terrain modeling. Aiming at the above disadvantages of the ROAM algorithm, an improved ROAM algorithm based on the interpolation of inner square is proposed in this paper. The polygon is divided into an inner square and multiple edge polygons, then the vertexes of these polygons are connected sequentially to divide the polygons into multiple triangles, and according to the size of the edge triangles, whether to continue segmentation of the edge polygon is determined. Thus, the problem of limiting the data source to a square is solved, and the crack generated by the terrain rendering is eliminated by adding split points. Using the irregular terrain gray image as the elevation data for terrain simulation experiment, the results show that the improved levenshtein distance algorithm can eliminate the crack with no binding requirements for data source, reduce the algorithm complexity and improve the overall visual performance. It can meet the requirements of terrain real-time dynamic display.

Key words： terrain modeling; ROAM algorithm; interpolated interpolation; algorithm improvement; fracture

Cite this article

LI Chaokui , WANG Ning , WU Baiyan , FANG Jun , YANG Wentao , CHU Nan . A New ROAM Algorithm and Its Application in Terrain Modeling[J]. Journal of Geo-information Science, 2018 , 20(9) : 1209 -1215 . DOI: 10.12082/dqxxkx.2018.180050

1 引言

实时地形可视化在地理信息系统、电脑游戏和军事模拟等多个流行应用领域发挥重要的作用[1]。为了使计算机在处理复杂物体表面模型时保持实时的连续显示,通常采用LOD（Level of Detail）技术[2]。LOD技术采用多分辨率模型和近似多边形表面的方法使物体在离视点不同距离时生成不同精度的表面模型,用粗糙模型表示距离比较远的观察点,用精细模型表示距离比较近的观察点[3]。在众多的LOD算法中,ROAM（Real-time Optimally Adapting Meshes）算法在地形可视化领域受到广泛关注[4]。
ROAM算法是Duchaineauy等[5]提出的,该算法基于Grid网格,利用三角形对地形表面进行逼近,并存储每个三角形的邻接三角形信息,以便其后续的分裂与合并[6]。ROAM是最流行的实时地形渲染算法之一[7]。但现有的ROAM算法在实际应用中对数据源有一定的限制,并且渲染后地形会出现裂缝现象。常用的裂缝消除算法或因要求节点之间具有强制的依赖关系而导致地形表达失真,或因算法过于复杂不适于大规模动态地形模拟[8]。针对上述不足,本文提出了一种新的改进方法。该方法通过将不规则地形分为一个内接正方形与多个边缘多边形,并根据边缘多边形分割成三角形的面积大小,确定是否对边缘三角形进行继续分割,由此解决数据源限制问题;通过添加拆分点消去地形渲染中产生的空洞。采用不规则地形的灰度图作为高程数据源进行地形模拟实验,结果表明：改进后的ROAM算法能够消除裂缝,实现对数据源无约束性要求。改进后的ROAM算法提高了地形对象的整体可视化性能,满足了实时动态显示的要求。

2 ROAM算法及其改进

2.1 ROAM原理

ROAM算法是利用二叉树剖分方法对三角形进行划分,从而表达地表形态,如图1所示。当需要精细的模型时,进行细粒度分割,等级较高;当需要粗糙模型时,进行粗粒度分割,等级较低[9]。
Fig.1 ROAM mesh division principle

图1 ROAM网格剖分原理

2.2 ROAM算法存在的不足

ROAM算法通过对原始大区域进行分块,减少了直接进行LOD建模的数据量,一定程度上可提高算法的运行速度,但也存在一定的不足[10,11]。首先ROAM要求高程数据必须是正方形地形,其次由于划分相邻区块时分割层次不同会导致裂缝产生[12]。如图2所示,在AD边两侧出现了相邻地形块不同等级的情况。AD边右上侧由△AEC和△CED组成,AD边左下侧由一个大三角形△ABD组成,AD边为其公共边。在右上侧AD边被分成了AE和ED两条边,分别包含于△AEC和△CED中,渲染时将作为两段分别进行渲染;因AD边只存在于三角形ABD上而直接被渲染。如果HE≠1/2（HA+HD）,即点E没有落到AD边上,则AD边两侧△ABD和△ACE、△CED在AD边处无法重合,即产生裂缝△AED。
Fig. 2 Generation of cracks in adjacent areas

图2 邻区裂缝的产生

2.3 ROAM算法的改进

针对2.2节中所述ROAM算法存在的问题,提出对该算法的进一步改进。ROAM算法改进的基本思想是采用基于内接正方形插值方法实现数据源的通用化,利用添加拆分点方法消除渲染产生的裂缝。
2.3.1 数据源的通用化
ROAM算法要求源数据为规则的正方形,其每个边的高程数据点为2n+1（n∈N）个[13]。对此,本文采用内接正方形插值方法来消除ROAM算法对数据的约束性要求。如图3所示,对不同地形形状的多边形进行了分别的描述。对于标准的正方形地形块,运用ROAM算法（图3（a））。对于凸多边形地形（图3（b））,找出凸多边形内的内接正方形,对正方形内的地形进行插值取高程值,满足传统ROAM算法对地形的要求,进行地表模拟。对于去除内接正方形后的边界地形（△CDB,△DEF,FGHI,IJAB）,可根据精度要求,设置最大面积精度S',将每个边缘多边形顺时针分割为多个三角形（多边形IJAB与多边形FGHI进行分割）,判断每个三角形面积S是否小于最小精度要求S',若不满足,取三角形两点中点,将三角形分割为2个小三角形 （△DCB分割为△CDB'和△B'DB）,继续判断小三角形面积是否满足精度要求。对于凹多边形（图3（c））,从最下面一点向两侧进行扩展,当从两侧分别搜索到两条边之间内侧的夹角大于180°的2个顶点时,将其进行连接,从而将其分割为多个凸多边形,进而对凸多边形进行分割。采用此种方法进行分割多边形,对于正方形采用原ROAM算法进行处理,能够满足大面积地形符合真实地表,对于边缘部分的处理解决了对数据源的限制。算法流程见图4。
Fig. 3 Different terrain segmentation

图3 不同地形分割

Fig. 4 Flowchart of terrain segmentation algorithm

图4 地形分割算法流程

对于正方形内地形进行细化分割三角形时,对当前细节等级的三角面是否细分的判断公式如下：
TriVariance = E × MapSize × 2 D （1）
式中：Mapsize为地形块的大小;E代表误差度,每个节点E的myVariance计算表达为：
myVariance = centerZ-1/2（leftZ + RightZ） （2）
D为视点距观察点的距离,其表达式如下：
D=1.0f + sqrtf（ （centerX - gViewPosition[0]）2
+（centerY - gViewPosition[2]） ）2（3）
误差TriVariance随着视距和地形起伏度的不同而动态变化,当误差大于设定的容忍限度时进行细分。将视距和地形起伏度考虑在内,尽可能达到要求的最低精度,降低三角形数量,从而加速渲染。
2.3.2 地形裂缝的消除
地形裂缝主要分为地形内部裂缝和地形边缘裂缝二大类。地形内部裂缝是由于相邻结点层次的差异而产生。通常人们采用保证相邻结点的层次差不超过1的解决办法,在进行实时绘制时,算法首先判断相邻结点的层次差是否超过1,如果层次差超过1,常采用的方法：① 无论精度是否达到要求都停止分割,确保层次差为1[14,15,16]。② 强制进行分割,即使已经达到精度要求,仍继续分割,直至层次差为1[17,18]。方法①强制停止分割,分割结果很难满足精度要求,方法②虽能达到精度要求,却大大增加了渲染的三角形面片数,效率低且比较复杂。本文通过增加节点来填充地形裂缝,获得很好的效果。如图5所示,对多边形A-J采取基于内接正方形插值方法,若不进行裂缝修复和边缘部分处理,渲染后会出现图5（b）所示的空洞。对于地形内部出现△OMP和△BNI裂缝,取N'=1/2（HB+HI）,M'=1/2（HO+HP）,此时N'、M'分别落在边BI、OP上,这样就消除了裂缝△OMP和△BNI。对于边缘部分出现的空洞,因对其取内接正方形之前,将其分割为凸多边形,所以其边缘多边形均为钝多边形。从内接正方形任一顶点出发,连接该点与邻近边界顶点,将边缘多边形分割为多个三角形,从而获得较高的三角形面积精度。以三角形外边中心的顶点对三角形进行再次分割,如图5（c）中△BCD,进而减小边缘三角形剖分的粗糙度,在剖分过程中,内部正方形的边为边缘三角形中一边,实现了边缘多边形和内部正方形的无缝衔接,最终,多边形A-J划分为图5（c）所示的多边形,且进行了无缝渲染。
Fig. 5 Repair of terrain cracks

图5 地形裂缝修补图

2.3.3 结点关系的调整
利用ROAM算法进行实时动态的地形渲染时,需根据所需的精度实时动态的分割三角形,根据所存储的三角形数据结构,定义节点邻接关系。如图6,红色△BFE代表目标节点,图中标明了其余邻接节点与△BFE之间的关系。每次分解产生新的节点都需重新设置节点之间的关系。
Fig. 6 Relationship between triangles

图6 三角形间的关系

白色地块为灰色地块的左相邻节点,对灰色三角形进行剖分,有3种情况（图7）。
Fig. 7 Left-neighbor nodes in three different situations

图7 三种不同情况的左相邻节点

左相邻节点关系调整定义：
if （tri->LeftNeighbor != NULL）
{
if （tri->LeftNeighbor->BaseNeighbor == tri）
tri->LeftNeighbor->BaseNeighbor = tri->LeftChild;
else if （tri->LeftNeighbor->LeftNeighbor == tri）
tri->LeftNeighbor->LeftNeighbor = tri->LeftChild;
else if （tri->LeftNeighbor->RightNeighbor == tri）
tri->LeftNeighbor->RightNeighbor = tri->LeftChild;
}
白色地块为灰色地块的右相邻节点,对灰色三角形进行剖分,有3种情况（图8）。右相邻节点关系调整定义：
if （tri->RightNeighbor != NULL）
{
if （tri->RightNeighbor->BaseNeighbor == tri）
tri->RightNeighbor->BaseNeighbor =tri->Right-Child;
else if （tri->RightNeighbor->RightNeighbor == tri）
tri->RightNeighbor->RightNeighbor=tri->Right-Child;
else if （tri->RightNeighbor->LeftNeighbor == tri）
tri->RightNeighbor->LeftNeighbor = tri->Right-Child;
}
Fig.8 Three different cases of the right adjacent nodes

图8 3种不同情况的右相邻节点

3 实验验证

实验的硬件环境条件为4 GB内存,Inter Core i5-3210 M处理器,NVIDIA GeForce GT 620 M显卡,Windows 7操作系统。利用Visual C++ 6.0进行编写,使用OPENGL进行渲染。实验数据大小为1025像元×1025像元个采样点和1024像元×1024像元,原始数据是*.png格式,通过Photoshop将其转换为*.raw格式。实验数据为标准的正方形数据,边长的高程数据点为2n+1（n∈N）。图9为使用传统ROAM算法进行地形建模的实验结果。图中红色小圈标注了相邻地形块间由于分割三角形的等级不同而产生地形裂缝。这是因为对数据的严格要求大大限制了传统ROAM方法的应用效果,且渲染后出现裂缝。图10显示了经过裂缝消除之后的渲染效果,视觉效果比较理想。
Fig. 9 Standard square data terrain grid without crack elimination

图9 未经过裂缝消除的标准正方形数据地形网格

Fig.10 Standard square data terrain grid through crack elimination

图10 经过裂缝消除的标准正方形数据地形网格

利用4098像元×4098像元的数据进行地形建模,在相同的条件下进行地形模拟,图11显示了强制分割法消除裂缝的网格图和渲染图。图12显示了采用添加拆分点方法消除裂缝的网格图和渲染图。对2种方法建模效果进行对比,表1显示了对比结果。从表1可以看出：在保证视觉效果的前提下,新的裂缝消除方法比强制分割方法减少了三角形数量,建模速率得到很大提高。
Fig.11 Model of forced segmentation

图11 强制分割建模模型

Fig.12 Adding split point modeling model

图12 添加拆分点建模模型

Tab. 1 Algorithm efficiency comparison

表1 算法效率对比

裂缝修补 三角形数量 建模时间/ms
强制分割法 19 712 4335.40
添加拆分点法 11 840 2309.66
图13为改进后ROAM算法的实验结果,所采用的数据是将规则格网的1024像元×1024像元的数据在Photoshop中裁剪为不规则地形数据,采用内接正方形插值方法和添加拆分点的方法解决数据源的限制和渲染裂缝这二大问题。在图13中,从左图红色部分可以看出裂缝已经被消除及不规则边界得到很好的处理,从右图的渲染图效果来看,无裂缝的产生。
Fig.13 Results of improved ROAM algorithm

图13 改进的ROAM算法实验结果

4 结论

本文提出了采用内接正方形插值方法消除数据源的约束性要求;利用添加拆分点的方法消除渲染产生的裂缝。采用不规则地形的高程数据进行改进方法的实验验证。研究表明：① 改进的ROAM算法适用于非规则地形数据;② 渲染后无裂缝的产生,视觉效果较好;③ 大大提高了地形渲染效率,满足地形动态实时绘制的要求。改进后的ROAM方法也存在一定的局限性,这是因为该方法的分割原理决定了其适用于取内接正方形后的边缘多边形相对较小的情形,否则失真会较大;另外,本文倡导方法对于狭长的地形块适应性不理想。上述局限性将是后续研究努力的方向。

The authors have declared that no competing interests exist.

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
张淑军,周忠,郭威,等.基于运动估算的多分辨率地形分块调度方法[J].计算机辅助设计与图形学学报,2009,21(7):880-885.

[ Zhang S J, Zhou Z, Guo W, et al.Multiresolution terrain block scheduling based on motion estimation[J]. Computer Aided Design and Graphics, 2009,21(7):880-885. ]

[2]
李清泉. 三维空间数据的实时获取、建模与可视化[M].武汉:武汉大学出版社,2003.

[ Li Q Q.Real-time acquisition, modeling and visualization of 3D spatial data[M]. Wuhan: Wuhan University Press, 2003. ]

[3]
高勇,刘家骏,郭潇,等.面向大规模动态地形可视化的LOD组织与调度技术[J].地理与地理信息科学,2016,32(1):6-11.

[ Gao Y, Liu J J, Guo X, et al.LOD organization and scheduling technology for large-scale dynamic terrain visualization[J]. Geography and Geographic Information Science, 2016,32(1):6-11. ]

[4]
刘明钢,龙俊生.一种基于ROAM的全球地形实时可视化[J].江西测绘,2011(2):11-14.

[ Liu M G, Long J S.A type of ROAM global terrain real-time visualization based on[J]. Surveying and Mapping of Jiangxi, 2011(2):11-14. ]

[5]
Duchaineau M, Wolinsky M, Sigeti D E, et al.ROAMing terrain: Real-time Optimally Adapting Meshes[C]// Visualization '97. Proceedings, IEEE, 2002:81-88.

[6]
李鹤元,陈刚,柯希林.三维地形数据塔式结构模型与可视化方法研究[J].地理空间信息,2016,14(9):12-16.

[ Li H Y, Chen G, kollin. 3D terrain data pyramid model and visualization method[J]. Geospatial Information, 2016,14(9):12-16. ]

[7]
González C, Pérez M, Orduña J M.A Hybrid GPU Technique for Real-Time Terrain Visualization[C]// International Conference on Computational and Mathematical Methods in Science and Engineering, 2016.

[8]
张俊峰. 大规模地形实时动态多分辨率显示关键算法研究[D].武汉:武汉大学,2011.

[ Zhang J F.Key algorithms for real-time dynamic multiresolution display of large scale terrain[D]. Wuhan:Wuhan University, 2011. ]

[9]
侯能. 地形可视化中的加速技术研究[D].南宁:广西大学,2012.

[ Hou N.Acceleration technology in terrain visualization[D]. Nanning: Guangxi University, 2012. ]

[10]
王金. 基于LOD的大规模地形可视化技术的研究[D].武汉:武汉理工大学,2011.

[ Wang J.Research on large-scale terrain visualization technology based on LOD[D]. Wuhan:Wuhan University of Technology, 2011. ]

[11]
杨立群. ROAM实时地形渲染算法研究[J].数字技术与应用,2015(11):121.目前,计算机图形学技术长足发展,国内外对地形渲染技术已经有大量的研究,产生了大量地形生成和渲染算法,目前所主流的有ROAM,四叉树等面向CPU算法,也有Mip Map等面向GPU算法。各种算法各有优缺点。本文通过对相关算法技术文献的学习,着重介绍ROAM地形渲染算法。

[ Yang L Q.ROAM real-time terrain rendering algorithm research[J]. Digital Technology and Applications, 2015(11):121. ]

[12]
殷媛,陈国军,吴威.地形分块绘制中的边界裂缝处理算法[J].计算机辅助设计与图形学学报,2006,18(10):1557-1562.

[ Yin Y, Chen G J, Wu W.Algorithm for boundary crack processing in block rendering of terrain[J]. Chinese Journal of Computer Aided Design and Graphics, 2006,18(10):1557-1562. ]

[13]
张旺,张志春,周同林,等.大规模多分辨率地形建模方法研究[J].科技信息,2014(15):9-10.为实现大规模地形的实时真实感漫游,基于分块分层的多分辨率地形组织结构,结合Pajarrola提出的约束四叉树思想,设计多分辨率分块分层约束四叉树结构。并采用基于视距的缩减剖分方法来消除裂缝,实现漫游过程中地形网格的平滑无缝过度。

DOI

[ Zhang W, Zhang Z C, Zhou T L, et al.Large scale multiresolution terrain modeling method[J]. Science and Technology Information, 2014(15):9-10. ]

[14]
Zhang Z, Zhang N.A LOD algorithm based on out-of-core for large scale terrain rendering[C]// International Conference on Mechatronic Sciences, Electric Engineering and Computer, IEEE, 2013:2168-2171.

[15]
刘局科. 基于GRID/TIN混合结构的地形场景数据组织方法研究[D].南京:南京师范大学,2015.

[ Liu J K.Research on data organization method of terrain scene based on GRID/TIN hybrid structure[D]. Nanjing: Nanjing Normal University, 2015. ]

[16]
程雪原. 面向大数据集的地形网格模型简化研究[D].大连:大连理工大学,2015.

[ Cheng X Y.Simplification of terrain grid models for large datasets[D]. Dalian: Dalian University of Technology, 2015. ]

[17]
Pajarola R.FastMesh: Efficient View-Dependent Meshing[C]//Computer Graphics and Applications, 2001. Proceedings. Ninth Pacific Conference on, IEEE, 2001:22-30

[18]
张俊峰刘文玉,邓荣鑫,等.大规模地形实时显示中的裂隙消除算法研究[J].测绘科学,2013,38(4):80-82,100.

[ Zhang J F, Liu W Y, Deng R X, et al.Crack-eliminated algorithm research on real-time adaptive display of large-scale terrain[J]. Science of Surveying & Mapping, 2013,38(4):80-82,100. ]

Options
Outlines

/

〈 〉