一种新的ROAM算法及其在地形建模中的应用

doi:10.12082/dqxxkx.2018.180050

地球信息科学学报 ›› 2018, Vol. 20 ›› Issue (9): 1209-1215.doi: 10.12082/dqxxkx.2018.180050

• 地球信息科学理论与方法 • 下一篇

一种新的ROAM算法及其在地形建模中的应用

李朝奎^1,²(), 王宁^1,², 吴柏燕^1,², 方军^1,², 杨文涛^1,², 褚楠^1,²

1. 湖南科技大学地理空间信息技术国家地方联合工程实验室,湘潭 411201
2. 湖南科技大学地理空间信息湖南省工程实验室,湘潭 411201

收稿日期:2018-01-15 修回日期:2018-06-22 出版日期:2018-09-25 发布日期:2018-09-25
作者简介:
作者简介：李朝奎（1967-）,男,博士,湖南汉寿人,教授,博士生导师,研究方向为三维地理建模及其应用。E-mail: chkl_hn@163.com
基金资助:
国家自然科学基金项目（41571374）;国家重点研发计划项目（2017YFB0503802）;湖南省教育厅重点项目（16A070）;湖南省自然科学基金湘潭联合基金（2017JJ4037）;特殊环境道路工程湖南省重点实验室开放基金项目（kfj150502）

A New ROAM Algorithm and Its Application in Terrain Modeling

LI Chaokui^1,^2,^*(), WANG Ning^1,², WU Baiyan^1,², FANG Jun^1,², YANG Wentao^1,², CHU Nan^1,²

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

Received:2018-01-15 Revised:2018-06-22 Online:2018-09-25 Published:2018-09-25
Contact: LI Chaokui
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.

摘要/Abstract

摘要：

地形建模是数字地形分析的重要基础工作。实时优化适应性网格算法（ROAM算法）是目前常用的地形建模方法。但ROAM算法应用于地形可视化实时渲染时要求原始数据为正方形,且渲染后常有裂缝产生,因而该法在地形建模实践中受到较大的限制。针对ROAM算法存在的上述不足,本文提出了基于内接正方形插值方法的改进ROAM算法。通过将多边形分割为一个内接正方形和多个边缘多边形,用多边形的一个顶点依次与其他顶点相连,使边缘多边形分割为多个三角形,并根据边缘三角形面积大小,确定是否对边缘多边形进行继续分割,由此解决数据源限定为正方形的问题,利用添加拆分点的方法消除地形渲染产生的裂缝。采用不规则地形的灰度图作为高程数据源进行地形模拟实验,结果表明：改进后的ROAM算法能够消除裂缝,且对数据源无约束性要求,降低了算法复杂度,提高了整体可视化性能,能够满足地形实时动态显示的要求。

关键词: 地形建模, ROAM算法, 内接正方形插值, 算法改进, 裂隙

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

李朝奎, 王宁, 吴柏燕, 方军, 杨文涛, 褚楠. 一种新的ROAM算法及其在地形建模中的应用[J]. 地球信息科学学报, 2018, 20(9): 1209-1215.DOI:10.12082/dqxxkx.2018.180050

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

图/表 14

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

表1

图13

参考文献 18

[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.
	[ 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. doi: 10.3969/j.issn.1001-9960.2014.15.008
	[ 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. ] doi: 10.3969/j.issn.1001-9960.2014.15.008
[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. ]

裂缝修补	三角形数量	建模时间/ms
强制分割法	19 712	4335.40
添加拆分点法	11 840	2309.66

一种新的ROAM算法及其在地形建模中的应用

A New ROAM Algorithm and Its Application in Terrain Modeling

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 14

参考文献 18

相关文章 3

Metrics

本文评价

推荐阅读 0

[1]	陶宇, 王春, 徐燕, 张光祖, 宋素素, 杨维. DEM建模视角下的城市道路分类与表达[J]. 地球信息科学学报, 2020, 22(8): 1589-1596.
[2]	徐晨晨, 廖小罕, 岳焕印, 鹿明, 陈西旺. 基于改进蚁群算法的无人机低空公共航路构建方法[J]. 地球信息科学学报, 2019, 21(4): 570-579.
[3]	李祥琛, 芮小平, 曲小康, 宋现锋, 王慧芳. 基于圆盘概化模型的岩溶裂隙渗流路径构建算法[J]. 地球信息科学学报, 2016, 18(2): 182-189.