基于限制性四叉树LOD大规模地形预处理算法

计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (24): 107-109.

基于限制性四叉树LOD大规模地形预处理算法

王道臣¹，万旺根¹，唐经洲²，陈华杰¹

1.上海大学通信与信息工程学院，上海 200072
2.南台科技大学电子工程系，台湾 73502634

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-08-21 发布日期:2007-08-21
通讯作者: 王道臣

Preprocessing LOD algorithm for large scale terrain based on restricted quadtrees

WANG Dao-chen¹，WAN Wang-gen¹，TANG Jing-zhou²，CHEN Hua-jie¹

1.School of Communication and Information Engineering，Shanghai University，Shanghai 200072，China
2.Department of Electrical Engineering，Southern Taiwan University of Technology，Taiwan 73502643，China

Received:1900-01-01 Revised:1900-01-01 Online:2007-08-21 Published:2007-08-21
Contact: WANG Dao-chen

摘要/Abstract

摘要： LOD（Level Of Detail，层次细节）技术是解决大规模地形实时渲染的关键技术之一，通过这种技术可以较好地简化场景的复杂度，减少图形显示的失真度，满足一定的实时性要求。传统的算法将四叉树和LOD技术相结合将大规模数字高程模型数据（DEM）进行分块，并对块内数据按照分辨率的大小分层存储。通过对四叉树的研究，在限制性四叉树的基础上引入预处理算法，提高了地形读取速度，增强了实时显示效果。该算法是基于限制性四叉树的一种高效的规则网格划分方法，内存开销少，降低了CPU的负担。实验结果表明该算法提高了地形导入的效率，能实现大规模地形的实时漫游。

关键词: 四叉树, 限制性四叉树, 预处理, 数字高程模型数据

Abstract: LOD（Level Of Detail） which can reduce the complexity of scene preferably is the a key technology to solve the rendering problem of large scale terrain，which，LOD can alleviate the distortion of graphics and meet the request of real-time.Traditional algorithm，which combining quadtrees with Level Of Detail technology，partitions the DEM（Digital Elevation Model） of the terrain and stores the data of the block hierarchically by the resolution.In this paper，a preprocessing algorithm is introduced，which based on the restricted quadtrees.This method can increase the speed of loading terrain，and improve the effect of the real-time displaying. algorithm based on restricted quadtrees is an effective regular mesh refinement，which spends less memory and reduces the burden of CPU.Experimental results show that the algorithm improves the efficiency of terrain loading as well as supports real-time visualization of large-scale terrain rendering of online games well.

Key words: quadtrees, restricted quadtrees, preprocessor, Digital Elevation Model（DEM）

王道臣¹，万旺根¹，唐经洲²，陈华杰¹. 基于限制性四叉树LOD大规模地形预处理算法[J]. 计算机工程与应用, 2007, 43(24): 107-109.

WANG Dao-chen¹，WAN Wang-gen¹，TANG Jing-zhou²，CHEN Hua-jie¹. Preprocessing LOD algorithm for large scale terrain based on restricted quadtrees[J]. Computer Engineering and Applications, 2007, 43(24): 107-109.

[1]	孙爽，陈燕，朴在吉，张金松. 轨迹数据的时空模式挖掘与管理决策研究综述[J]. 计算机工程与应用, 2021, 57(16): 16-26.
[2]	成立明，陈建新，陈瑞，陈志敏. 融合自监督单目图像深度估计的视觉里程计[J]. 计算机工程与应用, 2021, 57(15): 230-236.
[3]	彭小红，梁子祥，张军，陈荣发. 深度学习驱动的水下图像预处理研究进展综述[J]. 计算机工程与应用, 2021, 57(13): 43-54.
[4]	李道全，王雪，于波，黄泰铭. 基于一维卷积神经网络的网络流量分类方法[J]. 计算机工程与应用, 2020, 56(3): 94-99.
[5]	余同瑞，金冉，韩晓臻，李家辉，郁婷. 自然语言处理预训练模型的研究综述[J]. 计算机工程与应用, 2020, 56(23): 12-22.
[6]	伍锡如，黄榆媛，王耀南. 改进ORB特征的机器人RGB-D SLAM算法[J]. 计算机工程与应用, 2020, 56(14): 35-44.
[7]	刘俊涛，王素娟，林晓明，刘祚时，谭俭辉，宋丹. 结合FCM聚类和边缘感知模型的眼底渗出物检测[J]. 计算机工程与应用, 2020, 56(11): 192-199.
[8]	晁静静，沈文忠，宋天舒. 基于HOG和SVM的双眼虹膜图像的人眼定位算法[J]. 计算机工程与应用, 2019, 55(9): 184-189.
[9]	吕伟，宋文爱，富丽贞，许文. 大规模图数据边受限制的最短距离查询算法[J]. 计算机工程与应用, 2019, 55(7): 71-81.
[10]	马菁1，2，李力3. RDD上扩展索引层优化的分布式K-means算法[J]. 计算机工程与应用, 2019, 55(1): 161-167.
[11]	姜道银1，2，葛洪伟1，2，袁罗1. 一种动态划分的混合连续域蚁群优化算法[J]. 计算机工程与应用, 2018, 54(7): 144-151.
[12]	陈长华1，刘煜2，崔强3. 结合饱和度运算和暗通道理论的遥感图像去雾算法[J]. 计算机工程与应用, 2018, 54(5): 174-179.
[13]	覃宏超，李炎炎，龙伟，赵瑞朋，王倩. 改进的暗原色先验理论视频去雾算法研究[J]. 计算机工程与应用, 2018, 54(16): 176-181.
[14]	刘万军，赵庆国. 基于颜色饱和度的快速图像去雾研究[J]. 计算机工程与应用, 2017, 53(8): 209-215.
[15]	杨泽雪. 空间数据库中的一种混合索引结构的研究[J]. 计算机工程与应用, 2017, 53(20): 20-23.