三维地形数据结构与调度研究进展∗

袁松鹤靳海亮李留磊耿文轩

三维地形数据结构与调度研究进展∗

袁松鹤靳海亮李留磊耿文轩

（河南理工大学测绘与国土信息工程学院焦作454000）

地形三维可视化技术是将能够在二维平面中进行描述的以及无法在二维平面中显示的地理空间信息转换到三维环境中，并通过一定的规则将这些信息整合成为三维空间中的一个实体，人们可以通过三维地形可视化技术对事物内部深层次的关系和规律进行挖掘，提高研究成果的可靠性。论文将近几年国内外学者针对三维地形数据的存储和调度方面的研究进行了总结和归纳，对于今后研究该领域的技术具有一定的参考价值。

三维地形；三维可视化；Ogre3D；数据简化：GPU

Class NumberP283

1引言

由于地形高程数据获取方式越来越先进，地形数据的高程网格精度有了很大的提升，这将为构建高精度虚拟数字场景打下坚实的数据基础。目前，要求所实现的三维地形场景的规模逐渐地变大，从小区域到城市、国家乃至全球都在建立仿真系统，因此海量增长的地形数据，这必然导致相应的数据存储需求不能在现有计算机硬件条件上实现，为了使计算机的性能能够满足海量地形数据存储的要求，国内外学者针对地形数据的存储和调度进行了大量的研究。

2海量地形数据存储与调度

Lindstrom提出了隔层四叉树结构和交叉四叉树结构［1］，通过四叉树的数据组织方法对地形数据进行管理和绘制，并且利用∏型空间填充曲线法对数据进行重新排列，从而消除数据冗余，通过基于虚拟内存的管理方案，实现了内外存储空间之间的数据调度。Lindstrom的算法是从所有的数据角度出发，用相对稳健和高效的操作系统来完成页面动态调度操作。但是需要我们进一步研究的关键是，确定一种尽可能减少硬盘动态页面调度的原始数据存储方案和设计一种高效的快速确定硬盘中所需顶点位置的索引算法。

Falby是以观察者视点的移动作为出发点，来进行分辨率选取与层次结构数据调度［2］。因此提出了更为直接的地形动态页面调度系统。Pajarola以基于移动窗的方案来对地形块进行调度，通过观察视点的移动区域来对该区域的地形数据进行获取计算，从而实现了增量式的地形数据调度［3］。但是也存在一些不足：如果视点在水平或者垂直方向上快速漫游或反复移动时，将会有“抖动”现象出现。如果视点向斜对角方向移动时，所需要传输的数据块数将会增多，这样会给服务器增加负荷量。唐桂文等［4］首先从金字塔影响、分片分块的角度出发，组织三维地形数据，并在此基础上开发了一种空间数据中间件，并通过该中间件对数据库中的地形数据进行读写，实现了三维地形数据的存储和调度。其优点是地形渲染速度完全达到了实时性的要求，但三维地形数据在存储时间上比基于文件的管理方式要慢些。适用于基于Web应用的发展趋势。

温菊屏等［5］通过多通道图形输出地形漫游系统项目为基础，来研究地形数据的分块存储以及动态调整策略，提出的地形数据组织和调度方案，解决了海量数据同计算机有限的硬件水平之间的矛盾，从而使三维地形场景的初始化时间得到了极大缩短，并使大规模连续三维地形的显示更加平滑和连续。

蒋秉川等［6］基于体素的基本概念以及体素模型所实现的地形表达特点，结合Ogre3D实现了体素模型的三维地形可视化，为实现空间过程模拟建立统一的基于“体”的虚拟地理环境建立了重要的基础。其优点是能较好地表示空间粒子之间的相互作用关系，适用于表达地理空间过程的动力学机制，进而实现对多尺度地理现象与过程的模拟、分析与预测因此在3DGMS（三维地学模拟信息系统）中应用广泛。但关键问题是底层体素模型的设计，以及基于体素的地理空间表达。吴晨等［7］以传统多动态地形数据采用磁盘存储而导致的高频存取的现势性数据读取效率过低的角度出发，提出了MongoDB数据库支持下内外存储结合的多时态海量地形数据存储管理的优化方法，来满足用户可视化应用需求以及调度方面的要求，并进一步设计了MongoDB支持的时态数据自动分片以及索引的优化策略，进一步保证用户所需现势性数据在内存中快锁扑捉。李光辉等［8］从大地形海量数据量的角度考虑，提出了地形多分辨率四叉树模型，对该模型的定义和构成进行了简单的介绍，构建了模型的具体存储机制，设计了数据并行多线程调度机制，采用共享内存同步策略，进一步保证了数据处理的高效性和有序性。杨冰等［9］针对全球地形数据提出了一种正八面体球面四元三角的空间剖分方法，来解决两极区域拼接变形问题。实现了全球模型的无缝拼接。该方法的优点采用了一种新颖的经纬度编码方式，能够实现对地形数据的快速检索和调度，减少了CPU的计算量。但是仍需对海量地形数据压缩存储算法以及在实现一定要求的细节层次时精度不够的问题仍需进一步研究。

岳利群、夏青等［10］结合海量地形数据的特点和实际渲染需求，提出了海量地形数据组织管理的五个影响因素以及五个因素之间的关系，这五个影响因素分别为LOD级别、视觉精度、数据索引速度、三维地形分析精度和系统管理便携性。为了对地形基础地形块的属性变化对地形绘制产生的影响进行测试，它们将DEM和纹理均设置为三种不同的属性，从研究结果来看，五个因素的重要性不一样，研究的顺序也有先后，但是清楚表现出了数据组织管理的关键之处，五个因素共同提出有利于全面理解海量地形数据的组织管理方法，并且体现了各个要素之间相互交叉、融合和不能孤立存在与发展的特点。

杨靖宇、张永生等［11］以多用户全球三维仿真为应用背景，研究P2P环境下海量数据的多点并行分发技术。通过依据地理空间的影像分块、编码协议和Tracker服务器所维护的资源拥有节点四叉树索引列表，实现P2P网络中的快速资源定位；利用基于数据预测、缓冲思想的优先下载策略和用户节点间的直接数据交换，提高数据分发效率。最后，通过对现有的多用户三维地形可视化系统进行改造试验，证明该方法的有效性，但由于在多个用户节点存在数据副本，可能会造成用户对数据的非法获取与任意篡改，因此需要进一步研究数据的安全性问题。

许文波、李莉等［12］首先利用CTS和Vegaprime软件开发了一个大地形三维仿真系统。系统在对数据进行预处理之后，利用CTS软件生成虚拟纹理和地形格网，并进行纹理映射。在Vega Prime下引用地形格网和虚拟纹理形成三维的海量大地形场景，并在此基础上开发了基于MFC平台的功能模块，可以成为某些特定行业的三维电子沙盘。解决了在大区域尺度下海量地形数据漫游的难点，为三维仿真系统的研制与应用提供了参考价值。

左志权、陈媛［13］针对传统四叉树、八叉树等数据结构，在解决对于大规模场景漫游存在的瓶颈问题，通过实施多级缓冲机制、采用动态LOD与显存调度技术，以及引入多核CPU并行计算策略，最终构建出一套与数据大小无关的实时地形绘制算法。随着数据量的不断增大，平均绘制速率保持在30帧/s以上，比一般漫游速度高出2～3倍，这种解决方案在海量场景数据和渲染速度方面已取得较好效果，但该方案对计算机性能要求比较高，具有多核CPU并行计算能力。而且基于多核微机平台的并行渲染系统目前还仍然在研究。

潘少明等［14］针对大规模地形漫游所采用的P2P机制没有充分考虑数据的存储特点和时效性，导致节点优选效率不高，服务的时效性不强等问题，提出了一种基于节点分组的P2P海量地形数据共享机制，对P2P节点进行按瓦片分域、按带宽分组、组内按时效分级的模型。通过实验原型系统的比较测试表明，本文方法的平均传输速率更高，时效性更强。但是其在基于P2P的影像传输方面，一是只考虑节点间的物理网络关系或者只考虑节点的兴趣信息，没有根据空间影像的区域特性将两者有效结合；二是对于临近节点选择方法，大多是基于随机选择的方式，缺少对较优邻近节点和节点间历史传输参数信息的考虑。

殷小静等［15］针对海量数据存储与计算机内存不足的问题，提出构建瓦片金字塔模型，并给出了瓦片大小的最优值，提出了一种高效的四叉树瓦片索引方法，并采用最小二乘和算术编码对瓦片进行单独压缩。最后从地形瓦片预装载、双缓存机制、多线程技术、内存优化等方面进行了交互机制优化，并采用Geometry Clipmaps算法进行了地形绘制，以及利用“过渡带”的方法消除裂缝。实验结果具有较好的渲染效果和较高的实时性，但是不适用对于动态的地形块池，而且在实际应用中并没有真正的减少内存。

李振举、李学军等［16］针对海量地形数据在HBase中管理效率不高的问题，提出一种四叉树和Hilbert编码相结合的设计思想。其优点提高了数据入库的速度，降低了地形数据的查询时间。并且设计了地形数据的物理存储结构，只需通过行键即可调用相应区域的数据信息，方便了用户的操作。但也存在一些不足，比如复杂的查询，响应时间比较长。

杨莹、李雪等［17］针对有效地对海量地形数据进行组织并实现可见数据在内外存之间的实时调度，由此设计了一种矩形二叉树模型，其优点是能够保证地形数据很好的连续性，从而降低了每帧访问的数据量。这种无指针数据索引二叉树编码方式，大大降低了海量数据的调度次数，实现数据块的准确定位。但该论文对地形的管理与绘制是基于细粒度层次细节模型的，即绘制单元为单个三角形，而且随着GPU并行处理能力的提高，目前该方法并未大范围实施。

3基于GPU的海量地形数据处理优势

由于GPU的性能逐渐提高，GPU不仅具备高性能和高质量的图形处理能力，还适用于通用计算，而且鉴于CPU与GPU之间带宽的提高，以及GPU可编程能力的不断强大，GPU逐渐替代CPU完成图形软件处理运算。实施基于GPU的地形渲染将极大的提高地形渲染效率。目前，国内对基于GPU的地形数据存储和传输在进行深入地研究。

张兵强［18］为了解决海量数据在地形可视化中存储和传输的压力，通过构建地形数据多分辨率金字塔模型，采用一种基于块的GPU实时解压的高程数据无损压缩和有损压缩算法。该算法首先对地形块数据进行线性预测，其次对高分辨率地形块的预测误差采用变长编码定理，实现对高分辨率地形数据的无损压缩，不会损失地形细节；而对低分辨率地形块的预测误差，采用有损的预测量化编码，并将在GPU上的快速并行解压处理流程展现出来。该算法的优点是随着数据规模的不断增大可以取得较高的压缩率，但不足之处是地形块误差的计算量较大，耗费时间较长。

李浩等［19］为了充分发挥GPU的批量绘制的性能，提出了把它用在全球格网的快速绘制上。他们把地形数据通过重新编码存储在高度图中，再结合ShaderModel3.0引入的顶点纹理拾取技术，在GPU中进行解码，得到原始的DEM数据，避免了在CPU上执行顶点缓存的更新，降低了CPU的负担，能达到实时绘制的要求。但是仍然存在许多问题，比如基于球体剖分会造成两极的误差很大，精确性存在差异不能满足实际需要，仍需进一步研究基于椭球体的剖分。而且在网络传输的及时性方面需要将网络的带宽考虑在内。

张立民等［20］针对大规模地形数据绘制的速度以及生成图像清晰度的问题，从高度场形式的地形数据进行组织、LOD误差选择标准、裂缝以及突跃现象的处理、视锥体裁减等各个环节入手，提出合理的解决方案。其研究结果显示该方法能够充分利用GPU进行绘制，可以适用于大规模地形数据绘制。

曹巍等［21］提出利用GPU来对地形进行无缝渲染。本文在构建多层次地形网格时采用二叉树的细分方法，用行、列标号来表示网格模型。首先，将高程数据转化为便于GPU读取的高程纹理图，再通过顶点纹理提取（VTF）技术提取三维真实坐标进行渲染，同时，采用实时优化自适应网格（ROAM）算法的强制拆分法，通过相邻地形块控制在一定的等级上来消除裂缝。最后，为了减少向GPU传递的数据量，采用Triangle Strip方式进行渲染，使相邻三角形中公共顶点坐标不必重复传递。从实验分析来看，在保证渲染帧率较高的前提下同时也解决了地形裂缝的问题。但是对于两等级相差较大的分块来说该处理方法存在不足。因此王文博等［22］又在此基础上提出了基于细分着色器的硬件无缝绘制方法。其基本思想是通过利用一种细分着色器进行地形网格细分的层次细节地形渲染算法，并针对外部细分因子对裂缝进行消除。而且通过将四叉树结构存储至顶点缓冲区，缓解了CPU与GPU的资源交换。其优点是不需要大量的细分模板，实时漫游甚至回读过程，细分过程与可编程管线对映，更加顺畅。而且能够得到无缝的大规模地形。

李尚林等［23］提出了一种GPU网格生成的地形可视化方法来解决分块LOD方法存在的数据传输瓶颈问题，并且通过一系列方法设计了一个全球地形可视化系统GTVS，用于全球高精度地形数据与多分辨率高清卫星影像数据的调度与渲染等，该方法的优点是降低了GPU和CPU的工作耦合性，对GPU进行了更友好的设计，但该方法也存在一些不足，比如对GPU的要求更高，必须要到达一定的显卡支持，而求每个块的边界细分是有一定联系的，故对块边界的误差要求会比较严格。

4结语

长期以来，三维地形的可视化技术被广泛应用于虚拟现实、三维游戏、战场仿真、飞行模拟、电子地图、地形漫游等方面的研究重点。通过对当前国内外相关研究的归纳分析，可以看出，当前国内外针对三位地形可视化技术的研究非常广泛，尤其是基于分形理论的地形模拟非常盛行，但是还缺乏系统性和比较性，具体的实现算法还需要进一步的研究，而且全球地形可视化向着GPU的设计发展，系统将会让更多的GPU资源用于发展，目前对于海量三维地形数据的高效快速地实时绘制和漫游显示仍然面领着严峻的挑战。无论是国内外的学者都将该问题作为研究重点。

［1］P Lindstrom，V Pascussi.Visualization of Large Terrains Made Easy［C］//Proceedings of the conference on Visual⁃ization'01，San Diego，2001.Washington，IEEE Comput⁃er Society Press：363-370.

［2］J S Falby，M J Zyda，DR Pratt，etal.NPSNET：Hierarchi⁃cal Data Structures for Realtime Three-dimensional Visu⁃al Simulation［J］.Computer Graphics，1993，17（1）：65-69.

［3］R Pajarola，M Antonijuan，R Lario.Quad TIN：Quadtree Based Triangulated Irregular Networks［C］//Proceedings of the conference on Visualization'02，Boston.Washing⁃ton，IEEE Computer Society，2002：95-102.

［4］唐桂文，张庆娟，王功明，等.基于三维GIS的海量地形数据存储和调度的研究［J］.测绘科学，2008（3）：110-112，120.

TANG Guiwen，ZHANG Qingjuan，WANG Gongming，et al.Research of storage and schedule of huge terrain based on 3D GIS［J］.Science of Surveying and Mapping，2008（3）：110-112，120.

［5］温菊屏，李利军.大地形数据存储和调度方法研究［J］.佛山科学技术学院学报（自然科学版），2007（4）：13-15.

WEN Juping，LI Lijun.Data storage and scheduling of the large-scale terrain［J］.Journalof Foshan University（Natu⁃ral Science Edition），2007（4）：13-15.

［6］蒋秉川，游雄，夏青.一种基于体素的三维地形可视化方法研究［J］.测绘通报，2013（3）：46-49.

JIANG Bingchuan，YOU Xiong，XIA Qing.Research on a Method of Voxel-based Three-dimensional Terrain Visu⁃alization［J］.Bulletin of Surveying and Mapping，2013（3）：46-49.

［7］吴晨，朱庆，张叶廷，等.基于MongoDB数据库的多时态地形数据存储管理优化方法［J］.地理信息世界，2014（4）：37-42.

WU Chen，ZHU Qing，ZHANG Yeting，et al.Storage Man⁃agement Optimization Method for Multi-Temporal Terrain Data Based on MongoDB Database［J］.Geomatics World，2014（4）：37-42.

［8］李光辉，邵伟，吴东亚.基于OSG的大地形并行快速调度问题研究［J］.系统仿真学报，2013（S1）：282-285，296.

LI Guanghui，SHAO Wei，WU Dongya.Research of Large Terrain Multithreading Fast Scheduling Based on OSG［J］. Journalof System Simulation，2013（S1）：282-285，296.

［9］杨冰，谭力恒，魏迎梅.基于连续球面剖分的全球地形数据组织模型［J］.系统仿真学报，2012（1）：150-153.

YANG Bing，TAN Liheng，WEI Yingmei.Global Terrain Data Model Based on Continuous Spherical Grid［J］.Jour⁃nalof System Simulation，2012（1）：150-153.

［10］岳利群，夏青，王洪威，等.大规模三维地形可视化中数据组织管理影响因素探讨［J］.测绘科学，2010（5）：158-160.

YUE Liqun，XIA Qing，WANG Hongwei，et al.Research on the affect factor of data organization and management in large-scale terrain visualization［J］.Science of Survey⁃ing and Mapping，2010（5）：158-160.

［11］杨靖宇，张永生，蔡畅.多用户全球三维仿真的数据组织与调度研究［J］.系统仿真学报，2011（9）：1896-1899.

YANG Jingyu，ZHANG Yongsheng，CAI Chang.Study of Data Organization and Scheduling Method in Multi-user Accessed Global 3D Visualization Application［J］.Jour⁃nalof System Simulation，2011（9）：1896-1899.

［12］许文波，李莉，周虹霞，等.海量地形三维仿真系统的设计与实现［J］.电子科技大学学报，2011（3）：418-423.

XU Wenbo，LI Li，ZHOU Hongxia，et al.The Design and Implemention ofa Large Area Terrain 3D Simulation Sys⁃tem［J］.Journal of University of Electronic Science and Technology of China，2011（3）：418-423.

［13］左志权，陈媛.TB级地形数据实时漫游核心算法研究［J］.中国图象图形学报，2010（9）：1411-1415.

ZUO Zhiquan，CHEN Yuan.Research on kernel algo⁃rithm of real-time rendering based on TB lever terrain data［J］.Journal of Image and Graphics，2010（9）：1411-1415.

［14］潘少明，喻占武，王浩.基于节点分组的P2P海量地形数据共享机制［J］.武汉大学学报（信息科学版），2009（6）：650-653.

PAN Shaoming，YU Zhanwu，WANG Hao.Massive Ter⁃rain Data Sharing in Pyramid Hierarchical Peer-to-Peer Networks［J］.Geomatics and Information Science of Wu⁃han University，2009（6）：650-653.

［15］殷小静，慕晓冬，徐义文，等.海量地形数据的管理和交互策略优化［J］.计算机应用，2011（9）：2465-2467.

YIN Xiaojing，MU Xiaodong，XU Wenyi，etal.Optimized management and interactive strategy for massive terrain data.［J］.Journal of Computer Applications，2011（9）：2465-2467.

［16］李振举，李学军，谢剑薇，等.基于HBase的海量地形数据存储［J］.计算机应用，2015（7）：1849-1853.

LI Zhenju，LIXuejun，XIE Jianwei，etal.Massive terrain data storage based on HBase［J］.Journal of Computer Applications，2015（7）：1849-1853.

［17］杨莹，李雪，杨蕊.矩形二叉树实现海量地形数据组织与管理［J］.计算机工程与应用，2009（20）：169-172.

YANG Ying，LI Xue，YANG Rui.Organization and man⁃agement of massive terrain dataset using rectangular bin⁃tree［J］.Computer Engineering and Applications，2009（20）：169-172.

［18］张兵强，姜本清，方君.GPU快速解压的多分辨率地形高程数据压缩算法［J］.计算机应用研究，2015（11）：3513-3517，3520.

ZHANG Bingqiang，JIANG Benqing，FANG Jun.Multi resolution terrain height field data compression for rapid GPU decoding［J］.Application Research of Computers，2015（11）：3513-3517，3520.

［19］李浩，相恒茂，孙久虎.基于GPU的全球地形数据加速绘制技术研究［J］.山东国土资源，2015（7）：59-64，71.

LI Hao，XIANG Hengmao，SUN Jiuhu.Research on Ac⁃celerated Rendering Technique of Global Terrain Based on GPU［J］.Land and Resources in Shandong Province，2015（7）：59-64，71.

［20］张立民，闫文君.基于GPU的大规模地形数据绘制算法［J］.计算机与现代化，2012（1）：145-150.

ZHANG Limin，YAN Wenjun.A Method of Real-time Rendering for Large Terrain Based on GPU［J］.Comput⁃er and Modernization，2012（1）：145-150.

［21］曹巍，段光耀.基于二叉树和GPU的无缝地形场景渲染方法［J］.计算机应用，2012（9）：2548-2552.

CAO Wei，DUAN Guangyao.Seamless terrain rendering method based on binary tree and GPU［J］.Journal of Computer Applications，2012（9）：2548-2552.

［22］王文博，殷宏，解文彬，等.基于硬件细分的层次细节地形渲染算法［J］.计算机应用，2015（6）：1716-1719，1729.

WANG Wenbo，YIN Hong，XIE Wenbin，et al.Terrain rendering for level of detail based on hardware tessella⁃tion［J］.Journal of Computer Applications，2015（6）：1716-1719，1729.

［23］李尚林，郑利平，张迎凯，等.GPU Tessellation全球地形可视化方法［J］.中国图象图形学报，2015（10）：1412-1421.

LI Shanglin，ZHENG Liping，ZHANG Yingkai，et al. GPU Tessellation method of global terrain visualization［J］.Journal of Image and Graphics，2015（10）：1412-1421.

Research Progress of 3D Terrain Data Structure and Scheduling

YUAN Songhe JIN Hailiang LILiulei GENG Wenxuan
（Schoolof Surveying and Land Information Engineering，Henan Polytechnic University，Jiaozuo 454000）

Three-dimensional（3D）Terrain visualization technology can transform geospatial information that can or can not described in the two-dimensional plane into 3D environment and integrate the information into an 3D entity by some rules.People can min Internalrelations and rules ofthings to improve reliability of research results by the technology.This paper summarizes and induces research achievements of recent years based on 3D data storage and scheduling by domestic and overseas scholars，which has a certain reference value for the future technology research in this field.

3D terrain，3D visualization，Ogre3D，data reduction，GPU

P283

10.3969/j.issn.1672-9722.2017.08.037

2017年2月9日，

2017年3月23日

国家自然科学基金项目：海量地形数据无冗余存储模型及并行绘制研究（编号：41541011）资助。

袁松鹤，女，硕士研究生，研究方向：三维地形可视化。靳海亮，男，博士后，教授，硕士生导师，研究方向：三维地形可视化。