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

开篇：润墨网以专业的文秘视角，为您筛选了一篇临近空间平台下地形四又树优化分割算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

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

关键词：临近空间；四叉树；地形绘制；网格剖分

中图分类号：TP79

文献标志码：A

文章编号：lOO5-2615（2015）01-0059-05

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

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

四叉树网格兼具结构网格和非结构网格的特性.一方面具有结构网格的正交性特点，另一方面具有非结构网格的灵活性特点，便于网格的自适应化，进而方便处理复杂的边界问题。本文提出的新的四叉树算法得到的三维真实感地形不仅形状各异，而且实时动态变化。不必进行大量数据处理和附加计算.用少量的数据即可得到复杂的地形数据的逼真图像。

1 基于四叉树的动态地形生成算法

1.1 四叉树算法

树形结构是一种非线性结构，它在查找算法中有独特的优势。若将采样数据以某种形式划分，形成四叉树，缩小查找区域，减小查找数据量，将会提高查找效率。

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

在采样区域内随机分布着一系列采样数据点，当取nq=10时，其采样数据的划分如图1所示。图2为图1中采样数据的四叉树表示，“”为四叉树结点，“”表示对应结点（即子区）所含的采样数据。在子区内，由于数据量已控制在阈值范围内，冈此为简便起见，一般以线性链表存放。

地形绘制是四叉树算法的核心，用来完成三角形网格的所有绘制，算法流程如图3所示。

1.2 改进的四叉树算法

Ulrich提出了一种层次细节算法，该算法目的是在现代图形硬件上高效地渲染海量地形数据。本文算法借鉴了Geomipmap的一些思想，但做了较大的改进。该算法基于四叉树结构。四叉树的每个节点覆盖某一块区域，形成一个连续继承的关系。根节点有一个最低分辨率的多边形网格覆盖整个地形，其4个子节点分别覆盖1/4地形，但分辨率更高。地形递归细分，直到得到原始分辨率的地形。

地形数据多边形网格存储在四叉树的每个子节点，称之为“地形块”。每个地形块与其他地形块的关系相互独立。图4是一个三层四叉树地形块的示意图，分别代表父节点、4个子节点、16个孙子节点。

每个节点即地形块有一个最大几何误差。与Geomipmap一样，几何误差就是当前数据与原始数据在物方空间的最大背离。当地形块被构建时，它们的误差值随着每一层的细分而减半。例如一个节点有误差值16，则其子节点误差值为8，其他层次1，点误差以此类推。

要选择合适的细节层次需要从四又树的顶部开始递归。因为在Geomipmap算法中是假设视点沿着水平面移动，所以每个组块节点的物方空间误差被投影到屏幕空间得到误差。

离观察视点越近的地方细节越多，即节点变长越小。视点与节点中心的距离d与节点边长e成正比不等关系，设C为一个可调节常数：距离分辨率，则'd

如上所述，本文可以通过增加更多的采样值来为数据增加更多的细节。因为本文算法的点云数据存储在瓦片四叉树中，为了增加更多的采样值，四叉树必须用新的瓦片扩展。因为本文目的是实时扩展四叉树，所以输入的可能是低分辨率的点云数据，但是映射时可能会具有较高的细节层次_。

1.3 裂缝处理

在对地形进行渲染时，如果相邻子块节点的分辨率不一致，则在构建三角形网格时，就会在相邻的边界上出现裂缝，这是地形绘制时必须处理的问题。针对块与块之间的裂缝问题，国内许多学者采用限制相邻节点层次差不超过1的方法来消除裂缝，但是这种方法只适用于少量静态地形数据的场合。但在处理海量地形数据的过程中，要不断对节点的层次差进行判断，这个过程不仅计算量大，而且CPU处理时间比较长。为此本文提出了一种新的方法来消除裂缝。根据投影长度对规格网格进行重采样，使得边界采样点的个数与投影的长度成正比，网格内部采样点依据边界情况均匀过渡，使得均匀网格变成一种密度均匀变化的不规则网格，这样不仅可以消除裂缝，而且还大大减少了绘制图形的复杂程度，同时也不会影响观察的效果。结合节点分割和渲染规律，提出一种裂缝消除方法。算法基础是视点到节点中心距离较大时细节较少，因此裂缝消除通过缩减边的方式实现；而距离较小时需观察到的细节较多，通过剖分可使细节变得更丰富。算法流程如下：

（1）遍历过程巾两个节点问层级相差一倍以上的情况；

（2）判断节点视点距离d与给定阈值m的大小；

（3）若d>m咒则缩减高精度节点，重新设置分割标志；

（4）若d≤m则剖分低精度节点，重新设置分割标志；

（5）重复步骤（2～4）直至1所对应的节点全部剖分。

2 算法实现及实验结果

本文以某遥感数据网站提供下载的美国某地区地形数据为例，如图5所示。

该地形数据包含8 770 495个点，对其进行了网格剖分实验。由于该地形数据包含的点云数据量较大.直接使用Delaunay三角剖分，会使得地形的细节无法很好地显示出来，采用上述的四叉树原理.首先将水平方向和垂直方向二等分，得到4个子区.本文中以1 300 000个点为界限，如果该子区内的点小于等于1 300 000个，则该子区不需要进行继续划分.可以直接进行剖分；反之则将该区域继续四等分.直至所有的子区的点都小于1 300 000个为止。其采样后的子区划分结果如图6所示。每个子区内点的个数如表1所示。

图7为采用经典Delaunay，剖分方法得到的结果。采用四叉树算法得到的图像如图8所示。将图7，8比较可以看出，Delaunay，剖分方法得到的结果采样密度较大，层次感不够明显，且采样时间长。而采用本文提出的算法剖分后得到的结果层次清晰，可以更好地显示地形的层次结构。

分析实验结果可以看到：由于在瓦片四叉树中每个瓦片数据块是完全独立于其他数据块甚至于树本身，因而数据的调度简单，调度效率高；使用四叉树结构简化了算法的实现过程；通过细化处理瓦片数据，提高了数据的网格绘制效率，在INTEL i52. 53 GHz双核系统Matlab 2010b未优化环境下，运行时间从整体数据时的l 283. 498 s减到了四叉树分块数据时的79. 374 s，缩短了93. 8%。

接下来针对临近空间平台半实物仿真地形数据进行同样四叉树优化分割算法的网格剖分实验。采样后子区内点的个数如表2所示。地形原图如图9所示。对图进行分区，得到的分区结果如图10所示。

同理，将本文方法与经典Dclaunay剖分方法进行剖分时间的比较，得到的结果如图11所示：

可以看出本文所提出的基于四叉树原理的地形分治三角剖分算法比起原有算法在速度上有大幅提升，且这一优势在处理更多数量点云数据时愈加明显。

3 结束语

本文提出了一种分形地形的新的四叉树生成算法，仿真图与仿真数据较好地体现了其优越性，能够随机性模拟地形和四叉树的层次细节，实时绘制地形。该算法在地形绘制速率和真实感效果上也有提升，实现了地形的快速剖分，且剖分效果良好。