基于Grid/TIN混合结构的地形实时可视化算法研究

1 绪论1.1 研究背景及意义目前地形的模拟表述以及各种地学分析通常是在数字高程模型（Digital Elevation Model，DEM）基础上进行的，DEM 作为地形数字化表述方式有着诸多优点，广义上其由 Grid 结构、TIN 结构、等值线结构等三种方式进行组织[1]。 随着对地观测技术的发展，以 Grid 数据和 TIN 数据为代表的各种尺度地形地物数据的获取更加方便快捷，使得在大尺度范围内构建精细化的地形场景成为可能。传统的全站仪、经纬仪也可以获取小范围、高精度的地形数据来作为补充。由于地球系统的复杂性，任何对地观测手段都只能获取它的片面信息，多源数据融合便成为获取其全面丰富信息的有效手段[2]。在现实世界中，单一的数据模型难以高效表述各种地形场景，如地形变化不大区域适宜采用 Grid 进行表述，而如果想精细表述河流和湖泊边界、公路带状地形等，则 Grid 虽然可以通过提高分辨率的方式得到，但会带来较大的数据冗余。可以通过在大范围低分辨率的地形场景中，局部加入高分辨率的TIN 模型来实现此目的。 人们生活在三维世界中，利用获取的多源数据实现三维空间的可视化，能够带来更直观的感受。在现代新兴信息技术的驱动下，人类的地理空间信息交流已经超越时间和空间制约，正努力朝更接近自然的多感知的高级方式虚拟地理环境方向（VGE: Virtual Geographic Environment）发展[3]。 进入 21 世纪以来，随着计算机科学技术的发展，其为地形可视化的实现提供了可靠的硬件和软件保障。地形数据是国家地理信息系统建设的基础，三维地形可视化更是国家倡导的数字地球;、数字中国;、数字城市;等系统建设的基础及关键技术之一。三维地形可视化能够辅助自然灾害、险情等的预报，优化资源的配置并且对促进空间信息在多个领域的应用发展具有重要的意义。 地形可视化是一门以研究数字地形模型（Digital Terrain Model，DTM）或数字高程域（Digital Height Field）的显示、简化、仿真等内容的学科，其应用涉及地理信息系统、虚拟现实、气象数据可视化等诸多领域[4]。它是近二十年来国内外众多学者研究热点之一，地形的可视化具有动态直观、可交互、沉浸感等特点，极大的满足了人们对地形更加直观的认知和应用的需求。 随着地形场景可视化技术、数据融合技术以及多源数据量测获取技术的发展，利用多源数据的无缝融合模拟表述地形场景信息、反应真实的地理环境、恢复空间对象真实面貌的有效方法和手段，并实现地形场景的可视化，逐渐成为近年来新的研究热点。.......1.2 国内外研究现状在地形可视化过程中，虽然现今计算机处理能力与内存容量比过去得到很大提高，但是由于地形数据庞大，其仍然对计算机性能有不小挑战。为了更好的发挥计算机硬件的绘制性能，在满足视觉要求的前提下，需要对地形进行简化。同时，由于计算机内存容量有限，难以也没必要把所有数据一次性调入内存。所以本文的研究重点放在Grid 与 TIN 的模型简化算法和数据存储与调度方法的研究上。 基于细节层次（Levels of Detail，LOD）的地形简化渲染技术是遥感、地理信息系统领域的一个重要研究内容。LOD 的基本思想是指在同一个场景中，远离视点的物体只需粗糙表述，而离视点近的物体需要详细表述，通过具有不同细节的一组模型对物体进行渲染[5, 6]。该技术最早由 Clar[7]在 1976 年提出，他认为同一个场景中的物体可以由多个不同细节的模型组成，当物体占用屏幕较小区域时，用粗糙的模型渲染，在实时的显示过程中提高模型的渲染效率。 地形网格简化算法可以分为静态LOD算法、动态LOD算法和多分辨率分块LOD算法。静态 LOD 算法要制作多个不同细节层次的模型，渲染时不需实时生成，只需加载相应层次细节的模型[8-11]；动态 LOD 算法在每帧渲染之前进行重新计算，生成指定的地形模型[12-15]；多分辨率分块 LOD 算法思想是在同一渲染场景中可以存在多种分辨率地形块，每种地形块内分辨率相同。.........2 三维地形可视化理论基础地形模型表述有多种方式，按种类一般可分为 3 类：Grid 模型，TIN 模型和等高线模型。Grid/TIN 混合结构模型是通过 Grid 与 Tin 结合方式来表述复杂地形模型。地形简化技术和地形数据组织调度都是三维地形可视化重要组成部分。本章着重介绍三维地形表述方法、地形简化技术以及地形数据组织调度等基础理论，并进行总结归纳。2.1 三维地形模型表述研究数字高程模型(DEM)是地形曲面的数字化表述方式，也是在地形场景建模中经常采用的数据模型。DEM 通常使用有限的采样点按照某种规则连接成一系列的曲面或平面来逼近原始曲面[38]。数字高程模型是某个区域上的三维向量有限序列，人们对每个格网所标示的数值存在两种观点：一种观点认为格网内部具有同质性，格网内部高程相等，这种观点下 DEM 表述的是一种非连续面；另一种观点认为格网数值代表格网中心点的高程或者网格单元的平均高程值，这种观点下 DEM 表述了一种连续面，此种方法在目前受到人们普遍接受。 Grid 结构简易，易于存储，适宜计算机处理，但其冗余度比较大，对于精细表述地形特征表现效果不佳，如对于起伏高差变化较大的地方难以精细表述，不能精确反映出山峰、山谷等的特征。不规则三角网（Triangular irregular wor，TIN）是由连续的三角面组成的，它以一系列互不交叉重叠的三角形面来近似表述地形曲面。其中三角形的大小、形状由不规则分布的点的密度和位置决定。TIN 能够随地形变化灵活的改变三角形面片大小，在地形变化较小的平坦地区，三角形面片较大、分布较为稀疏，能够避免数据冗余，在地形起伏较大复杂地区，三角形面片较小、分布密集，可以有效保留地形特征。 ..........2.2 地形简化技术研究在地形场景绘制过程中，会产生数据冗余的现象：视点距离物体较近时，会在屏幕上占据较大空间；当视点距离物体较远时，物体占用较小屏幕空间，但经投影后绘制在屏幕上的很多面片对提高视觉可视化效果的贡献很小，却仍然占据了很多绘制资源。因此为提高渲染效率，对地形场景的简化是十分必要的。 所谓细节层次技术（level of details，LOD）就是在视觉效果影响不大的前提下，通过简化场景模型的表面细节来减少几何复杂性，用来提高渲染效率[38]。LOD 可以有效地简化模型复杂度，在确保图形质量的情况下实时渲染。LOD 在许多领域得到应用，如飞行仿真、交互式可视化、虚拟现实等，并是其中不可或缺的关键技术。 物体细节层次的建立有三种方案：一种是静态 LOD 技术，即事先准备好物体的多个不同层次细节模型，然后有选择性的调用；一种则是动态的简化，即动态 LOD技术，它不需要事先做预处理，准备多个物体层次模型，而是在漫游的每一帧中计算；最后一种多分辨率 LOD 简化技术和前面两种最大的不同在于其是基于块的技术，在同一场景中可能处处存在不同分辨率的模型[42, 43]。静态 LOD 技术，即采用离散的层次细节来表示同一个模型的技术。它是三维地形简化技术发展的第一个阶段。在 90 年代前半期以前，该算法是三角形简化算法中的主流算法。对于同一个物体模型，在绘制场景之前，生成若干个精度不同的模型副本，即生成若干使用不同个数三角形表示的层。各层次之间没有必然的联系，在渲染时简易的计算视点的距离或者屏幕误差来决定选取哪一个细节层次。若距离或者屏幕误差超过预先设定的阈值，则整个物体就选用另一层次的模型来表示物体。该算法简易明了，但是过于粗暴，一个突出的缺点就是在层次之间切换的过程中会产生视觉跳跃感。有多种方法可以减少该现象：一种是通过减少各个层次之间的差别，并生成更多的层次。该方法虽然有效的减少视觉跳跃感，但是占用过多的存储空间去存储各个层次；一种是在距离视点较远处，进行层次细节的更新交换；还有一种便是在层次交换的过程中进行插值计算，即在中间加入过渡的细节。这些方法虽然能够减少跳跃感，但其效果并不明显且附加的计算代价或者存储代价较大。

..........3 基于 Grid/TIN 混合结构的地形简化 .... 173.1 Grid/TIN 混合结构地形组织 ....... 173.1.1 Grid/TIN 融合规则 .... 173.1.2 地形瓦片拓扑关系 ........... 183.2 基于矢量线的约束 TIN 构建 ..... 183.3 基于 ROAM 的 Grid 地形简化 ........... 193.4 基于 PM 的 TIN 地形简化 .......... 263.4.1 算法基础 .... 263.4.2 算法改进 .... 293.5 地形裂缝消除 ...... 343.5.1 裂缝消除方法 ........... 343.5.2 裂缝消除步骤 ........... 353.6 本章小结 ...... 384 地形场景组织调度及渲染优化 ..... 394.1 地形数据外存组织方法 ...... 394.1.1 地形数据的外部存储方式 ....... 394.1.2 地形数据组织形式 ........... 394.2 基于多线程的数据调度方法 ...... 404.3 混合地形渲染优化方法 ...... 454.4 本章小结 ...... 485 实验验证与分析 ..... 495.1 实验数据与方法 .......... 495.2 实验的软硬件环境 ...... 505.3 实验结果展示与分析 .......... 515.4 本章小结 ...... 585 实验验证与分析5.1 实验数据与方法本文采用庐山九江9个图幅5米分辨率的DEM数据和比例尺1:1万的DLG数据，如图 5.1 所示。数据范围为东经 115°52′30″ ~ 116°03′45″，北纬 29°30′00″ ~ 29°37′30″。原始Dem数据行列数分别为2806和3661。数据处理先要将9块DEM数据进行拼接，然后进行裁剪。裁剪大小行数为 2561。以从DLG 数据中抽取的庐山景区主要道路及湖泊作为实验数据。实验数据如图 5.1 所示，其中 DLG 数据包括 39 个多边形，所有边界点共 12575 节点。本文实验的测试环境是在 Window 7 旗舰版 64 位操作系统，使用 Qt 5.4.0 作为开发平台，采用 C++语言和 OpenGL 编程开发。PC 主要硬件配置：Intel Core(TM)2 Quad 双核 CPU 2.66GHz；内存容量 4G，显卡为 NVIDIA GeForce 9800GT，显存容量 512M。 图 5.3 显示 Grid 地形分块及简化情况，蓝色线框为包围盒，可见相邻 Grid 地形瓦片之间简化连续，不存在裂缝，并且保留了地形特征。图 5.4 显示了视椎体裁剪效果，可见视椎体以地形瓦片为基本单元进行剪裁。...........总结本文结合 Grid、TIN 的优点，利用 Grid/TIN 混合数据结构表述地形场景。针对Grid/TIN 混合结构地形组织方式，设计出混合结构地形瓦片的融合规则；为满足实时渲染需求，提高渲染效率，本文分别对 ROAM 算法和 PM 算法做出改进，并将两者结合提出一种适用于混合结构的地形简化算法；针对大地形场景数据管理，本文设计出一种混合数据组织与调度方法；最后，通过实验对本文算法进行分析验证。本文研究工作主要包括：(1) 本文针对 Grid/TIN 混合结构的地形组织，设计了混合结构地形瓦片的融合规则，建立了各地形瓦片之间的拓扑关系。给出基于矢量线的约束 TIN 构建方法，以此方法在庐山DEM数据的基础上，添加矢量线的约束，生成了Grid/TIN的融合数据。(2) 基于 Grid/TIN 混合结构的地形实时简化算法设计。本文首先针对传统 ROAM算法在处理混合数据上的不足分别对 ROAM 简化判据、视椎体剪裁方式以及渲染方式进行了改进；其次分析了传统 PM 算法折叠代价计算方式、折叠代价的排序以及拓扑错误的处理，并对它们进行了改进；针对 Grid 与 TIN、TIN 与 TIN 之间渲染过程中存在的裂缝，设计了相应的裂缝消除算法；为进一步提高渲染效率，本文优化了地形场景的剪裁及渲染方式；最后通过实验验证了算法的有效性。(3) 混合地形数据的组织与调度。本文针对大地形场景渲染过程中，地形数据量大及计算机内存有限等问题，设计了一种基于文件的 Grid/TIN 混合结构数据的外存存储方式，设计了一种基于多线程、多缓冲区的数据调度方法。.........参考文献(略)