基于四叉树算法的三维地形显示技术

孙锴

（太原航空仪表有限公司 山西省太原市 030006）

随着航空领域的快速发展，航空座舱显示设备已经逐渐由以前的二维显示模式向三维显示模式发展。在三维显示模式下，飞行员可以直观的感受到飞机当前所处的状态，而三维地形显示可以更好的为飞行员提升飞行体验。由于三维地形显示需要的DEM 高程数据和卫星图片数据数据量很大，因此采用合理的算法组织数据显示是三维地形显示的重中之重。

1 地球表面几何模型

由于绘图操作中的三维坐标系统是直角坐标系统，因此我们对地球表面进行几何建模，以地球中心为原点，地球表面近似认为是一个半径为6378137.0 米的正球面（没有考虑实际的地球是近似椭球体，地表大圆长度40075016.0 米），地心到本初子午线与赤道交点的矢量为X 轴正向，地心到北极点的矢量为正Z 轴方向，X,Y,Z 构成右手系坐标系统（这样Y 的正向是地心到赤道与东经90 度交点的矢量）。

这里提供的三维地图都基于这个几何模型，它的坐标系统与常用的经纬度，高程坐标系统的转换关系如下：

经纬度，高程分别用J,W,H 表示（J,W 用弧度单位，东经北纬为正，H 用米单位，海平面为0，海平面以上为正），几何模型的三维直角坐标系统坐标用X,Y,Z 表示（用米为单位），则换算关系是：

X=(H + EARTHRADIUS) * cos(W) * cos(J)

Y=(H + EARTHRADIUS) * cos(W) * sin(J)

Z=(H + EARTHRADIUS) * sin(W)

J=atan2(Y,X) (arctg(Y/X)) (反正切，取值-180--180)

W=arcsin(Z/sqrt(X2+Y2+Z2)) (反正弦，取值-90--90)

H=sqrt(X2+Y2+Z2) - EARTHRADIUS (sqrt 是开平方)

其中EARTHRADIUS 为地球半径，定义为6378137 米，如图1所示。

2 数据逻辑坐标系统

如图2所示，三维地图中的数据相关的位置可以用经纬度表示（高程作为一个数据属性，表征了地形），为了支持不同的地球表面投影方式，我们在三维地图引擎内部不直接采用地理坐标系统，因为地理坐标系统在某些投影方式中不是线性的，不便于在直角坐标系统中使用。我们采用一种逻辑坐标系统，该系统中的数据按二维组织，二维坐标范围都是[0,1]。在地表的分布如下：

三维地图引擎中事实上不关心数据的地理坐标，只需要关心逻辑坐标即可。用户使用三维地图引擎时可以指定投影方式（给出投影方式下地理坐标与逻辑坐标之间的相互转换算法），数据则按照逻辑坐标提供。比如在谷歌地球的墨卡托投影坐标系统中，北京天安门广场旗杆附近（E116.3910,N39.9055）的逻辑坐标是：(0.823308,0.379606)。

三维地图引擎要求地形数据和地表影像数据按照逻辑坐标提供，这两部分由系统处理。其他的用户层数据可以自行处理，也建议按照逻辑坐标组织，具体参见后面的数据组织方式。

3 按四叉树组织的地图数据

图1：三维直角坐标系统与地理坐标系统示意图

图2：三维地图引擎的数据逻辑坐标

图3：四叉树组织的地图数据

图4：按四叉树组织的地图数据

图5：绘图任务与数据加载任务的执行流程

三维地图涉及到的地图数据量比较大，不可能全部放在内存里，显示时在不同的视角看到的范围和内容都不同，离得远的视角，看到的范围广，但是细节少，分辨率低，反之，离得近看，看到的范围小，但是细节丰富，分辨率高。同一个地理目标的绘制方法也不一样，比如一栋高楼，在10 公里距离以上，可能就标记为一个点目标，在1 公里距离内，可能成为一个三维目标。细节也不一样，在50 公里高度俯视地表，可以看到200 公里方圆的内容，最小的行政目标可能是县级，在5 公里高度，可能就需要到村镇级别了。还有一个特征是，在不同的地方数据的分辨率可能不一样，在重点城市，可能详细到足以分辨街道，在一些深山老林，能够分清山的走向和植被分布就够了。这些需求都要求地图数据应该按照多分辨率存储。

三维地图引擎中的数据用四叉树组织，可以满足上述的要求。具体做法如下：

在上述的逻辑坐标系统中，把全球数据作为一个树根，平分成四份，每一份作为它的四个子节点，以后每个子节点又包括四个子节点，以此类推，就构成了一棵四叉树。其中的每一个节点构成地图数据中的一个图幅。我们为每个图幅给出一个唯一的编号，每个图幅的编号由三个数字组成：层号，横向坐标，纵向坐标，其中横向坐标和纵向坐标是同一层中的图幅编号，按照逻辑坐标的顺序编码，所有编号都从0 开始，在第k 层，横向和纵向的编号是从0 到2k-1。从图幅编号可以得到它所在图幅的逻辑坐标范围，从某个地理目标的逻辑坐标也可以得到它在指定层中的图幅号。比如上述讲的天安门广场旗杆，逻辑坐标是0.823308,0.379606，在第九层中所在图幅的编号就是(9,0.823308*512,0.379606*512)，即(9,421,194)。

一般情况下，我们的数据对一幅图的数据量是一样的，层数越小，一幅图的范围就越广，分辨率就越低。

在三维观察视角看到的场景，离得远的，层数就小，离得近的，层数就大，这样保证防拥效果。每一个视角看到的场景在地图数据树中对应一个树的切面。如图4所示。

节点(l,m,n)的四个子节点编号分别为：

(l+1,2m,2n),(l+1,2m+1,2n),(l+1,2m,2n+1),(l+1,2m+1,2n+1)

节点(l,m,n)的父节点编号为(l-1,m/2,n/2)(l＞0)

在实际的应用中，这棵四叉树不一定是完全四叉树，这样可以在不同的地域对应的最大层号不同，从而实现不同的最大分辨率。比如在国内的应用中，全球的数据，可以采用到第9 层，中国地区可以到第13 层，重点城市或重点目标，可以到第18 层，像素分辨率可以到米级以下。

4 数据调度算法

由于三维地图的数据量大，同时需要访问的图幅数据又是有限的，在连续视点变换的应用中（比如模拟飞行），该缓存哪些数据，就靠数据调度算法来实现。

在设定一个视角参数后，我们从四叉树的树根开始往下反复检查，先查节点是否在视口中出现，如果不出现，该图幅就不需要调入，如果出现，判断其分辨率是否够（如果该图幅在视口中占的屏幕百分比超过一个阈值，就认为分辨率不足。在分辨率不足时，如果该节点有子节点，就接着检查它的四个子节点。这样，我们就收集到一系列不同层次的图幅，要么是分辨率达到要求，要么是没有子节点，这些图幅就是需要绘制的图幅。

在实际使用中，我们在内存中存放一定数量的图幅数据，需要绘制的图幅就调入内存，不需要绘制的图幅就删除，这样可以在连续的视点变换应用中维持一个有限的节点数目，最大的节点数可以根据系统中内存的大小来决定。

在实际实现时，数据的加载一般比较慢（有可能要对数据进行预处理，比如压缩图像解码，格式变换等，或者通过比较慢的网络加载数据），为了保证数据加载过程不会造成绘制过程的暂停，我们一般采用不同于绘图任务的任务（线程）来进行数据加载，保证绘图任务的平滑运行。这样，分辨率高的地图数据没有加载完成时，就先绘制分辨率比较低的数据。

5 嵌入式下地图数据加载

为保证图形显示的性能，避免显示时卡顿，地图的绘制和地图数据的加载分别在两个任务中执行。数据加载任务负责从电子盘读取地图数据，而绘图任务不需要等待从电子盘读取地图数据，这两个任务的执行流程如图5所示。

其中，绘图任务在判定一个图幅需要显示之后，会将该图幅的信息加入到待加载图幅队列中；数据加载任务从这个队列中读取要加载数据的图幅，读取成功之后，对该图幅做出已加载完成的标记；绘图任务在显示图幅时如果读到了数据已加载成功的标记，就把该图幅绘制出来，否则就不绘制该图幅了。

6 结语

随着航空领域的快速发展，对机载座舱显示设备都提出了较高的要求，具有真实视觉效果的三维显示技术可以为飞行员提供更好的飞行体验。