TIN数字地形模型的通视性算法

1、TIN数字地形模型的通视性算法第27卷第5期2005年1O月情报指挥控制系统与仿真技术InformationCommandControlSystem&SimulationTechnologyVo1.27No.5Oct.20()5文章编号:1672-7908(2005)05.0091.05TIN数字地形模型的通视性算法王智杰(白城兵器试验中心,吉林白城l37001)摘要:数字地形模型的地形通视性分析有着广泛的应用,对TIN地形模型上两点问的通视性算法进行了研究,改良与实现.研究结果说明,视线与三角形相交法算法简单直观,但计算效率太低;改良的视线与边相交法数据结构简单,编程实现容易

2、,适合地形数据结构单一的系统;而投影覆盖检测算法通用性好,适合地形数据结构多样的系统.关键词:通视性;数字地形模型;不规那么三角网;视线;视点;目标点中图分类号:0241文献标识码:AInterVisibilityAlgorithmsOnTINDigita1TerrainModelWANGZhi-jie(BaichengOrdnanceTestCenteabaseformat.TheSOalgorithmhasgoodgeneralization,anditCanbeappliedtothesystemsofmixedterraindatab?aseformats.Keywords:inter

3、visibility;digitalterrainmodel;TIN;lineofsight;viewpoint;targetpoint基于数字地形模型的地形通视性分析广泛应用于建模与仿真,地形勘探,制导导航,测量测绘,游戏娱乐及地理信息系统等多个领域.例如,依据适当约束条件进行观察点的设置,地面测控点的选取,地面通信中继站的定位,具有指定特征(如最大隐蔽性)的路径规划,作战指挥中的兵力配置,火力点的选取,雷达位置确实定,三维游戏中的视线判定等都要进行通视性判断,特别是仿真系统中计算机生成兵力的决策制定在很大程度上依赖于通视性的计算.,在各种应用中,地形上两点之间的通视性计算是最根本,最常见的

4、问题.虽然通视性的概念简单,但是它在计算机生成兵力仿真系统中却是非常花费计算时间的环节,严重的影响着仿真的实时性和仿真规模的扩大.1通视性模型1.1数字地形模型自然地形在数学上建模为三维空间的连续表面,可以用平面内连通域上的一个二变量实值连续函数z=妒(,y)来表示,这是对地形进行了简化收稿日期:2005-01.13作者简介:王智杰(1972.),男,内蒙古赤峰人,硕士,程师,主要研究方向为系统仿真,环境建模.的理想数学地形模型,在这种理想情况下地形被定义为M兰(,).在实际情况下,由于地形的复杂性,就需要对区域进行分割,应用数字地形模型提供一种地形的离散近似表示.基于地形外表的有限采样数据点

5、序列,定义数字地形模型为D兰(,),其中是以点序列(,Y)I(X,Y,z)Sl作顶点的平面连通域的一种分割,是一个二变量连续函数族,每一个函数定义在一个闭区域R上,任一点(五y)Ri处的地形高程可以通过对离散分割点上的高程进行插值得到,且一般对于任意(X,y)RfnR,都假设有妒f(,Y)=ej(,Y),这就是数字地形模型.构建数字地形模型的点序列既可以是规那么的又可以是不规那么的采样点,根据分割方法的不同可以将数字地形模型主要分为规那么方形格网(RegularSquareGrid,RSG)地形模型和不规那么三角网(TriangulatedIrregularNetwork,TIN)地形模型.本

6、文研究在TIN地形模型上两点间的通视性算法.1.2TIN数字地形模型的结构TIN数字地形模型用三角形来分割地形区域,是一种多面体地形模型,如图1所示.TIN是根据区域有限个点集,将区域划分为相连的三角面,92王智杰:TIN数字地形模型的通视性算法第27卷构造出邻接三角形组成的格网型结构,区域中任意点落在三角面的顶点,边或三角形内.如果点不在顶点上,该点的高程值通常通过线性插值的方法得到.TIN的每个根本单元的核心是组成不规那么三角形的三个顶点的三维坐标.<图1TIN地形模型1.3通视性概念在仿真中,通视性指的是对这样一个简单问题的答复:给定两个仿真对象,它们能够看到对方吗?为了答

7、复这个问题,就必须确定连接这两个对象的视线是否跟地形相交.给定一个地形模型M兰(R,)和地形上的两个点与P2,如果对于直线段P2上的任一点Q兰(X,Y,z)都有z>妒(,Y),那么与P2是可以通视的.2通视性算法2.1视线与三角形相交法在三维空间中,可以将TIN数字地形视为由诸多三角形组成的三维曲面,如果视点到目标点的连接直线与其中一个三角形平面相交,并且交点位于该三角形内,那么表示该视线被遮挡,视点与目标点不能通视.如果直线与每一个三角形平面无交点或交点不在任意一个三角形内,那么表示此视线没有被遮挡,视点与目标点之间可以通视,如图2所示.图2视线与三角形相交法(V为视点,T为目

8、标点,D为视线与三角面交点)由此可得N-一种最简单的通视性算法:视线与TIN地形上所有的三角形都进行一次相交运算,以判断是否有三角形遮挡住目标点.如果存在一个三角形能够遮挡住目标点丁,那么目标点丁与视点之间是不能通视的;如果所有的三角形都不能遮挡住目标点丁,那么说明目标点与视点之间是可以通视的.2.2视线与边相交法及改良给定一个TIN数字地形D兰(,),在D上有视点,和目标点,计算与之间的通视性,可以不计算视线与地形三角形的交点,而是计算视线耋FT在XY平面上的投影(记为)与边的交点.在与的每一条边e的交点P处,检验是否位于D相应于边e的地形上面.如果在所有这样的交点处视线都在相应的地形上面,

9、那么视点和目标点是可以通视的,如图3所示.图3视线与边相交法(V为视点,丁为目标点,为视线与边的交点)视线与边相交的简单算法要对地形中的所有三角形边都计算与视线投影的交点,并进行交点检验.但实际上,从图3中可以看出,如果计算交点前可以预先判断出哪些边需要计算与视线的交点,或者在计算过程中选择推进方向,只计算那些有效的交点,即可大大减少通视性判断时间.本文没有对简单的视线与边相交法进行实现,而是对其改良后再实现.设计过程中,根据TIN中三角形间的拓扑关系,由视点至目标点进行视线与边交点的判断,减少检验交点的三角形边数量,从而提高计算效率.2.3投影覆盖检测算法前面两种通视性算法以及目前在各种系统

10、中所用的绝大局部通视性算法,尽管在细节方面不同,但是在概念上有相当大的共性.算法根本包括4个步骤:首先将地形三角形库中的三角形和视线段投影到水平面上(设为XY平面);其次和J用点定位程序找到包含视线端点投影的两个地形投影三角形;再次根据投影三角形的邻接关系在xY平面找到视线投影穿过的所有置角形;最后,沿着视线穿越地形数据库,并依次检验穿过的每一个三角形同视线的交点,判断出视线与三角形在维空间中是否真正相交.这一类通视性算法称为传统穿越算法.由于传统穿越通视性算法在穿越过程中用地形数据库的数据结构来从一个角形到下一个角形第5期情报指挥控制系统与仿真技术进行连接,这些算法就在很大程度上依赖于执行它

11、们所用的地形数据库的特定数据结构细节.这些数据库特性并不具有可移植性,因此,通视性算法必须对每一种地形数据库格式都重新实现或修正.当大规模仿真中不同的仿真实体用不同的通视性算法时,多算法就可能导致通视性确定的不一致.至于计算效率问题,实际上,由于视线与三角形的求交检测是在j三维空间进行的,所以很费时间.一些主要的改良工作集中在对地形三角形的组织上,通过构建一个复杂的地形三角形组织结构,提高求交及判断的效率,减少判断时间.在这些改良算法中,投影覆盖检测(SieveOverlap,简记为SO)算法提出了一种通用的地形三角形组织方法,并且具有很高的检测效率,比拟有效地解决了已有的点到点通视性检查算法

12、的一些问题.2.3.1SO通视性算法的概念SO通视性算法是通过减少判断三角形与视线交点次数的方法来提高通视性查询速度的,它利用一个包含视线段,且各边与坐标轴平行的最小包围盒,该包围盒称作过滤筛(Sieve).假设把视线投影到3个坐标轴上,那么分别在轴上有3个线段,Sieve实际上是定义了这3个线段;相应的地形三角形也可以投影到3个坐标轴上,产生3个线段.该算法的前提是这样一个事实:仅当地形三角形投影的3个线段与Sieve投影的3个线段都有重叠时,此地形三角形才可能与视线相交.SO算法有效的选择在三个坐标轴上与Sieve投影线段都有重叠的地形三角形系列,然后对此系列进行三角形与视线相交检验.2.

13、3.2?数据结构.SO算法首先要建立一个通用的地形三角形组织结构,这一结构使用了两个主要的数据结构,一个称为单线索三叉树,另一个称为桶表.2.3.2.1单线索三叉树单线索三叉树是一个类似于二叉检索树的结构.每个结点包含1个键值和3个指针,指针分别指向比其键值小的结点,比其键值大的结点和与其键值相同的结点.这个树在结点插入和检索时具有较高的效率.当一个新数据元素插入一个单线索三叉树时,它的键值与当前结点的键值进行比拟,这种比拟从根结点开始.如果新元素的键值小于当前结点的键值,这个新元素就插入到当前结点的左子树;如果新元素的键值大于当前结点的键值,这个新元素就插入到当前结点的右子树;而当一个要插入

14、的数据元素有一个等于当前结点键值的键值时,它就沿着相等链插入到相等子树中.这个相等子树将包括有相等键值的全部结点,因此在每一个结点处保存一个附加的指针来指向其等子树的最后一个结点,不要求查询程序搜索整个等子树,新结点就可以立即插入到等子树底部.在单线索三叉树中,树结构链附加有指针,称为线索,它以升序键序列连接树的结点.通过从一个与每棵树相关联的特定首指针开始,从结点到结点沿着线索,就可以按升序键序列遍历树的所有结点.2.3.2.2桶表桶表是SO算法中另一个主要数据结构,每个桶表中存放了按键值排序的数组,桶表中包含有假设干的桶,每一个桶中存储键值落在一个指定范围内的数据元素;那些构成一个桶表的桶

15、对可能的键值范围进行分割,因此每一个数据元素将按照其键值正确地存储在一个桶中.每一个桶又是某种其他的数据结构,因此到一个桶表中的一个插入分两步:首先,按照其键值确定拥有这个数据元素的桶;其次,将此数据元素插入桶的数据结构中,在本算法中,这个数据结构就是单线索三又树.在桶表结构中有一个桶头,桶头包含桶边界值,它规定了桶的键值范围.如果桶t有边界bi,而桶tf-l有边界bf-l,那么桶tf包含那些键值在bi_l,bil】范围内的数据元素.2.3.3算法描述SO算法如下:预先构建三个桶表,其中每个坐标轴一个桶表,每一个桶表都用来存储地形数据库三角形沿着一个轴的三角形线段,而桶表中的每一个桶又是一棵单

16、线索三叉树.这种桶表结构可以有效地选择在那个轴上的三角形投影线段与Sieve线段重叠的三角形.在通视性确定过程中,此算法首先访问为z轴预构建的桶表来选择在z方向三角形线段与Sieve线段重叠的地形三角形.找到这些_角形之后,将所选定三角形的x线段插入到一个Workingx桶表中.它只包含那些在z轴上选定了的i角形的x线段,并且为在x轴上直接访问它们来进行组织.Workingx桶表被输入到x选择阶段,类似地产生一个只包含那些在z和x上都重叠的_角形的WorkingY桶表.它们在第j个选择阶段中在Y上进行重叠试验,从这一步中选择的三角形在94王智杰:TIN数字地形模型的通视性算法第27卷所有三个坐

17、标轴上都与Sieve线段重叠.最后将这些选出的三角形用三角形与线段相交检测程序进行相交性检测.图4显示了SO算法的整个流程.交点检测阶段重叠结果图4SO算法流程2.3.4算法设计说明选择阶段轴的顺序(z,X,Y)是基于直觉,直觉认为通过去掉那些在视线之上和视线之下的地形三角形可以在处理过程中最早地区去掉最大数量的三角形.在程序设计过程中此选择顺序作为一个参数,因此可以很容易按照某种其他的启发式规那么进行修改,诸如基于Sieve线段的长度(如,从最短到最长)来排序轴的选择顺序,这就是为什么尽管在算法执行过程中从未用到X轴和Y轴的TDB桶表,却也生成它们的原因.另外,在算法执行过程中桶表内桶的数量

18、和桶的边界值也是参数,并且可以在不对算法本身进行修改的情况下改变它们.对不同的地形数据库,这些参数可以选择不同的值来进行优化.除计算效率较高以外,SO算法的另外一个好处就是一旦在预处理过程中构建了三个TDB桶表,SO算法就只访问这些结构,从本质上独立于地形数据库格式.因此,任何TIN地形数据库格式都可以由此算法进行处理,任何可以导出三角形格式的地形数据库也可以通过在预处理过程中生成三角形来由SO算法进行处理.SO通视性算法独立于任何特定地形数据库格式的特性就使得它可以应用于不同仿真的不同地形数据库格式,这种单一通视性算法的应用就促进了算法和代码的重用,并且可以消除仿真系统间误差的一个来源.3各

19、种通视性算法比拟本文采用PORTLAND附近边长为99km的真实地形数据,对各种通视性算法进行比拟分析,对不同算法进行了大量的试验.例如,取120000个视点与目标点对,这些点在地形上的位置是随机的,它们在地形之上的高度是0100米之间的随机值,计算这些点之间的两两通视性.计算结果见表1,表中时间为120000个点对的总计算时间,单位为s(简记:视线与三角形相交法为算法一,改良的视线与边相交法为算法二,投影覆盖检测算法为算法三).表1120000对点的通视性计算结果比拟再如,取3000个视点与目标点对,这些点在地形上的位置也是随机的,它们在地形之上的高度是080米之间的随机值,计算结果比拟见表

20、2.表23000对点的通视性计算结果比拟选舞阶段第5期情报指挥控制系统与仿真技术95下面对计算结果进行分析,从算法本身来看,此三种算法都是精确的计算方法,因为如果认为数字地形是精确的,本文中所介绍的三种算法并未对通视性问题进行近似,它们或者判断视线与地形三角形的交点,或者判断视线与三角形边的交点,其效果应该是相同的,所以理论上三种算法的计算结果也应该是相同的.但从实际计算结果来看,采用视线与三角形边交点进行判断的算法二同采用视线与三角形交点进行判断的算法一和算法三的计算结果是有一点差异的.这些算法间的结果差异完全是由于计算机误差所造成的,最主要的误差出现在判断视线与平面交点是否在三角形内时,由

21、于计算机字长的限制对非常靠近三角形边的交点的判断就不一定准确.至于计算效率问题,很显然算法一的效率是很低的,它所用计算时间比其他两种算法要高出一个量级;算法二和算法三的计算效率相差不多,但是算法二实现容易,而算法三通用性好,所以实际应用过程中要根据它们各自特点决定选择哪种算法.从表1中还看得出,算法三中改变桶的数量这个参数,可以优化计算,提高效率.4结束语由于TIN数字地形模型能够较好地适应不规那么地形区域并防止地形平坦时的数据冗余,所以得到了越来越广泛的应用,本文就对TIN地形模型上的通视性算法进行了研究,改良与实现.研究结果说明,视线与三角形相交法的计算效率太低,所以根本上不适合真实系统的

22、需要;改良了的视线与边相交法数据结构简单,编程实现起来也比拟容易,所以对于地形数据结构单一的系统推荐使用它;而SO算法数据结构比拟复杂,但是通用性好,所以对地形数据结构多样的系统优先考虑它.参考文献:【l】L.DeFloriani,P.Magillo,lntervisibilityonTerrains,Chapter38inGeographicInformationSystems:Principles,Techniques,ManagamentandApplications,P.A.Longley,M.F,Goodchild,D.J.Maguire,D.W.Rhind(Editors),JohnWiley&sons.1999.【2】LDeFloriani,P.Magillo,VisibilityAlgorithmsonTriangulatedDigitalTerrainModels,InternationalJournalofGeographicInformationSystems.Vo1.8.N.1,TaylorandFrancis.London,1994.