三维地形数字板块结构法

摘要

虚拟现实是发展到一定水平上的计算机技术与思维科学相结合的产物，它的出现为人类认识和改造世界开辟了一条新的途径。虚拟现实技术以其实时三维空间表现能力、人机交互式的操作环境以及给人带来的身临其境感受，使得人们越来越认识到它的重要作用。虚拟现实技术将使众多传统行业和产业发生革命性的转变。
　　虚拟现实中，三维地形具有广泛而重要的地位。超大范围的三维地形的建模及其快速显示是计算机图形学领域中的一个重要课题。近年来，以智能手机为代表的移动通信终端迅速发展并普及，专家预测，在不久的将来，人类社会将进入智能手机的时代。因此，在目前的条件下，如何实现超大范围的三维地形在计算和存储能力不强的智能手机平台上快速显示，为该领域的研究又提出了新的挑战。面对着能力差距很大的各种硬件水平的设备，研究人员不能仅仅停留在单纯地对某一平台上的技术细节的追求，同时还应该注重其宏观的兼容性，只有对相关技术与应用的最终平台进行深入的了解，才能更好地解决问题。快速显示超大规模的地形主要存在两个问题，一是需要实时地对海量的数据进行处理;二是需要为海量的数据提供足够的存储空间。面向于智能手机平台，开展三维地形数字板块结构法的研究，减少地形数据的处理量，降低地形数据的空间占用，具有十分重要的意义。
　　本文首先介绍了三维地形模型的三种构造方法，包括分形地形生成法、基于Perlin噪声生成法和DEM模型法。其中，分形地形生成法和基于Perlin噪声生成法生成的地形更加接近真实的自然地形，但由于计算复杂，较少使用。DEM模型计算简单，能够近似地反映出自然地形，是目前用于构建三维地形的主要方法，本文主要以DEM模型为研究对象。
　　与普通的PC计算机相比，智能手机具有体积小、方便携带的优点。同时，也存在明显的缺点，比如计算和存储能力较弱，需要蓄电池提供能量等。因此，要想在智能手机平台上流畅地显示三维地形，必须尽可能地降低计算强度和需要保存的地形数据。由此本文提出了一种三维地形板块结构法，以降低计算复杂度和减少存储空间的占用。
　　由于三维地形是根据DEM图构建的，所以超大规模的三维地形的DEM图是巨大的。本文将超大的DEM图分块成若干个DEM分图，由DEM分图构建出地形板块(Plate)，先后提出了狭义的地形板块模型和广义的地形板块模型。通过板块的拼接，再现出原地形的部分或全部。考虑到视野范围的因素，显示地形的时候，只构建必要的地形板块即可。相对于原始的超大地形，处理板块地形的计算复杂度和存储空间占用要小得多。
　　由于整个地形由地形板块拼接构成，那么就需要解决板块之间的实时、无缝显示的问题。本文先后提出了九宫模型、即插即用模型和嵌入式模型。定义了地形结构表达式的概念，不同模型结构的地形能够通过地形结构表达式抽象地表示。通过实验，这三种模型能够完成地形无缝显示的任务。
　　采用板块地形拼接的方式，使得智能手机的CPU在运行程序的时候，需要处理的数据量大大减少，为了能够比较流畅地显示地形，必须对板块地形进行LOD处理。现有的ROAM算法和GeoMipMap算法可以很好地完成这个任务。但是，由于这些算法需要CPU实时不断地进行LOD计算，会产生较大的功耗，对于使用蓄电池的手机来说，会造成缩短待机时间，对用户的工作和生活带来不便。所以，这些算法不适合直接使用在手机平台上。本文在GeoMipMap模型的基础上，提出了一种完全静态的GrayScale模型，并给出了相关的算法。该模型将LOD信息保存在一张GrayScale中，并对GrayScale的存储方式进行了优化。使用GrayScale可以进一步降低手机CPU的计算强度。

目录

声明

摘要

第1章 绪论

1．1 研究背景

1．2 研究的现状

1．3 本文研究内容

1．4 本文的组织结构

第2章 三维地形建模及快速显示方法综述

2．1 三维地形建模方法

2．1．1 分形地形方法

2．1．2 Perlin噪声生成地形数据

2．1．3 DEM模型

2．2 大地形快速显示方法

2．2．1 地形的创建

2．2．2 地形的渲染

2．2．3 不可见剔除

2．2．4 LOD模型

2．3 本章小结

第3章 狭义的地形板块模型

3．1 DEM分图

3．2 DEM分图尺寸

3．2．1 匀速运动

3．2．2 变速运动

3．3 引入基准值

3．4 SRTM数据

3．5 复杂度分析

3．5．1 时间复杂度

3．5．2 空间复杂度

3．6 实验结果及数据

3．6．1 开发环境搭建

3．6．2 实验结果

3．7 存在的问题

3．8 本章小结

第4章 广义的地形板块模型

4．1 板块拓扑

4．2 二维螺旋数组

4．2．1 海龟算法

4．2．2 分割算法

4．2．3 递归算法

4．2．4 非对称周期律算法

4．2．5 四种算法复杂度对比

4．2．6 小结

4．3 索引位图模型

4．3．1 模型结构

4．3．2 解决方案

4．3．3 小结

4．4 动态Zone模型

4．5 复杂度分析

4．5．1 广义的地形板块模型的复杂度分析

4．5．2 动态Zone模型的复杂度分析

4．6 本章小结

第5章 板块间无缝显示的研究

5．1 九宫模型及其算法

5．1．1 指导思想

5．1．2 解决方案

5．1．3 复杂度分析

5．1．4 地形结构表达式

5．1．5 小结

5．2 即插即用模型及其算法

5．2．1 指导思想

5．2．2 解决方案

5．2．3 优化方案

5．2．4 复杂度分析

5．2．5 地形结构表达式

5．2．6 小结

5．3 嵌入式模型及其算法

5．3．1 指导思想

5．3．2 解决方案

5．3．3 复杂度分析

5．3．4 地形结构表达式

5．4 实验结果及数据

5．5 本章小结

第6章 板块内快速渲染的研究

6．1 ROAM算法简介

6．1．1 地形的二叉树结构

6．1．2 消除裂缝

6．1．3 几何误差描述

6．1．4 分裂合并

6．1．5 存在的问题

6．2 GeoMipMap算法简介

6．2．1 MIPmap

6．2．2 地形结构

6．2．3 评价系统

6．2．4 裂缝消除

6．2．5 存在的问题

6．3 GrayScale模型及其算法

6．3．1 静态LOD地形结构

6．3．2 GrayScale模型

6．3．3 评价系统

6．3．4 裂缝消除

6．3．5 地形消隐

6．3．6 模型优化

6．3．7 试验结果及数据

6．4 本章小结

第7章 结论

7．1 工作总结

7．2 主要贡献

7．3 下一步工作

参考文献

致谢

攻读博士期间发表的论著