去LoD层级约束的海量三维地形裂缝实时消除算法

刘振东，李成名，武鹏达，刘 坡

(中国测绘科学研究院，北京 100830)

随着遥感测绘数据采集、数据存储技术的发展，地形数据规模越来越大，地形之上承载的建筑物模型、视频、管线等数据日益丰富。对于大范围、大场景下的地形来说，既要对其丰富的细节进行逼真的显示，又要尽可能地减少计算量，为场景中其他对象腾出渲染时间和空间，因此，研究海量三维地形的实时渲染技术具有重要意义。当前，国内外主要采取视点相关的连续LoD(level of detail)[1-2]技术对地形数据进行简化，然而，由于LoD技术中存在细节层次差异，不同层级的相邻地形网格边界上网格点的高程值并不完全一致，导致地形实时渲染过程中会出现地形裂缝。裂缝问题是LoD技术中一个必须解决的关键问题[3]。

传统的地形裂缝处理方法尝试通过调整网格边界顶点、附加补丁、模板分解等几个方面解决该问题。调整网格边界顶点法[4]出现较早，主要通过在裂缝处为较高层次网格添加顶点或在较低层次网格中删除相应顶点的方式，使不同层次的对应节点具有相同高度，从而消除裂缝。这类算法使用范围广，但CPU运算量大，对LoD层级跨度要求高。垂直边缘法(vertical skirt)[5-6]是一种典型的附加补丁算法，通过为每个地形网格的四周添加垂直向下的“裙边”，以“裙边”充当补丁去遮挡视觉上的裂缝。但该方法会额外绘制地形面片，当进行大场景地形实时渲染时，会给计算机带来不小的负担，同时在接缝处容易造成地形垂直显示，破坏真实地形高度变换规律。限制性四叉树算法[8-10]通过确定顶点约束关系解决地形裂缝问题，然而该算法仅考虑了相邻层次节点的约束关系，因此，同样存在层级跨度低、地形陡峭处的三维真实感表现力不够的问题。

整体而言，传统的地形裂缝消除方法在实现海量三维地形数据实时渲染时，通常会存在运算量大、渲染效率低、瓦片层次跨度小等问题。鉴于此，本文在分析地形四叉树组织方式及地形LoD控制规则的基础上，提出一种去LoD层次跨度约束的海量三维地形裂缝实时消除算法。

1 带有邻居关系的地形四叉树结构

当相邻地形网格的LoD层次等级不相同时，网格边界处的分辨率不一致则很可能造成地形裂缝。因此，实现地形裂缝消除的关键在于运用四叉树数据结构对地形进行LoD动态实时绘制时，能够对地形网格节点的邻近关系进行准确地识别及判断。为此，本文首先建立包含边邻居与角邻居的地形四叉树结构，即对传统地形四叉树增加以下约束：

(1) 地形网格节点简称为瓦片(Tile)，如图1中的A1、A2等，瓦片以所在LoD层级、所在的列号、所在的行号作为唯一编码，即Tilecode=(LoD，TileX，TileY)，且每个瓦片包含M×M个顶点(M为瓦片某边上的网格点数，且为正整数)。

(2) 地形四叉树中，没有“父亲”的节点称为根节点，如图1中的节点C1，没有“孩子”的节点称为叶节点，如图1中的节点C2、C6、C7等。

图1 四叉树地形结构

(3) 以某一瓦片为中心、空间关系为依据，将其周围瓦片划分为边邻居、角点邻居两大类。其中边邻居类可分为：左边邻居(LN)、上边邻居(UN)、右边邻居(RN)、下边邻居(DN)。角点邻居类可分为：左上角邻居(LUN)、右上角邻居(RUN)、右下角邻居(RDN)、左下角邻居(LDN)，如图2所示。

(4) 四叉树结构中，依据“父亲”节点、“孩子”节点之间的空间关系，将位于“父亲”节点左上角的“孩子”节点命名为LUChild、右上角的“孩子”节点命名为RUChild、右下角“孩子”节点命名为RDChild、左下角“孩子”瓦片命名为LDChild。

图2 瓦片的邻居关系

特别说明，算法将只寻找LoD小于或等于当前瓦片的邻居，并将其存储在当前瓦片中。因为此时正处于地形四叉树动态重构阶段，瓦片会更新裂分、合并状态，这是一种状态极不稳定的阶段，该阶段无法确定绘制时瓦片的显示邻居。

2 地形裂缝实时消除算法

2.1 瓦片间邻居关系及其状态判断

邻居信息的动态更新处理是地形裂缝消除的关键步骤。本文根据叶节点自身特性，将邻居信息的动态更新处理分为裂分叶节点邻居信息处理算法和合并叶节点邻居信息处理算法两个模块。前者处于渲染帧的更新阶段，后者处于渲染帧的资源调出阶段。

瓦片间邻居信息的判断依赖于瓦片的空间位置关系，为便于计算，为瓦片的各个边、角方位邻居信息设置更新标识(Dirty)，Dirty具有休眠及激活两种状态。

2.1.1 裂分叶节点邻居信息及其状态确认

判断裂分叶节点位于“父亲”瓦片的方位，根据所在方位及空间位置关系，识别该瓦片的邻居信息。以左上角“孩子”瓦片(LUChild)为例，边及角点的邻居判断方式如下：

边邻居及其状态确认。因裂分叶节点为左上角“孩子”瓦片，因此它的右边邻居和下边邻居和当前瓦片属于同一“父亲”节点，在同一层级LoD中分辨率相同，故将当前瓦片的右边、下边及其右边邻居的左边、下邻居的上边的裂缝消除Dirty标识，设置为休眠状态；左边邻居和上边邻居与当前瓦片不属于同一“父亲”节点，则首先找到其“父亲”节点的左边邻居和上边邻居，进而计算当前瓦片的左边邻居和上边邻居，将关联瓦片相应边的裂缝消除Dirty标识，设置为激活状态。

角点邻居及其状态确认原理与边邻居及其状态确认原理相似，在此不再赘述。

2.1.2 合并叶节点邻居信息及其状态确认

因4个“孩子”节点要合并成一个“父亲”节点，则需依次更新4个“孩子”邻居节点的邻居信息。这里同样以左上角“孩子”瓦片(LUChild)为例进行说明。

(1) 边邻居及其状态确认。因右边和下边邻居和当前瓦片LUChild属于同一“父亲”，且三者被同时合并，因此这两个邻居瓦片的邻居信息不作处理；如果左边邻居(LN)、上边邻居(UN)存在且与当前瓦片的LoD层级相同，则4个“孩子”节点合并后，其LN、UN的邻居信息会发生变化，将LN的右边邻居、UN的下边邻居设置为LUChild的“父亲”节点，若LN、UN有“孩子”节点则需递归更新相关联的边邻居信息，同时将相应边Dirty标识设为激活状态。

(2) 角点邻居及其状态确认。与边邻居及其状态确认原理相似，因右下角邻居与当前瓦片属于同一“父亲”节点，因此此邻居瓦片的邻居信息不作处理；根据空间位置关系，如果左上角邻居(LUN)存在且与当前瓦片的LoD层级相同，则应将LUN的右下角邻居设置为LUChild的“父亲”节点，若LUN有“孩子”节点则需递归更新相关联的角点邻居信息；如果右上角邻居(RUN)或左下角邻居(LDN)存在且与当前瓦片的LoD层级相同，因二者与LUChild的“父亲”节点在空间位置上并不是角点邻居关系(如图2中瓦片O与UN2)，则二者需将相关联的角邻居设置为空，同样若RUN、LDN有“孩子”节点则需递归更新相关联的角点邻居信息。

2.2 去层次跨度约束裂缝消除算法

从根节点开始遍历地形四叉树的每个节点，探索需要消除的瓦片范围。根据视点相关的LoD控制规则，遍历瓦片判断其是否为新增瓦片。对于属于叶节点的新增瓦片，确认其邻居瓦片及其Dirty状态，若Dirty为激活状态则表明该瓦片存在裂缝可能，为此，本文提出去层次跨度约束裂缝消除算法。其基本思想为：以单个瓦片为处理单元，根据地形裂缝仅出现在瓦片边界处的特点，顺序处理瓦片的4条边和4个角点，通过线性插值方法使处在不同层级的邻近瓦片的节点高程值与处理瓦片对应节点的高程值保持一致。下面以某一瓦片的左边处理过程为例，详细阐述具体步骤：

步骤1：根据动态更新的瓦片邻居信息，探索当前瓦片的左边邻居节点(叶节点)。假设当前瓦片节点为N，节点N的左邻居信息数组为Lvec[](左边邻居可能有多种情况，如图3所示，但处理过程一致)。为找出三维地形场景中瓦片N的左边邻居，遍历Lvec[]数组中的成员，判断每个成员是否有“孩子”节点，有则将该成员右上、右下两个“孩子”节点LChild1、LChild2赋给当前节点N，作为N的左邻居，同时继续按上述步骤进行递归处理LChild1、LChild2，直至到叶节点，将其记录至邻居数组LYvec[]。在设置了N的左邻居后，同时将该左邻居的右邻居设置为N。

图3 瓦片左边邻居节点情况

步骤2：遍历左边邻居数组LYvec[]，进行消除运算。若LYvec[]中仅有1个节点，则表明左边邻居与当前瓦片N的LoD相等，二者在边界上的顶点关系是严格一一对应的，如图4所示，则可直接遍历边界上的每一个顶点，判断二者的高程值是否相等，不相等则以瓦片N作为基准，将其顶点的高程值赋值给邻居对应的顶点；若LYvec[]中仅有2个节点，且瓦片N与邻居节点的LoD相差1，则二者在边界上的顶点关系如图5所示，邻居瓦片两个格网的长度与瓦片N的一个格网的长度相等，此时对瓦片N的顶点进行等距离线性插值运算，得到瓦片N边界上两节点的中点高程值，并将该高程值赋给邻居顶点；若LYvec[]有4个节点，且瓦片N与邻居节点的LoD相差n(n>1)，则二者在边界上的顶点关系如图6(n=2)所示，说明邻居瓦片两个格网的长度是瓦片N的一个格网长度的1/n，此时计算出瓦片N中距离邻居瓦片最近的网格点，并将瓦片N的格网边上等距离分为2n个节点，利用线性插值算法得出每一个节点的高程，将该高程值赋给邻居顶点。

图4 LoD层级相等

图5 LoD层级相差为1

图6 LoD层级相差为2

本文提出的地形裂缝实时消除算法不需控制相邻节点之间的层级差，以实现去层级跨度约束的裂缝消除，而且该方法不需额外绘制地形面片，可以保持起伏的地形地貌。

3 试验与分析

本文依托中国测绘科学研究院研制的NewMap软件平台，嵌入提出的地形裂缝消除算法，以四川省典型山区地形数据为例对本方法进行效果验证。其中，高程数据来源于SRTM，经纬度范围为97.5°—108.5°E，26.2°—34.1°N，水平分辨率为90 m，竖直分辨率为0.1 m；影像数据来源于国际科学数据服务平台Landsat陆地卫星遥感影像数据。试验的硬件环境为：CPU Pentium Dual Core E5300 2.60 GHz，内存1.96 GB，显卡NVIDIA GeForce 6800。高程、影像四叉树金字塔依托NewMap TerrainPublish软件进行构建，金字塔大小分别为15.76、63.34 GB。

依据本文算法进行瓦片间裂缝消除试验的部分效果如图7所示，其中图7(a)为裂缝消除前三维地形可视化画面；图7(b)为裂缝消除后的可视化结果。对比两幅图片可以发现，本文算法在保证地形裂缝正确且完全消除的同时，能够很好地再现高低起伏的三维地形。

图7 本文算法裂缝消除前后对比

在瓦片裂缝处理时间上，首先测试了任意选择的某一视点下裂缝处理的瓦片数量及每个瓦片处理时间，如图8所示。从图中可以看出，单个瓦片的处理时间最小值为0.021 ms，最大值为0.15 ms；其次，随机选择某一路径漫游进行测试，从图9可以看出，每帧处理的瓦片数量基本维持在1～20个瓦片数，处理时间最小值为0.03 ms，最大值为0.74 ms。因此，结合图8、图9可知，每一帧裂缝消除的总时间最多不超过1 ms，消耗时间很少。

图8 单个瓦片裂缝处理时间

图9 漫游路径下裂缝处理时间

与前文中提到的裙边算法进行比较，由于本文算法是修改瓦片裂缝范围内的顶点高程值，因此不会产生多余的补丁，减少率为100%；从线框模式也可以看出裂缝消除后的瓦片网格并没有增加多余的三角面片。

4 结 语

本文提出了去LoD层级约束的海量三维地形裂缝实时消除算法，在四叉树地形表示结构和LoD控制规则的基础上，利用四叉树结构及父子节点间隐含的邻居关系，实现了地形裂缝的实时消除。以四川省典型山区地形数据为试验案例，进行了地形裂缝消除算法验证。试验结果表明，本文算法不需任何额外的“补丁”，而且瓦片层次跨度不受限制，在能正确消除裂缝的前提下最大限度地再现了起伏的真实感三维地形地貌，同时裂缝消除效率较高。总体而言，本文提出的识别模型较优于常见地形裂缝消除方法且操作简单、便于计算，更适用于海量地形的可视化表达与分析。