三维地表模型的自动综合及渲染算法研究

论文总字数：29615字

摘 要

随着3S技术的迅猛发展，获取海量高精度的地形数据越来越容易，海量高精度地形数据给数据存储、传输和管理都带来了新的挑战，迫切需求提高三维地表模型形实时渲染效率的相关解决方案。本文致力于研究三维地表模型的自动综合及渲染相关理论与方法。论文的主要研究内容如下：

（1）在分析现有点云精简算法优缺点的基础上，研究了一种特征保留的自适应点云精简算法。该算法利用曲率将点云数据分成特征点和非特征点，对特征点采用基于法向量夹角的精简方法，对非特征点采用基于最小距离的精简方法。实验证明，该算法能够有效保证精简后的点云不丢失型面特征。

（2）对很多经典的三角剖分算法进行了研究，在理论上比较了它们的优缺点，确立了基于逐点插入法的大规模点云数据三角网格构建的技术路线。

（3）整合上述两种算法，提出了一种三维地表模型的自动综合及高效三维地表模型多分辨率渲染方案。该算法能够根据用户给定的一系列阈值对输入的点云数据进行预处理，即进行点云精简和三角化，预处理结束之后可以实现与用户交互式的多分辨率三维地表模型渲染。

（4）在Windows平台和openGL环境中，采用面向对象方法，用Visual C 语言实现了上述算法，开发出了一个支持三维地表模型自动综合及渲染的软件。

关键字：点云简化，Delaunay三角剖分，多分辨率显示，三维地表模型，三维渲染

Automated generalization and rendering algorithm of 3D terrain model

Abstract

With the rapidly development of GIS,IS and GPS, it’s really easy to get massive and highly accurate point cloud data of terrain. But the highly accurate terrain data has resulted in a great burden on data storing, transmission and management. What’s worst, it can slow the real-time rendering of 3D terrain model. To solve this problem, we propose a automated generalization and rendering algorithm of 3D terrain model. The main research works are as follows:

(1) We have done a lot of research work on simplification algorithm of point cloud. Finally we choose an adaptive simplification algorithm with feature preserving for point cloud, this simplification algorithm devide the point by the curvature into two classification: feature point and non-feature point. For the feature point, we use a simplifying criterion based on the angle of normal vector. For the non-feature point, we use a simplifying criterion based on minimum distance. The point cloud simplified by this simplification algorithm can preserve the sharp feature of the original point cloud effectively.

(2) We have done a lot of research work on triangulation algorithm of point cloud. After comparing the advantages and disadvantages of these algorithm, we choose the incremental insertion algorithm to triangulate the point clouds.

(3) Based on the two algorithm mentioned above, we propose a automated generalization and rendering algorithm of 3D terrain model. According to the a set of thresholds defined by the user, this algorithm can carry out a pretreatment on the input point cloud data of terrain model, which can simplifify and triangulate the point cloud. After the pretreatment, this algorithm can render a 3D terrain model in multiresolution interacting with users.

(4)We have accomplished the development of the software using Visual C and openGL.

KEY WORDS: simplification of point cloud, Delaunay triangulation, multiresolution, 3D terrain model, 3D rendering

目 录

摘 要 I

Abstract II

第一章 绪 论 1

1.1 研究背景 1

1.2 国内外的研究现状 2

1.2.1 点云精简 2

1.2.2 三角网格重构 3

1.3 本文的研究目的和主要研究内容 4

第二章 特征保持的点云自适应精简算法 5

2.1 引言 5

2.2 几种经典的点云精简算法 5

2.2.1 包围盒法 5

2.2.2 均匀网格法 5

2.2.3 最小距离法 6

2.2.4 曲率采样法 6

2.2.5 分析总结 6

2.3 特征保持的点云自适应精简算法的基本思想 6

2.4 特征保持的点云自适应精简算法中的三大关键步骤 7

2.4.1 K邻域的求取 7

2.4.2 法向量估算 8

2.4.3 曲率估算 9

2.5 特征保持的点云自适应精简算法的精简原则 11

2.5.1 基于法向量夹角的特征点精简方法 11

2.5.2 基于最小距离的非特征点精简方法 12

2.6 算法具体流程 12

2.7 算法程序实现 14

2.8 实验结果与分析 16

2.9 本章小结 19

第三章 三角网格重构算法 20

3.1 引言 20

3.2 Delaunay三角剖分 20

3.2.1 Delaunay三角剖分的定义 20

3.2.2 Delaunay三角剖分的准则 21

3.2.3 Delaunay三角剖分的特性 21

3.2.4 经典Delaunay三角剖分算法 21

3.3 本文使用的三角网格重构算法 25

3.4 本章小结 25

第四章 三维地表模型自动综合及渲染软件的开发 26

4.1 引言 26

4.2 软件系统架构 26

4.2.1 开发框架与输入文件 26

4.2.2 三维地表模型自动综合的实现方案 26

4.2.3 三维地表模型多分辨率渲染的实现方案 26

4.2.4 相关文件的存储格式 27

4.2.5 系统流程图 28

4.3 软件的测试实验与分析 29

4.3.1 实验具体步骤 29

4.3.2 实验数据分析 33

4.4 本章小结 38

第五章 总结 39

5.1 工作总结 39

5.2 尚存在的问题及对未来工作的展望 39

致谢 41

参考文献 42

1. 绪 论

1.1 研究背景

“数字地球”是由美国副总统戈尔在1998年提出的概念，作为一条联系信息科技、空间科技、地球科学等交叉学科的纽带，其在当代信息社会的地位变得越来越重要^[1][1]。以目前的科技水平，大量采集地球的三维的、多分辨率的、动态的数据已经不再困难，只要将这些数据按地理坐标整合到一起就可以得到一个虚拟地球，即数字地球。数字地球实际上就是对地球大数据的一个采集、整合与再现，利用先进的地理信息采集技术将实体地球数据化，通过地理信息系统对这些数据进行管理，利用虚拟现实技术将这些海量的地球数据三维再现。在这三个环节中，地球数据的三维再现至关重要，因为它可以让我们更好地感知虚拟的数字地球。而数字地球三维再现中最重要的部分就是地形的建模与三维可视化。

早在20世纪60年代，地形三维可视化的概念随着地理信息系统的出现和发展应运而生。地形三维可视化技术是指在计算机上对虚拟地形数据进行逼真的三维显示、多分辨率表达和网络传输等内容的一种技术，具有动态化和可交互两大特点。作为数字地球与用户交互的一个重要环节，地形三维可视化的高效性和实时性显得异常重要。然而当前主流的数字地球平台在面对海量的地形数据时，普遍存在渲染效率较低的问题^[2]。

建立三维地表模型要从获取地表环境的描述信息开始,这些信息主要包括地形地物的空间位置信息和地表的纹理信息等。获取这些信息的方法主要有航空摄影、卫星遥感、激光扫描以及雷达探测等手段，然而随着3S技术（GIS、RS和GPS）的迅猛发展，如今获取大规模地形数据变得越来越容易，不仅数据的采集速度越来越快，数据数量越来越大，数据的采集精度也越来越高。

能够轻松地获得海量、高精度的地形数据对于构建数字地球来说无疑是有益处的，因为原始数据精度越高，所能显示真实地形的细节也就越详尽。可是高精度的地形渲染往往会受到硬件平台的限制，对于用户而言，有时并不需要如此高精度的显示细节。正是这些海量、高精度的数据使得三维地表建模的难度也大大提高。如何组织和处理这些海量、高精度的地形数据，使得在不同性能的计算机平台上都能根据需要流畅地渲染出三维地表模型，成为了计算机图形学、计算机视觉、空间信息处理与虚拟现实等领域中研究的热点。

本课题致力于研究出一种三维地表模型的自动综合及渲染算法，能够将海量、高精度的散乱点云数据按照用户所需求的分辨率进行精简，并快速高效的渲染出三维地形。该算法能为包括数字地球、地理信息系统、大型3D游戏等在内的需要渲染大型地形的虚拟现实提供稳定高效的解决方案，实现“多精度”和“快速高效”这两大特点。

1.2 国内外的研究现状

为了解决地形数据海量、高精度的特性与地形三维渲染的高效、流畅特性之间的矛盾，本文本课题致力于研究出一种三维地表模型的自动综合及渲染算法，实现地形三维渲染的“多精度”和“快速高效” 这两大特点。要想实现“自动综合”，我们需要使用点云精简算法来精简地形的点云数据；要想实现地形的渲染，我们需要使用快速稳定的三角网格重构算法来构建地形点云数据的三角网格。因此，本文针对这两大算法做了大量研究，这两种算法的研究现状如下。

1.2.1 点云精简

根据待简化点云的拓扑结构，已有的点云精简算法可以被分为以下两大类：基于多边形网格的方法和基于离散点云数据的方法。前一种简化方式先将深度图像或三维点云数据三角化，再根据相应的法则删除冗余点。基于点云数据的算法不需要预先建立多边形网格，可以直接对深度图像或点云数据进行简化。由于点云拓扑结构信息的缺失，要在保留原始点云细微结构特征的情况下删除冗余点是件相当困难的工作。

国外的点云精简算法的相关研究开始的比较早。Martin等人^[2][3]在他们的欧盟哥白尼计划中发表过一种基于规则网格的数据简化方法。这种方法采用了一种已经在图像处理中广泛应用的中值滤波法。通过建立一个网格结构，所有输入点就可以被分配到这些网格之中，然后选择一个中心点来代表属于该网格的所有的数据点。Lee等人^[3][4]提出了基于单向或双向非规则网格的简化方法，然而这些方法只适用于深度图像。

Alexa等人^[4][5]提出了基于移动最小二乘法（MLS）的简化方法。在这个方法中，先计算出每个点到最小二乘曲面的距离，再将其中距离最小的那些点删除。Scheidegger等人^[5][6]将最小二乘法推广应用到了简化点模型曲面和建立高质量三角网格中。Moening和Dodgson^[6][7]提出了快速行进最远点采样准则，不仅适用于二维图像，还适用于以三角面片、点云或隐式曲面存在的高维曲面。Pauly等人将一些流行的基于网格的简化方法改进并推广至适用于点云简化的情况，并对其中一些基于聚类、增量式区域增长法和迭代法的算法在精度、采样分布和计算效率这些方面进行了测试。Wu和Kobbelt^[7][8]提出一种基于最优化椭圆Slapts（一种具有法向量和一定空间扩展的面元）的点云简化方法，在该方法中，在保持低于全局最大容差的情况下，用近似最小Slapt集合来拟合整个表面。Song和Feng提出了一种基于全局聚类的点云简化方法，通过最小化输入点集和简化后点集的几何偏差来得到一个全局最优的结果。

最近，弦长、邻近点的空间距离和法向变量已经被广泛应用到点的采样之中。Kalaiah和Varshney^[8][9]用从周围点得到的局部几何特征值来衡量每个单独点的冗余度。Listen^[10]将一个点的信息含量定义为与邻近点之间的距离、非平面度和通过临近点估计的法向量偏差这些因素的加权总和值。Lee等人提出了一种基于局部几何特征的点云简化方法，该方法按照每个点的法向量值使用三维网格来精简点云。Miao等人^[9][11]提出了一种自适应曲率识别的采样方法，该方法设计了一种自适应的均值移动聚类法来生成非均匀分布的采样点。Kang等人提出一种平衡的特征敏感的点采样方法，他们通过正常化局部区域采样点的个数来使得整个采样点的分布达到平衡。

剩余内容已隐藏，请支付后下载全文，论文总字数：29615字

相关图片展示：