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

陈芬

摘 要：地形可视化与人类的生产生活息息相关，就是利用计算机对地形数据进行模拟仿真，并通过对相关技术的应用实现对地形模型的表达、显示以及传输。该技术涉及到测绘学、图像处理、现代数学以及计算机网络等多个学科，如今，该技术在虚拟现实、地理信息系统以及计算机仿真等领域的应用越来越广泛，是当前计算机图形学的一个重要研究课题。随着地形仿真应用要求的不断提高，地形可视化逐渐向构建三维真实感地形模型的趋势发展，而要生成三维真实感地形，就需要进行较复杂的数据计算，所以，计算机的图形处理能力非常重要。本研究就是基于数字地形模型对三维地形建模技术进行探讨，并对可以生成数字地形模型的TIN（不规则三角网模型）的改进算法进行详细分析。

关键词：三维地形；可视化；建模；算法

中图分类号：TP391.9 文献标识码：A 文章编号：2095-1302（2015）12-00-02

0 引 言

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 基本三角网的生成

首先要生成初始三角网，然后逐个插入其余点，并采用LOD对初始三角网的形成以及数据插入过程进行优化，以保证形成有效的Delaunay三角网。初始三角网的形成过程：一是根据采集的原始采样点特征构造凸壳；二建立用于逆时针存储凸壳形成过程中各个点的链表；三是 将链表中的P0点（凸壳上最小的点） 以及后续点P1、P2构成第一个三角形；四是从P2开始重复步骤三的操作，形成新的三角形，直到链表头部，整体过程采用LOD进行优化。初始三角网形成后，再逐点插入所有数据，以形成完整的Delaunay三角网。之后就可完成基本三角网的合并。

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

3.1 系统设计

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

3.2 系统设计结构

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

4 结 语

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

参考文献

[1] 贾瑞生，姜岩，孙红梅，等.三维地形建模与可视化研究[J].系统仿真学报，2006，18（z1）：330-332.

[2] 黎华，肖伟，黄海峰，等.三维真实感地形生成的关键技术研究[J].测绘科学，2006，31（4）：57-59.

[3] 闫丰亭.大规模三维地形建模与渲染的研究及改进[D].青岛：山东科技大学，2011.

[4] 漆泽军.三维地形建模与渲染的研究和实现[D].武汉：中南民族大学，2012.

[5] 文雄志.关于三维地形建模简化技术的研究与实现[J].计算机光盘软件与应用，2015（1）：7-8.

[6] 万苗，张新家，宋佳音，等.一种交互编辑与自动生成的三维地形综合构建方法与实现[J].电子设计工程，2014（23）：14-17.