虚拟现实中三维地形建模及其算法探讨

引 言

DTM（数字地形模型）的定义为“以数字形式存储的地球表面上所有信息的总和，是描述地面特征空间分布的数值的集合，是地形表面形态等多种信息的一种数字表示，是描述地形特征空间分布的有序数值阵列。”数字地形模型不仅包通过航、卫片的立体像对生成的高程数据，还包括公路、建筑物、河流等存在于地形表面的地物数据。地形可视化概念自形成以来，国内外学者就针对不同的目的对数据模型、相关算法以及理论进行不断研究，如今依托于计算机技术已经成功建立起多种可视化模型。1997 年，Mark 等人提出了 ROAM（实时优化适应网格）算法，ROAM 算法规则是对传统 LOD（层次细节技术）算法的改进，优化后的的ROAM 算法可以极大地提高地形数据的运算效率，尤其适合应用于大规模地形数据，因为它可以根据视点的位置实现对模型细节层次的动态计算。通过近年来的研究，我国学者提出一种基于地形特征和参数的地形生成方法，研究者将地形视为一个随机统计过程，并综合应用了实用回归、分形几何模型等多种技术。另外， 有学者将三角网地形生成方法与传统的分割 - 合并法融合在一起，提出了基于不规则三角网模型的自适应分块思想以及相应的地形简化过程。

1 改进的 Delaunay三角网法算法

数字地面模型从数据结构的角度可以分为 2 大类，即TIN（不规则三角网模型）和 Grid（不规则网格模型），TIN是针对离散点数据，其具有数据冗余小的优点，而且可以充分顾及到地形特征，能够将地形各种复杂的细节特征有效反映出来，但该方法的算法比较复杂，所以在实现方面存在一定难度，而且存储以及空间操作上也很不方便 ；Grid是基于规则分布数据点，该方法拓扑关系简单，算法容易实现，存储以及空间操作都非常方便，但其数据冗余较大，不能有效地对地形结构和特征进行描述。TIN是地形生成算法的基础， 本文着重讨论TIN的算法。三角网相对于TIN 和 Grid算法比较简单，而且图形灵活多变，改进的Delaunay三角网法可以有效提高 TIN的建网效率，下面就对Delaunay的改进算法的相关研究。

利用数据分块建网再合并技术对Delaunay 算法进行优化处理，因为 Delaunay 算法的原则同样适用于TIN 建网和合并， 所以基于该方法的建网效率与采样点增长呈线性递减分布，使得Delaunay 三角网的生成速度得到大幅度提高。Delaunay 改进算法处理过程如下：

2 处理原始数据（切分采样点）

图 1所示是采用数据切分的过程图，图中的“A为原始采样点。首先对原始采样点 A插入二叉树根节点，并根据采样点的地理位置置入叶子节点，如果叶子节点中采样点的最终数量大于三角网采样点的最大允许数量值，将该叶子节点作成根节点形成两个叶子节点，此时形成了两部分数据，实现了区域二分，反复进行此操作模式直到数据插入完毕”。图 1中采样点处理完毕后一共形成 4个三角网，各个三角网的合并好结合其在二叉树中的位置进行， 其中有父节点相同时先合并。图 1中 11由110和 111 合并而成，1由10和 11合并而成，完整的Delaunay 三角网最终由1 和 0 合成。

3 基本三角网的生成

3 三维地形可视化系统的实现 

3.1 系统设计 

地形表面网格模型的构建根据 DEM 数字高程模型，以 实现三维地形可视化系统的设计，并利用光照、立体视觉技术 以及纹理映射等实现地形地貌的真实再现。三维地形建模的 流程如下图 2 所示。 

3.2 系统设计结构 

本 研 究 的 基 础 设 施 为 Windows XP 操 作 系 统 以 及 VC++6.0、OpenGL，基于以上系统和软件进行开发，三维地 形可视化系统用到的关键数据结构可根据三角形面片使用单 链表形式定义，代码如下：（来自 DEM 文件的数据多通过面 向对象方法设计出的 Cterrain 类来处理，这里不再详细介绍）。

4 结 语

采用逐点插入的方法对 Delaunay 进行三角划分是三维地 形显示中非常重要的环节，在原有 Delaunay 算法基础上采用 采样数据分块建网，然后对基本三角网进行合并，这一方法极 大的提高的 Delaunay 三角网的生产速度。