临近空间平台下地形四又树优化分割算法.doc

《临近空间平台下地形四又树优化分割算法.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、临近空间平台下地形四又树优化分割算法　　摘要：提出一种利用四叉树算法生成临近空间平台下动态地形的新方法，并提出了一种新的四叉树递归分割算法的实时优化算法，利用可见性剔除的简化策略和数据简化的存储方式，解决地形绘制的裂缝问题。通过对该算法的实现和优化，在保证一定地形环境的视觉真实程度前提下，达到提高实时渲染速度的目的。实验结果表明：采用本文提出的四叉树算法可以快速对地形数据进行网格剖分，且可得到较好的剖分效果。　　关键词：临近空间；四叉树；地形绘制；网格剖分　　中图分类号：TP79　　文献标志码：A　　文章编号：lOO5-2

2、61501-0059-05　　临近空间，又称近空间，指20--100km的高空，这个定义是以战略意义和实用角度为出发点，而不是直接由特性得出，所以研究临近空间，应该从实际要求出发，指明具体研究哪部分空间。现存的作战空间包括深海/浅海/水面/陆地/空中/地球轨道，临近空间的补入填补了空天联合作战的空白区域，与空天信息均能产生良好互动，具有重大的战略意义。而对平台所得到的系列图像进行三维重建，则可以结合目标检测等技术对战场指挥、情报侦察予以有效反馈。　　本文讨论的三维重建属于表面重建，不需要获取目标的内部结构细节。三维重建中最

3、常用的方法为网格剖分，网格剖分中最常用的算法为三角化算法。三角化算法虽然很多，但大多算法生成的足Delaunay三角网格，即以空外接圆准则为优化准则。经典的Dclaunay网格剖分算法有Bowycr算法，Watson算法，Bowycr-Watson的联合划分算法等。为了克服有时不能准确表示地形的结构与细节特征的缺点，可通过附加地形特征数据，如地形特征点、山脊线、山谷线等，提高局部细节，从而构成完整的地形地物数据模型。本文采用的网格剖分方法正是基于这种思想，利用Delaunay三角剖分和规则网格剖分相结合的方式建立地形地物模

4、型.进而更好地表现目标及场景的特征。　　四叉树网格兼具结构网格和非结构网格的特性.一方面具有结构网格的正交性特点，另一方面具有非结构网格的灵活性特点，便于网格的自适应化，进而方便处理复杂的边界问题。本文提出的新的四叉树算法得到的三维真实感地形不仅形状各异，而且实时动态变化。不必进行大量数据处理和附加计算.用少量的数据即可得到复杂的地形数据的逼真图像。　　1基于四叉树的动态地形生成算法　　1.1四叉树算法　　树形结构是一种非线性结构，它在查找算法中有独特的优势。若将采样数据以某种形式划分，形成四叉树，缩小查找区域，减小查找数

5、据量，将会提高查找效率。　　建立采样数据四叉树结构的基本思想是：首先确定阈值，检查区域内采样数据个数是否超过阈值；若超过，则将该区域四等分，然后对4个子分区进行同样的处理，直到所有子分区内的采样数据个数均不超过阈值为止。具体操作为：设nq为预先给定的阈值，若采样区域内采样数据个数n>nq，则将该区域四等分，得到4个子区。若4个子区中存在大于nq，的子区，则再将其四等分，直到所有子区的采样数据个数小于nq为止，由此得到的树即为采样数据的四叉树结构。在此四叉树中，只有叶子结点含有采样数据。　　在采样区域内随机分布着一系列采样数

6、据点，当取nq=10时，其采样数据的划分如图1所示。图2为图1中采样数据的四叉树表示，“○”为四叉树结点，“□”表示对应结点所含的采样数据。在子区内，由于数据量已控制在阈值范围内，冈此为简便起见，一般以线性链表存放。　　地形绘制是四叉树算法的核心，用来完成三角形网格的所有绘制，算法流程如图3所示。　　1.2改进的四叉树算法　　Ulrich提出了一种层次细节算法，该算法目的是在现代图形硬件上高效地渲染海量地形数据。本文算法借鉴了Geomipmap的一些思想，但做了较大的改进。该算法基于四叉树结构。四叉树的每个节点覆盖某一块区

7、域，形成一个连续继承的关系。根节点有一个最低分辨率的多边形网格覆盖整个地形，其4个子节点分别覆盖1/4地形，但分辨率更高。地形递归细分，直到得到原始分辨率的地形。　　地形数据多边形网格存储在四叉树的每个子节点，称之为“地形块”。每个地形块与其他地形块的关系相互独立。图4是一个三层四叉树地形块的示意图，分别代表父节点、4个子节点、16个孙子节点。　　每个节点即地形块有一个最大几何误差。与Geomipmap一样，几何误差就是当前数据与原始数据在物方空间的最大背离。当地形块被构建时，它们的误差值随着每一层的细分而减半。例如一个节

8、点有误差值16，则其子节点误差值为8，其他层次1，点误差以此类推。　　要选择合适的细节层次需要从四又树的顶部开始递归。因为在Geomipmap算法中是假设视点沿着水平面移动，所以每个组块节点的物方空间误差被投影到屏幕空间得到误差。　　离观察视点越近的地方细节越多，即节点变长越小。视点与节点中心的距离d与