Computer Science ›› 2018, Vol. 45 ›› Issue (4): 34-45.doi: 10.11896/j.issn.1002-137X.2018.04.005

Previous Articles     Next Articles

Survey of Terrain LOD Technology Based on Quadtree Segmentation

WANG Zhen-wu, LV Xiao-hua and HAN Xiao-hui   

  • Online:2018-04-15 Published:2018-05-11

Abstract: Level of detail(LOD)technology is the most widely adopted technology in the model simplification of large-scale terrain,which greatly accelerates the speed of roaming terrain.Among all the LOD methods,the most popular one is LOD algorithm based on quadtree segmentation.Many domestic and foreign scholars have done lots of research work on the LOD technology.In this paper,the quadtree based LOD algorithms were sorted and summarized systematically,several key algorithms were classified and analyzed,their advantages and disadvantages were analyzed in details,and their current research status were introduced comprehensively.

Key words: Fast roaming,LOD technology,Quadtree,Terrain

[1] LI X Y.A hybrid algorithm for terrain simplification[D].Vancouver:The University of British Columbia,2003:25-38.
[2] LINDSTROM P,KOLLER D,RIBARSKY W,et al.Real-Time,Continuous Level of Detail Rendering of Height Fields[C]∥Proceedings of the ACM SIGGRAPH Conference on Computer Graphics and Interactive Techniques.ACM,1996:109-117.
[3] DUCHAINEAUY M,WOLINSKY M.ROAMing Terrain:Real-time Optimally Adapting Meshes[C]∥Proceedings IEEE Visua-lization.Phoenix,AZ,USA,1997:81-88.
[4] MA Z T,PAN M,HU J X,et al.A Fast Walkthrough Method for Massive Terrain Based on Data Block Partition[J].Journal of Peking University(Natural Science Edition),2004,40(4):619-625.(in Chinese) 马照亭,潘懋,胡金星,等.一种基于数据分块的海量地形快速漫游方法[J].北京大学学报(自然科学版),2004,0(4):619-625.
[5] DE BOER W H.Fast Terrain Rendering Using GeometricalMipmapping[C]∥World Wide Web Conference Series.2000.
[6] VON HERZEN B,BARR A H.Accurate Triangulations of Deformed,Intersecting Surface[C]∥Conference on Computer Graphics and Interactive Techniques.ACM,1987:103-110.
[7] LI Q,DAI S L,ZHAO Y J,et al.A Block LOD Real-time Rendering Algorithm for Large Scale Terrain[J].Journal of Computer-Aided Design & Computer Graphics,2013,25(5):708-713.(in Chinese) 李钦,戴树岭,赵永嘉,等.分块LOD大规模地形实时渲染算法[J].计算机辅助设计与图形学学报,2013,5(5):708-713.
[8] ZHANG J F,YAO Z H.LOD Algorithm of Terrain Based on Conservative Screen Error and Isolated Division of Quad-tree[J].Journal of Southwest Jiaotong University,2013,48(4):666-671,677.(in Chinese) 张俊峰,姚志宏.基于四叉树孤立分割和屏幕误差的地形LOD算法[J].西南交通大学学报,2013,8(4):666-671,7.
[9] RUI X P.A LOD Algorithm Based on Unfullquadtree [J].Journal of Image and Graphics,2005,10(9):3659-3662.(in Chinese) 芮小平.一种基于不完全四叉树的LOD生成算法[J].中国图象图形学报,2005,0(9):3659-3662.
[10] CHEN H M,ZHAN S Y,LIU T.Real-time Simulation of Global Terrain Facing CE-1 Missions[J].Journal of System Simulation,2009,21(19):6135-6139.(in Chinese) 陈宏敏,战守义,刘涛.“嫦娥一号”任务全球地形实时仿真技术研究[J].系统仿真学报,2009,1(19):6135-6139.
[11] WANG J Y,HE Y Z,XIE J B,et al.Rapid Protracting Arithmetic about Large Scale DEM Data Based on Embeded Envirment[J].Acta Aeronauticaet Astronautica Sinica,2009,30(1):132-135.(in Chinese) 王金岩,何亦征,谢剑斌,等.一种基于嵌入式环境的海量DEM数据快速绘制算法[J].航空学报,2009,0(1):132-135.
[12] ZHAI R.GPU-based real-time terrain rendering Design and implementation[J].Neurocomputing,2016,171(1):1-8.
[13] ZHAO Y X.A modified LOD terrain model based on quadtree algorithm[C]∥Proceedings of the 2009 International Joint Conference on Computational Sciences and Optimization(CSO 2009).2009:259-263.
[14] TAN B,XU Q,ZHOU Y.The Research of Large Scale Terrain Visualization[J].Journal of Image and Graphics,2003,8(5):578-584.(in Chinese) 谭兵,徐青,周杨.大区域地形可视化技术的研究[J].中国图象图形学报,2003,8(5):578-584.
[15] LINDSTROM,PETER.Real-Time Generation of ContinuousLevels of Detail for Height Fields[C]∥Proceedings of the ACM SIGGRAPH Conference on Computer Graphics.1996:109-117.
[16] SONG L B,GONG H J,WANG X H.Global Terrain Real-Time Rendering Based on Improved Constraint Quad-Tree and Level of Detail Algorithm[J].Computer and Digital Engineering,2013,1(10):1668-1671.(in Chinese) 宋力兵,龚华军,王新华.基于改进的约束四叉树LOD全球地形实时绘制[J].计算机与数字工程,2013,1(10):1668-1671.
[17] LAN L,XU L.Elimination of Boundary Cracks in 3D Environment Art Design[J].Bulletin of Science and Technology,2015,1(11):203-206.(in Chinese) 兰玲,徐莉.3D环境艺术设计地形绘制中的边界裂缝消除[J].科技通报,2015,1(11):203-206.
[18] ZOU C M,LI Y,LU Y,et al.Dynamic LOD virtual terrain optimization based on quadtree[J].Journal of Wuhan University of Technology,2009,1(18):182-185.(in Chinese) 邹承明,李引,陆苑,等.基于四叉树的动态LOD虚拟地形优化[J].武汉理工大学学报,2009,1(18):182-185.
[19] LEI J H,ZENG F X,WU M X.The study of the LOD algorithm based on quad-tree structure[J].Manufacturing Automation,2010,2(8):211-214,8.(in Chinese) 雷军环,曾凡喜,吴名星.基于四叉树的视点相关LOD地形仿真算法研究[J].制造业自动化,2010,2(8):211-214,8.
[20] LI C H,WANG C B.Large-Scale LOD Terrain Rendering Based on Hierarchical Classification[J].Journal of Donghua University(Natural Science Edition),2010,6(4):351-355.(in Chinese) 李晨辉,王长波.基于层次划分的大规模LOD地形绘制[J].东华大学学报(自然科学版),2010,6(4):351-355.
[21] LIN Q P,ZHOU D Y,ZHANG K.Rapid Generation of 3D Terrain Scene in Battlefield Environment Simulation[J].Electronics Optics & Control,2009,6(12):38-42.(in Chinese) 林清漂,周德云,张堃.战场环境三维地形快速生成算法研究[J].电光与控制,2009,6(12):38-42.
[22] WU J,YANG Y,GONG S,et al.A New Quadtree-based Terrain LOD Algorithm [J].Journal of Software,2010,5(7):769-776.
[23] DENG Z H,ZHANG T T,LIU R H,et al.A Fast and Effective Method for Large-Scale Terrain Rendering[J].Journal of Northwestern Polytechnical University,2010,28(6):936-940.(in Chinese) 邓正宏,张婷婷,刘瑞恒,等.大规模地形渲染技术的研究与实现[J].西北工业大学学报,2010,8(6):936-940.
[24] HU A H,HE Z Y,MA X P.Rendering Technique for LargeScale Terrain Based on LOD[J].Acta Geodeaticaet Cartographica Sinica,2009,38(12):28-31.(in Chinese) 胡爱华,何宗宜,马晓萍.基于LOD的大规模地形实时绘制方法[J].测绘通报,2009,8(12):28-31.
[25] ZHU J,GONG J H,QI H,et al.A Simple and Efficient Algorithm for Real-Time Rendering of Large Scale Terrain[J].Geo-graphy and Geo-information Science,2005,21(2):24-27.(in Chinese) 朱军,龚建华,齐华,等.大规模地形实时绘制算法[J].地理与地理信息科学,2005,1(2):24-27.
[26] LUO J X,TANG J.LOD Algorithm Based on Improved Quad-tree-split and Node Storage[J].Computer Engineering,2009,35(20):202-204.(in Chinese) 罗景馨,唐琎.基于改进四叉树分割和结点存储的LOD算法[J].计算机工程,2009,5(20):202-204.
[27] ZHAO Y X,MA Y.A modified LOD terrain model based on quadtree algorithm[C]∥Proceedings of the 2009 International Joint Conference on Computational Sciences and Optimization(CSO 2009).2009:259-263.
[28] LINDSTROM P,PASCUCCI V.Visualization of Large Terrains Made Easy[C]∥Conference on Visualization.IEEE Computer Society,2001:24-26.
[29] JIN H L,GAO J X.An Algorithm for Real-Time Visualization of Large-Scale Terrain[J].Journal of Zhengzhou Institute of Surveying and Mapping,2006,23(1):65-68.(in Chinese) 靳海亮,高井祥.大规模地形实时可视化算法[J].测绘科学技术学报,2006,3(1):65-68.
[30] YI C L,ZHAN Q M,XU W Q,et al.Simplification Technology for Real-time Rendering of Large-scale 3D Terrain[J].Geoma-tics and Information Science of Wuhan University,2012,37(5):555-559.(in Chinese) 尹长林,詹庆明,许文强,等.大规模三维地形实时绘制的简化技术研究[J].武汉大学学报(信息科学版),2012,7(5):555-559.
[31] WEI Y M,GU T Y,YANG B,et al.Rapid Continuous Rende-ring Technology of Terrain Based on Wavelet[J].Computer Engineering,2007,33(19):218-220.(in Chinese) 魏迎梅,谷天阳,杨冰,等.基于小波的地形连续快速绘制技术[J].计算机工程,2007,3(19):218-220.
[32] WANG P,ZHAI Z J,JIANG H M.Research on Real-Time Rendering for Massive Multi-Resolution Terrain[J].Measurement & Control Technology,2008,27(2):32-35.(in Chinese) 王培,翟正军,姜红梅.大规模多分辨率地形实时绘制算法研究[J].测控技术,2008,7(2):32-35.
[33] YIN G S,WANG H L,ZHANG J,et al.A Fast Real-Time Rendering Method of 3D Terrain[C]∥The IEEE International Conference on Computer Science and Software Engineering.2009:1-4.
[34] NIE J L,LIU S,GUO D L,et al.GPU-Accelerated Fast Rende-ring Method for Multi-Resolution Geometry Image[J].Journal of Computer-Aided Design & Computer Graphics,2013,25(1):101-109.(in Chinese) 聂俊岚,刘硕,郭栋梁,等.GPU加速的多分辨率几何图像快速绘制方法[J].计算机辅助设计与图形学学报,2013,5(1):101-109.
[35] LI S,LIU X H,WANG W C,et al.Combination of Hierarchical Visibility with Level of Detail Terrain Model[J].Chinese Journal of Computers,2002,25(9):945-952.(in Chinese) 李胜,刘学慧,王文成,等.层次可见性与层次细节地表模型相结合的快速绘制[J].计算机学报,2002,5(9):945-952.
[36] ZHAO Y B,SHI J Y,et al.A Fast Algorithm for Large Scale Terrain Walkthrough[J].Journal of Computer-aided Design & Computer Graphics,2002,14(7):624-628.(in Chinese) 赵友兵,石教英,等.一种大规模地形的快速漫游算法[J].计算机辅助设计与图形学学报,2002,4(7):624-628.
[37] WU J,XU X G,WANG J G,et al.Real-time Walkthrough ofLarge Scale Ocean[J].Journal of System Simulation,2006,18(9):2505-2507.(in Chinese) 吴晶,徐晓刚,王建国,等.大规模海面的快速漫游[J].系统仿真学报,2006,8(9):2505-2507.
[38] WANG J,TANG X A,JING N.A Real-Time Walkthrough Algorithm of Large-Scale and Complex Scene[J].Computer Engineering and Applications,2003,39(16):88-90.(in Chinese) 王钧,汤晓安,景宁.一种大范围复杂场景的快速绘制算法[J].计算机工程与应用,2003,9(16):88-90.
[39] CHEN G,XIONG X H.A Study of Dynamic LOD Algorithm for Huge Quantities of Topographic Roaming[J].Bulletin of Surveying and Mapping,2007,36(4):46-48.(in Chinese) 陈刚,熊兴华.海量地形漫游中动态LOD算法研究[J].测绘通报,2007,6(4):46-48.
[40] GAO Y,DENG B S,CHEN P,et al.Fast Rendering Algorithm for Large-scale and Complex Scene Based on Continuous HLOD[J].Journal of Chinese Computer Systems,2007,28(7):1267-1271.(in Chinese) 高宇,邓宝松,陈鹏,等.基于连续HLOD的大规模场景快速绘制算法[J].小型微型计算机系统,2007,8(7):1267-1271.
[41] ZHI M,ZHENG Y T.HLODs for fast rendering of large-scale environments[J].Journal of Computer Applications,2007,27(9):2126-2128.(in Chinese) 智明,郑姨婷.HLODs模型在场景快速绘制中的应用[J].计算机应用,2007,27(9):2126-2128.
[42] FENG C S,WANG L L,YANG Y D.Fast Rendering Method Based on View Frustum Culling and Image Caching[J].Journal of System Simulation,2006,18(z1):94-98.(in Chinese) 封春升,王莉莉,杨跃东.基于视域剔除和图像缓存技术的复杂场景快速绘制方法[J].系统仿真学报,2006,8(z1):94-98.
[43] HOU S Y,ZHAO X S,GUAN Y Q.Seamless expression ofblock LOD model based on multi-resolution half-edge [J].Geography and Geo-Information Science,2015,1(4):18-21.(in Chinese) 侯绍洋,赵学胜,官亚勤.基于多分辨率半边的分块LOD模型无缝表达[J].地理与地理信息科学,2015,1(4):18-21.
[44] YI J,ZHAO L.Research on Terrain Visualization Based on LOD Dynamic[C]∥Seventh International Conference on Measuring Technology and Mechatronics Automation.2015:901-904.
[45] KALEM S,KOURGLI A.Large-scale Terrain Level of Detail Estimation based on WaveletTransform[C]∥Proceedings of the 10th International Conference on Computer Graphics Theory and Applications(GRAPP-2015).2015:258-264.
[46] ZHANG Z F,ZHANG N.A LOD algorithm based on out-of-core for large scale terrain rendering[C]∥2013 International Conference on Mechatronic Sciences,Electric Engineering and Computer(MEC).2013:2168-2171.
[47] SONG X S,QUAN J C,ZHAO X Y.Real-time detail enhancement terrain algorithm based on Chunked LOD [J].Computer Engineering and Design,2014,35(2):578-582.(in Chinese) 宋省身,全吉成,赵秀影.基于Chunked LOD的实时细节增强地形算法[J].计算机工程与设计,2014,5(2):578-582.
[48] LI Y,SUN S,XU H.A LOD algorithm for terrain-load in the scene of high-speed railway virtual reality based on quad-tree[C]∥Proceedings 5th International Conference on ComputationalIntelligence and Communication Networks(CICN 2013).2013:500-502.
[49] WANG Q,GAO B L,GAO R J,et al.LOD algorithm based on quadratic tree surrounded by ball and screen error [J].Microelectronics and Computer,2016,33(5):127-132.(in Chinese) 王倩,高保禄,高锐军,等.基于四叉树包围球和屏幕误差的LOD算法[J].微电子学与计算机,2016,3(5):127-132.
[50] ZENG W,HAN Z X,ZHU X F.Research of Application of LOD Algorithm to 3D Terrain Simulation[J].Journal of System Si-mulation,2009,21(1):292-294.(in Chinese) 曾维,韩占校,朱学芳.LOD算法在3D地表模拟中的应用研究[J].系统仿真学报,2009,1(1):292-294.
[51] HOPPE H.Smooth View-dependent level-of-detail control andits application to terrain rendering[C]∥Proceedings of the IEEE Visualization Conference.1998:35-42.
[52] REN H P,JIN B.Real-time Rendering of LOD Terrain Based on Quadtree[J].Journal of Huazhong University of Science and Technology(Natural Science Edition),2011,9(2):6-10.(in Chinese) 任宏萍,靳彪.基于4叉树的LOD地形实时渲染技术[J].华中科技大学学报(自然科学版),2011,9(2):6-10.
[53] THATCHER U.Chunked LOD:Rendering massive terrainsusing chunked level of detail control[EB/OL].http://
[54] YU W L,ZHANG L M.Large-scale LOD Adaptive TerrainRendering [C]∥2nd International Conference on Advanced Design and Manufacturing Engineering.2012:2450-2453.
[55] ULRICH T.Chunked LOD:Rendering massive terrains using chunked level of detail control[EB/OL].(2003-12-08).
[56] WAN M,LIANG X,ZHANG F M.Improved Crack Removing Algorithm for Quad-Tree Terrain Rendering[J].Journal of System Simulation,2015,27(7):1520-1525.(in Chinese) 万明,梁霞,张凤鸣.一种四叉树地形渲染裂缝的改进消除算法[J].系统仿真学报,2015,7(7):1520-1525.
[57] CHEN J,WU S,XIE B X.Visual modeling of complex 3D model for GPU rendering [J].Journal of Wuhan University(Information Science Edition),2014,39(1):106-111.(in Chinese) 陈静,吴思,谢秉雄.面向GPU绘制的复杂三维模型可视化方法[J].武汉大学学报(信息科学版),2014,9(1):106-111.
[58] MA C Y,CHEN G,CHEN Y,et al.An Algorithm of Avoiding Crack for Rendering Terrain Based on Pyramid Model[J].Control & Automation,2009,5(15):157-159.(in Chinese) 马纯永,陈戈,陈勇,等.基于金字塔模型的地形格网裂缝消除算法[J].微计算机信息,2009,5(15):157-159.
[59] WANG Z,HU M,LI X.Quick simplification for LOD terrainwith dynamic multi-resolution based on quad tree[J].Journal of Computer Applications,2007,27(7):1641-1643.(in Chinese) 王臻,胡敏,李响.基于四叉树的动态多分辨率LOD地形快速简化[J].计算机应用,2007,7(7):1641-1643.
[60] WANG D C,WAN W G,TANG J Z,et al.Preprocessing LOD algorithm for large scale terrain based on restricted quadtrees[J].Computer Engineering and Applications,2007,43(24):107-109.(in Chinese) 王道臣,万旺根,唐经洲,等.基于限制性四叉树LOD大规模地形预处理算法[J].计算机工程与应用,2007,3(24):107-109.
[61] CHEN G.Research on Hierarchical Description and Real-time Rendering of Virtual Terrain Environment[D].Zhengzhou:PLA Information Engineering University,2000.(in Chinese) 陈刚.虚拟地形环境的层次描述与实时渲染技术的研究[D].郑州:解放军信息工程大学,2000.
[62] MC ROBERTS D A K,HARDY A.Level of Detail for Terrain Geometry Images[C]∥Conference on Computer Graphics,Virtual Reality,Visualisation and Interaction in Africa.2007:25-30.
[63] ZHANG J F,SUN D P,XU D H.High-scale Terrain Adaptive LOD Algorithm Supported by 3D_DP and Quad_TIN [J].Geography and Geo-Information Science,2014,30(3):29-32.(in Chinese) 张俊峰,孙大鹏,许德合.3D_DP和Quad_TIN支持下的大规模地形自适应LOD算法[J].地理与地理信息科学,2014,0(3):29-32.
[64] YU Z,LIANG X H,MA S,et al.A Real-Time Rendering Methodfor Large Terrain Including Details in Different Resolutions[J].Journal of Computer Research and Development,2010,47(6):988-995.(in Chinese) 于卓,梁晓辉,马上,等.一支持大规模多种精度地形的实时绘制算法[J].计算机研究与发展,2010,7(6):988-995.
[65] LENG Z G,TANG X A,HAO J X,et al.Study on Dynamic Rapid Rendering Technique of Large Scale Terrain[J].Journal of System Simulation,2006,18(10):2832-2835.(in Chinese) 冷志光,汤晓安,郝建新,等.大规模地形动态快速绘制技术研究[J].系统仿真学报,2006,8(10):2832-2835.
[66] TAN B.Research on terrain three-dimensional reconstructionbased on remote sensing image[D].Zhengzhou:PLA Information Engineering University,2001.(in Chinese) 谭兵.基于遥感影象的地形三维重建技术的研究[D].郑州:解放军信息工程大学,2001.
[67] ZHANG J B,LIU X G.The Application of Linear QuadTrees in Rendering Terrain Surface[J].Computer Engineering and Applications,2002,38(8):46-47.(in Chinese) 张剑波,刘修国.线性四叉树在基于LOD的地表模型绘制中的应用[J].计算机工程与应用,2002,8(8):46-47.
[68] YIN Y,CHEN G J,WU W.An Algorithm of Avoiding Crack for Rendering Parting Terrain[J].Journal of Computer-aided Design & Computer Graphics,2006,8(10):1557-1562.(in Chinese) 殷媛,陈国军,吴威.地形分块绘制中的边界裂缝处理算法[J].计算机辅助设计与图形学学报,2006,8(10):1557-1562.
[69] HAN M,TANG S T,LI Y.Real-time Visualization Algorithm of Large-scale Terrain[J].Computer Engineering,2008,34(13):270-272.(in Chinese) 韩敏,汤松涛,李洋.大规模地形实时可视化算法[J].计算机工程,2008,4(13):270-272.
[70] TANG X A,CHEN M,SUN M Y.An Approach of Simplification and High-speedRendering for Terrain Model[J].Journal of Wuhan University(Information Science Edition),2001,26(4):310-314.(in Chinese) 汤晓安,陈敏,孙茂印.地景模型的简化与快速绘制方法研究[J].武汉大学学报(信息科学版),2001,6(4):310-314.
[71] WANG D,ZHU Q S.Adaptive LOD terrain rendering withGPU tessellation[J].Journal of Computational Information Systems,2015,11(20):7489-7496.
[72] DONG L M,ZHANG B,ZHAO X S.A Seamless Segmentation Algorithm Based on GPU Tessellation [J].Journal of Wuhan University(Information Science Edition),2016,1(11):1-6.(in Chinese) 董路明,张斌,赵学胜.一种基于GPU Tessellation的地形无缝绘制算法[J].武汉大学学报(信息科学版),2016,1(11):1-6.
[73] NIE J L,ZHANG J W,GUO D L.Application of Smooth Transition to GPU Fabricated Terrain Rendering [J].Small Microcomputer System,2014,35(1):121-125.(in Chinese) 聂俊岚,张精卫,郭栋梁.细节平滑过渡的GPU构网地形渲染[J].小型微型计算机系统,2014,5(1):121-125.
[74] ZHAO J Y,TANG M.Connectivity-based segmentation forGPU-accelerated mesh decompression[J].Journal of Computer Science and Technology,2012,27(6):1110-1118.
[75] CRAIG L,PATRICK M.A GPU-based level of detail system for the real-time simulation and rendering of large-scale granular terrain[C]∥22nd International Conference in Central Europe on Computer Graphics,Visualization and Computer Vision.2015:169-178.
[76] SUREZ J P,TRUJILLO A.An efficient terrain Level of Detail implementation for mobile devicesand performance study[J].Computers,Environment and Urban Systems,2015,52:21-33.
[77] LIU X,LIU Z,MEI X D.Based on real-time LOD simplified rendering rendering method[J].Journal of Hunan University of Science and Technology(Natural Science Edition),2015,0(4):92-96.(in Chinese) 刘晓,刘镇,梅向东.基于实时LOD简化绘制的渲染优化方法[J].湖南科技大学学报(自然科学版),2015,0(4):92-96.

No related articles found!
Full text



No Suggested Reading articles found!