基于不规则三角网的数字地形生成与简化算法研究

摘要

随着数字地球概念的提出及虚拟现实技术广泛应用,三维地形模型作为其中不可缺少的组成部分,扮演着越来越重要的角色。它是建立虚拟地形环境的“骨架”,是对复杂地形进行分析和研究的基础,是绘制逼真地形环境场景、准确表达空间信息相关关系以及空间分析结果可视化的前提。由于三维地形场景的生成一般基于真实的地形数据和高分辨率的遥感影像,对于大规模地形场景的显示来说,如此庞大的数据量使得图形工作平台无法进行实时的显示。针对大规模地形场景的绘制问题,国内外的学者进行了大量的研究,其工作重点集中在TIN的生成技术和多分辨率地形模型上。 本文主要研究了三维地形模型建模的基本理论与方法,总结了前人在地形模型建模方面所作的工作。针对逐点插入算法在构建TIN地形模型时效率低的问题,提出了一种基于“虚拟网格”划分的VG-逐点插入法,并给出了一种优化离散点插入顺序的方法,减少了点插入过程中需查找的三角形数目和需要重构的三角形个数。VG-逐点插入算法使时间复杂度由原来O(n2)降低到了O(nlogn),实现了TIN地形模型的快速建立。同时研究、对比了各种构造多分辨率地形模型的算法,针对常用的PM算法存在的时间效率低、部分拓扑关系不能有效保持的问题,将二次误差测度与顶点的法向锥半角相结合作为网格简化准则,代替了原PM算法中的能量方程；选择折叠边其中的一个顶点作为边折叠后新顶点的位置,提出了一种改进的PM算法。改进后的算法不仅降低了原算法的复杂度,而且消除了累进网格的二义性。同时还对简化过程中各种可能产生的拓扑错误进行了判断并给出有效的解决方法。在算法的改进过程中还对边界边、边界点进行了合理的处理,使得算法更具有普遍性；采用最小堆进行对边折叠误差进行排序,降低了时间复杂度。最后采用太行山某区域地形数据验证了TIN地形模型生成算法的可行性和高效性,并验证了改进后的PM算法不仅效率高而且生成的简化网格质量好,为地形模型在实际中应用提供了前提。

目录

文摘

英文文摘

声明

第一章绪论

1.1研究背景

1.2国内外研究现状

1.2.1 TIN地形模型构建算法

1.2.2地形LOD模型构建算法

1.3论文研究内容及安排

1.3.1论文研究内容

1.3.2论文各章内容安排

第二章地形模型生成与简化技术的基本理论研究

2.1地形模型生成技术

2.1.1 D-TIN基础

2.1.2逐点插入法实现过程

2.2地形模型简化技术

2.2.1降低地形场景复杂度的方法

2.2.2地形LOD模型

2.2.3 PM算法的基本定义

2.2.4模型简化常用准则

2.2.5二次误差测度

2.3本章小结

第三章基于虚拟网格的高效DELAUNAY三角网生成算法研究

3.1 VG逐点插入法

3.1.1虚拟网格索引技术

3.1.2虚拟网格索引技术实现过程

3.1.3虚拟网格的划分

3.1.4离散点插入顺序的优化

3.1.5数据的存储结构

3.2 VG逐点插入算法的主要步骤

3.3算法仿真及结果

3.4时间复杂度分析

3.4.1传统算法时间复杂度的计算

3.4.2 VG逐点插入算法时间复杂度计算

3.4.3分析与结论

3.5本章小结

第四章基于PM算法的网格简化改进算法研究

4.1 PM算法实现过程描述

4.2改进的PM算法

4.2.1折叠误差的计算和新顶点的确定

4.2.2折叠误差的最小堆排序

4.2.3边界顶点、边界边的判断与处理规则

4.2.4拓扑错误的判断和处理

4.3改进算法的主要数据结构与算法实现

4.3.1改进算法的数据结构

4.3.2改进算法的实现步骤

4.4算法仿真及结果分析

4.4.1算法仿真

4.4.2实验结果分析

4.5本章小结

第五章总结与展望

5.1总结

5.2展望

参考文献

研究生在读期间取得的研究成果

致谢

个人简介