基于TIN模型的三维地形模拟研究

2012-09-06 00:54钱锋屠彦钧
城市建设理论研究 2012年22期
关键词:算法

钱锋 屠彦钧

【摘要】:三维地形模拟一直是虚拟现实、地理信息系统(GIS)等领域的研究热点。它是一种表示三维空间连续起伏的数学模型,是从已知三维坐标的离散点出发,构筑地形表面,以数字的形式表示实际地形特征的空间分布,本文探讨采用TIN技术来实现不规则三角网的建立。

【关键词】:不规则三角网(TIN)、Delaunay三角网、算法

【Abstract】: 3D topography simulation is a hot research field of virtual reality, geographic information systems (GIS). It is a representation of the continuous ups and downs of three-dimensional mathematical model, starting from the known 3D coordinates of discrete points to build a terrain surface, the spatial distribution of the actual terrain features in digital form,This text will adopt TIN technology to realize the setting-up of the irregular triangular network .

【Keyword】: Triangulated irregular network (TIN ) , Delaunay triangular network , algorithm

中图分类号:O343.2文献标识码:A 文章编号:

一、引言

随着计算机技术、计算机辅助设计、信息技术及相关学科的不断发展和数字化概念在测绘中的应用不断深入,以“3S” 、“4D” 为主要生产手段的测绘业已成为新兴的信息产业,并且日益得到了社会各方面的重视,数字高程模型DEM已经成为地理空间基础设施和“数字地球”的重要组成部分。 通过计算机采用一定的算法,能够方便地将DEM数据转换成为等高线、三维立体景观图、晕渲图、坡度图、断面图及数字正射影像图复合成景观图等各种专题图产品。正因为有如此广泛的用途,研究、建立DEM仍然是目前十分热门的课题。

二、数字高程模型建立方法比较

DEM有很多种表示形式,其中主要的有规则格网模型(Grid)、等高线和不规则三角网模型(TIN)。但这三种不同数据结构的DEM表征方式在数据存储及空间关系等方面,则各有优劣,见表1:

表1 不同数据结构数字高程模型的比较

等高线 规则格网 不规则三角网

存储空间 很小(相对坐标) 依赖格距大小 大(绝对坐标)

数据来源 地形图数字化 原始数据插值 离散点构网

拓扑关系 不好 好 很好

任意点内插效果 不直接且内插时间长 直接内插且时间短 直接内插且时间短

适合地形 简单、平缓变换 简单、平缓变换 任意、复杂地形

从表1中可以看出,虽然TIN在存储空间的要求上相对较高,但在处理任意复杂的地形上具有绝对的优势,而且研究也表明,在所有可能的TIN中,只有D-TIN(简称D-TIN)表现最为出色。因此,在很多DEM都是以不规则三角网模型来建立的。而生成DEM的数据通常是以离散数据点(即野外实测的所有地形特征点)为主,对于离散数据点转换为TIN,主要采用Delaunay三角网法来实现。

三、 TIN的构建与算法

1、TIN的概念

TIN(不规则三角形格网),是直接利用测区内野外实测的所有地形特征点(离散数据点)构造出邻接三角形组成的格网型结构。TIN的每个基本单元的核心是组成不规则三角形的三个顶点的三维坐标,这些坐标数据完全来自于原始测量成果。由于观测采样时选取观测点是由地形决定的,一般是地形坡度的变换点或平面位置的转折点,从而使得离散点在相关区域内非规则和非均匀分布。由这些点构成的三角形格网所包含的三角形必然是形状不规则的三角形,网格中三角形的数目只有在格网形成后才能确定。但根据计算几何学,如果区域中有n个离散点,它们可以构成的互不交叉的三角形的数目最多不超过2n-5。

2、TIN的数据结构

TIN的数据表达复杂地形数据的灵活性决定了它在数据组织上的复杂性。它是由两个基本元素组成:(1)有X、Y、Z值得点;(2)连接点形成的三角形的一组边。即要建立不规则三角网数字高程模型,首先就要存贮每个点X、Y、Z的值,然后要存贮网点连接的拓扑关系,三角形及邻接三角形等信息。TIN结点坐标的数据结构如图2-1所示,数据结构中仅使用了点号,根据点号在数据文件中查找坐标。数据结构的核心分别是坐标数组和三角形数组,结点用其在坐标数组中的存储位置(或称下标)作为点号,三角形用其在三角形数组中的存储位置作为三角形号。

坐标数组

图1 TIN结点坐标的数据结构

3、D-TIN的局部优化

二维三角剖分的优化原则有很多种,比较常用的有最大--最小距离原则、圆原则、最大—最小内角原则、最大—最小高原则、Thiessen原则等(姜寺山等,1995)。这些原则归纳起来,无非是要求经过剖分形成的三角网(TIN)要满足Delaunay三角网的特性,即唯一性、最大最小角特性和空圆特性。而研究表明,在所有可能的TIN中,只有Delaunay三角网(即D-TIN)在满足上述要求时表现最出色。

4、Delaunay生长算法

三角网生长算法的基本过程是将最邻近的三个离散点连接成初始三角形,再以这个三角形的每一条边为基础连接邻近离散点,组成新的三角形。新三角形的边又成为连接其它离散点的基础,如此继续下去,直到所有的三角形的边都无法再扩展成新的三角形,而且所有离散点都包含在三角形中。

设平面上有几个离散点,我们希望将其中最靠近的三点构成三角形,从而形成三角网。在联结三角网时,要求建立在可能获得最佳三角形的条件下。这个条件就是在使用周围邻近的离散点所组成三角形网时,应尽可能地确保每个三角形都是锐角三角形或三边的长度近似相等,避免出现过大的钝角和过小的锐角。

四、三维地面模拟实现

三维地形的模拟是开发可视化系统中最基本也是最重要的技术之一。地形的模拟可以分为两类:真实地形与模拟地形。对于真实地形的构造,通常采用经纬度线构成的规格化网格体逼近的方法实现。而对于一般的非真实地形的模拟,采用的方法有随机高程数据生成和分形高程数据生成等。本文所要实现的真实感地形模拟程序便是基于OpenGL,运用Visual Basic语言实现。

1、地面模型的建立

如图2所示,P1P2P3P4 为一空间四边形,首先对 P1P2P3P4上每条线段的中点产生扰动点P12、P13、P14、P11,再对线段Pm1Pm2和Pn1Pn2使用同样的过程以生成它们的扰动点,这两个扰动点的中点P0便是细分后四个空间小四边形的公共点。四个小四边形为P1P12P0P11、P12P2P13P0、P13P3P14P0、P14P4P11P0,然后再对这四个小四边形运用同样的方法进行细分,这种细分过程一直进行到满足一定的深度为止。

图2 中点位移法地形建模

2、投影变换

在对物体进行坐标变换时,可以使用平移、旋转、缩放等各种数学变换,完成对模型各个顶点的坐标变换即整个模型的坐标变换,从而实现从物体空间坐标系到视点坐标系的变换。

完成了坐标系的变换之后,接着进行投影变换,分为平行投影和透视投影两种。而平行投影又分为正平行投影和斜平行投影;两者的区别在于正平行投影的投影方向是垂直于投影平面,斜平行投影的投影方向则与投影平面不垂直。在三维地面模拟中通常都是采用透视投影的。

3、颜色和光照模型

在上述地形建模的基础上,为了更加真实地模拟现实世界中的地形地貌,还需要通过OpenGL中的消隐、设置光照模型和颜色模型等来模拟出具有初步真实感的地形。

总的来说,应用OpenGL来绘制三维地形具有图形质量高、程序可移植性好等优点。如图3便是本文试图采用OpenGL绘制真实感三维地形的基本框架:

图3 基于OpenGL的地形绘制基本框架

五、 结论

本文提出的基于TIN的三维地形模拟研究,从理论到实践进行了探索,提出了一套可行的方案,实践表明,本方法理论成熟,实践效率高,相信对今后的研究能起到好的引导作用。

参考文献

[1] 汪志明,花向红,晁怡. DEM建模方案分析.东北测绘,2002(3):15-17

[2] 郝海森,吴力新. 基于Delaunay—TIN的三维地学模拟与可视化. 地理与地理信息科学,2003(3):15-19

[3] 周雪梅,杜世培. GIS中三维可视化模型构造及算法设计研究. 贵州工业大学学报,2003(4):55-58

[4] 和平鸽工作室. OpenGL三维图形系统开发与实用技术(基础编程篇). 清华大学出版社,重庆大学出版社,2003

[5] 程效军,孙晋岳. 基于凸壳的TIN建立技术. 东北测绘,2001(1):6-9

[6] 赵文芳. 离散点集Delaunay三角网生成算法与软件开发. 测绘工程,2003(4):22-25

注:文章内所有公式及图表请用PDF形式查看。

猜你喜欢
算法
国际主流轧差算法介绍:以CHIPS的BRA算法为例
利用数形结合明晰算理
《算法》专题训练
例说算法初步中常见的易错点
清华大学开源迁移学习算法库
Travellng thg World Full—time for Rree
算法框图型扫描
《漫画算法:小灰的算法之旅》
学习算法的“三种境界”
算法框图的补全