基于四叉树的全球地形实时绘制方法

谢剑薇， 刘 涛， 于凤坤

（装备学院 信息装备系，北京101416）

随着“数字地球”（digital earth，DE）［1］和“全球信息网格”（global information grid，GIG）概念的相继提出，建立具有多分辨率、海量数据的大规模虚拟地形场景在全球范围受到越来越多的关注。“数字地球”强调对地球的真三维描述，因此，基于全球三维地形的实时绘制技术成为面向“数字地球”的虚拟现实系统的关键技术之一，即如何在计算机上对数字地形模型（digital terrain models，DTM）中的地形数据进行实时三维显示、模拟仿真［2］。

减少视景体以外场景的绘制是加快全球海量地形数据可视化的有效途径之一。根据可见性评估的依据，可见性剔除算法可分为3类：背面剔除（back face culling）、视域剔除（view frustum culling）和遮挡剔除（occlusion culling）［3］。由于基于全球地形数据实时绘制涉及数据量非常庞大，一般采用视域剔除算法，即计算当前视域内的地形；然后根据节点评价准则，对地形进行剖分，得到多分辨率地形可见节点集。由于节点之间分辨率不同导致边界出现裂缝，因此在绘制之前进行不同分辨率节点之间的无缝处理。本文全球地形数据采用四叉树逻辑存储结构。

1 地形数据组织

由于地理空间采用经纬度方式自然分割，因此地形数据很适合采用四叉树结构进行存储。全球地形数据以如下四叉树［4－5］形式进行组织，如图1所示。所有地形数据均放在全球范围内进行定位，四叉树的第1层分别对应东西两半球地形数据，然后每一节点按照地理区域均匀分割为4个子节点，如此继续，一直分割到所需要的精度。全球地形数据以这样的逻辑四叉树进行存储，每个节点的地理位置是确定的，用经纬度表示。每个节点包含特定范围地形数据，采用规整网格进行地形数据的存储。通过实验，每个节点中数字高程模型（digital elevation model，DEM）数 据 采 用33×33采样点，数字正射影像（digital orthophoto map，DOM）数据采用256×256采样点，在这种情况下每一帧数据量大小满足实时显示的需求，同时以影像为纹理，与地形数据匹配效果好。

图1 全球地形数据四叉树逻辑结构

2 全球地形数据快速可见性判定

本文采用基于四叉树的全球地形快速可见性判定的基本思想是：通过球面解算实现数据过滤，减少了图形绘制的数据量。将地球看作一个空间的球面，用相机视域与其求交，剔除视域以外的部分；对视域以内的部分，则依据节点评价准则，对地形进行剖分，得到一个多分辨率地形可见节点集，以保证每一帧地形的绘制数据量保持基本恒定。

2.1 可见区域的计算

首先根据给定的相机参数（包括视点、观察方向以及相机内参数），针对球模型计算出可见范围。可见区域的计算方法如下：

1）根据当前相机位置、相机观察方向、视域和焦距确定相机观察视域4条锥线的方程，并计算各条锥线与球面的交点；

2）根据相邻2条锥线与球面相交的情况，计算相机各个锥面与球面相交的空间圆弧以及相交圆弧的相关信息（包括圆弧半径、圆心位置以及圆弧起始点与结束点）；

3）合并各段圆弧，得到相机视锥与球面相交的轮廓线；

4）根据轮廓线各段圆弧的角度和对其进行相应采样，得到一组采样点集合；

5）将采样点投影到测量平面坐标，并顺序相连，得到一个多边形区域，该区域即为可见区域。多边形区域的顶点坐标用经纬度坐标表示。

2.2 多分辨率地形可见节点集的生成

得到上述的可见区域后，需要根据视点以及地形模型对其进行剖分，以得到一个既能满足视觉质量，又能保证数据量尽可能小的多分辨率地形节点集。因此节点评价准则必须使生成的网格尽量减少几何形变，在保证实时性的前提下，使画面质量接近全分辨率时的地形［6］。在建立节点评价准则时，一般要考虑视距与地形本身粗糙程度的影响［7］。本文节点评价函数的建立，主要考虑视距的影响，这是因为在后续过程中会对节点内数据进行相应调整，使得绘制数据量满足实时绘制的需求，所以没有必要再进行地形粗糙度的判定以进一步减小绘制的数据量。

2.2.1 视距标准

从人体视觉仿生角度出发，希望距离视点近的景物能够很精确地显示，距离稍远的则不用很精确，因此采用距视点距离作为地形节点剖分依据。但是目前几乎所有的视线相关的距离计算方法，都局限于在距离计算中添加一个不同的视线因子，只是经验公式，且忽略了深度（Z轴）的影响［8］。为此本文采用如下节点评价标准：计算可见区域多边形在当前相机参数的投影面积，根据投影面积确定当前节点是否有必要进行剖分，该评价准则充分考虑了视线方向的影响。多边形投影面积计算公式为

式中：多边形由顶点p0，p1，…，pn顺时针组成；p′i是点pi的投影坐标；A是当前相机的投影矩阵。

式中：S是多边形的投影面积；P′ix和P′iy表示点pi的投影坐标x与y值。

如果当前多边形的投影面积大于给定阈值，则对该多边形所在的节点进行细分；否则输出该节点。投影面积阈值设置为256×256＝65 536，这样使得地形数据投影尺度与DOM节点数据分辨率一致，可以得到最佳的视觉效果。

2.2.2 多分辨率地形可见节点集生成流程

在得到当前视点下的可见区域后，依据上述的视距标准对可见区域是否细分进行判断，由此得到1个多分辨率地形可见节点集。具体算法流程见图2所示。

图2 多分辨率地形可见节点集生成流程

3 裂缝处理

在对地形进行渲染时，如果相邻子块节点的分辨率不一致，则在构建三角形网格时，就会在相接的边界上出现裂缝，这是地形绘制时必须解决的问题［9］。针对块内“裂缝”问题，不少学者研究采用限制相邻节点层次差不超过1的方法消除裂缝，且只适用于少量静态地形数据场合。但处理海量地形数据时，要不断地对节点层次差进行判断，计算量大、耗费CPU时间长［10］。为此本文提出一种新的方法来消除裂缝。本文地形数据采用规整网格结构，由于观察方向原因，网格各边界投影长度会有很大差别。若根据投影长度对此规则网格进行重采样，使得边界采样点的个数与投影长度成正比，网格内部采样点依据边界情况均匀过渡，如此一来均匀网格变成了一种密度均匀变化的不规则网格，这样不仅可以消除裂缝，而且大大减少绘制的复杂度，同时不会影响视觉效果。具体过程如图3所示。

图3 网格重采样消除裂缝

从理论上说，由于相邻数据节点的相邻边界无论分辨率是否相同，它们在屏幕上的投影长度都是相等的；所以，经过重采样简化处理以后，相邻数据块的共同边界的重采样点分布情况也是相同的，这样自然而然消除了裂缝。但实际上会出现图4所示的情况，节点A右边界采样步长为2，节点B左边界采样步长为2，节点C左边界采样步长为4，使得节点A与节点B之间出现裂缝。这是由于边界重采样步长只能是2的整数幂，使得重采样不能完全根据实际投影长度来进行，当相邻数据块共同边界的重采样投影长度不一致时就产生了裂缝。在这种情况下采用分辨率向面积大的数据节点看齐的方法，即比较一个数据节点的相邻节点，如果相邻边的分辨率（边界重采样步长）不同，则比较2个数据节点的面积，调整面积较小的数据节点的边分辨率等于面积较大的数据节点的边分辨率。针对图4所示情况，即调整节点B的采样步长为4，这样节点A、B之间的裂缝就消除了。这样做是牺牲了某些节点部分数据的分辨率，但是不会明显降低显示质量。

图4 裂缝消除前后的多分辨率地形模型

为了避免重采样所占用的时间开销，采用模式文件存储各种可能产生的网格情况，在地形数据绘制时，直接调用模式文件绘制相应的不规则网格。节点网格重采样方法不仅能够实现各不同分辨率节点之间的无缝拼接，而且使得绘制数据的冗余量大大减少，在保证输出图形效果的同时，大大提高了绘制速度。

4 算法实验结果

通过实验测试，基于四叉树的全球地形实时绘制方法可以在计算机上实现全球地形的实时浏览，平均达到50帧／s以上的高速漫游。测试环境为：CPU为P4 2.8G，2G内存，750G硬盘，操作系统Windows XP，显示器分辨率1 024×768，GEFORCE6200（512 M显存）显卡。表1是不同视点情况下一帧图形绘制数据量（三角形个数）测试结果，由测试数据可看到每帧数据量基本恒定，其中视点位置用大地坐标系表示，观察方向用方位角、俯仰角和滚动角来表示，所有角度表示用度为单位，表1测试视点位置的经纬度固定，为（116.662 0°，40.353 6°），观察方向固定，为（90°，－30°，0°），视点高度不同；表2是采用节点网格重采样方法与直接利用规整网格绘制数据量的比对 结 果，视 点 位 置（116.662 0°，40.353 6°，20 000m），方位角为90°，滚动角为0°，俯仰角有变化。

表1 不同视点下绘制数据量的比较

表2 不同方法绘制三角形数目的比较

5 结 论

基于四叉树的全球地形实时绘制方法计算球模型与相机锥面的相交区域，得到可见区域，计算方法简单；以投影面积为节点评价准则，对可见区域进行剖分得到1个多分辨率地形可见节点集。依据节点边界的投影长度进行网格重采样，在消除裂缝的同时，大大减少绘制冗余数据量，使得每一帧地形绘制的数据量保持相对恒定。算法应用到数字地球平台中，可以实现基于全球地形数据的实时浏览。

（

）

［1］承继成，郭华东，薛勇.数字地球导论［M］.北京：科学出版社，2007：1－5.

［2］凌实.大规模地形LOD模型简化与实时绘制方法研究［D］.合肥：合肥工业大学，2009：1－13.

［3］COHEN D，CHRYSANTHOU Y L，SILVA C T，et al.A survey of visibility for walkthrough appli－cations［J］.IEEE Transaction on Visualization and Computer Graphics，2003（3）：412－431.

［4］邢伟，孙延奎，唐泽圣.与视点相关的多分辨率地表模型简化算法［J］.清华大学学报：自然科学版，2004，44（l）：29－32.

［5］龙熙华，靳玉萍，宋勇利.大规模地形真实感渲染技术研究［J］.计算机工程，2012，38（7）：260－262.

［6］吴忠.四叉树LOD算法优化及在地形仿真中的应用［D］.武汉：华中科技大学，2006：7－15.

［7］李颖，陈业斌.基于四叉树的三维地形绘制算法［J］.安徽工业大学学报：自然科学版，2008，25（1）：80－82.

［8］娄高鸣，李小奇，侯健，等.一种基于四叉树的动态多分辨率LOD大规模三维地形绘制研究［J］.装备制造技术，2009（8）：53－55.

［9］于卓，梁晓辉，马上，等.一种支持大规模多种精度地形的实时绘制算法［J］.计算机研究与发展，2010，47（6）：988－995.

［10］原庆红，韩燮.基于视点的分块LOD大规模地形生成算法研究［J］.微电子学与计算机，2011，28（6）：41－45.