基于OSG的地形多分辨率四叉树模型

2013-10-08吴东亚黄玺瑛夏永春

装甲兵工程学院学报 2013年1期

吴东亚，邵伟，黄玺瑛，夏永春

(1.装甲兵工程学院科研部，北京100072;2.装甲兵工程学院装备指挥与管理系，北京100072)

目前，三维地形可视化技术在多个行业中已得到广泛应用，如三维城市建设、军事中战场地形的三维可视化显示等，众多成熟的商业可视化开发平台大都支持地形建模和可视化显示，但价格昂贵。OpenSceneGraph(OSG)是一个基于工业图形标准OpenGL的高层次图形开发API接口，具有开源、平台无关性、高品质及高性能等优点，已广泛用于虚拟仿真、虚拟现实、科学和工程可视化等领域［1］，OSG在地形可视化方面也提出了VirtualPlanetBuilder、osgGIS及osgEarth等解决方案。

随着地形显示范围的扩大和显示精度的提高，数字高程模型(Digital Elevation Model，DEM)数据量呈几何倍数增长，从而加大了计算机实时渲染的难度。针对这一问题，笔者以OSG为实现平台，构建了地形多分辨率四叉树模型，阐述了该模型的存储机制及调度策略，最后在OSG中采用该模型实现了按需动态加载地形数据并进行实时渲染。

1 地形多分辨率四叉树模型定义

大规模地形实时渲染存在的主要问题是数据量过大，计算机无法一次全部加载数据。随着计算机软、硬件技术的发展，计算机的计算能力与存储容量均得到大幅度提升，采用传统的地形数据调度、渲染算法，一方面无法实现流畅渲染，另一方面也造成了计算机计算与存储优势的极大浪费。解决这一问题的核心是对地形数据的存储结构进行科学、合理的组织，优化数据调度算法，提高渲染效率。四叉树是一种数据组织结构，该结构的每个节点最多有4个子节点，如图1所示，常用于数据库存储或文件存储［2］。

图1 四叉树示例

地形多分辨率四叉树模型是将同一块地形数据按照不同分辨率进行分割存储管理的数据结构模型，适用于矩形栅格DEM，分割前后地形数据分辨率呈倍数递增关系，即分割后地形数据的网格间距是分割前网格间距的1/2。

矩形栅格DEM由地表规则网格单元构成［3］，结构如图2所示。

图2 矩形栅格DEM结构

地形多分辨率四叉树模型具有以下2个特点:一是除叶子节点外，其余节点都拥有4个子节点;二是4个子节点将父节点地幅按面积均分为4份。下面以如图3中所示的A地域为例，建立3级分辨率四叉树模型。

根据建立模型分辨率的层级数，将地域进行相应分割。建立3级分辨率模型，先将A地域按面积均分为4块，分别为 A1、A2、A3、A4，而后将该4块地域继续进行分割，生成16块地域，最终形成了A地域的3级分辨率四叉树模型，模型结构如图4所示。

建立多分辨率层级结构后，需设计对应的存储及调用机制，从而可按需调用不同分辨率的地形数据。

图3 A地域

图4 四叉树分割模型

2 地形多分辨率四叉树模型存储机制

2.1 存储结构

为便于快速检索数据，多分辨率四叉树模型采用大数据文件加索引文件的形式进行存储，大文件将模型中所有节点的地形数据进行整合，四叉树节点数据的存储顺序为从上到下、由左至右。大文件存储模式如图5所示。

图5 大文件存储模式

索引文件负责记录大文件中各个节点数据的相关信息，包括节点编码、分辨率级别、存储起始地址等信息，索引文件结构如图6所示。

图6 索引文件结构

图6中各个节点均有一条索引记录来记录该节点的相关信息，记录中的区域1-8地址信息为当前节点毗邻地域DEM数据的存储地址信息，如图7所示，节点A索引记录中的区域1-8地址信息依次记录A1，…，A8地域DEM数据的存储地址信息。

图7 区域关系图

2.2 DEM数据存储处理

将DEM数据进行处理，生成上述存储结构，即通过数据内插、分块、合并等多种操作对DEM数据进行处理。DEM数据处理流程如图8所示。

图8 DEM数据处理流程

分辨率高的分块的DEM数据主要由低分辨率数据采用内插算法生成，即根据若干相邻的高程点求出待定点上的高程值，如常用的加权平均算法等，在数学上属于插值问题;而后将同一地域不同分辨率的DEM数据组织成大文件，并生成索引文件。

构建DEM多分辨率数据时，还需考虑文件大小的影响，若生成的文件过大，文件的定位索引会变慢，不便于对其进行处理。对此，可将要处理的地域合理划分为多块，对每块建立多分辨率模型并存储为大文件，由此减小各个文件的大小，文件名需包含各块地域在整个地幅中的位置，如采用行号、列号对文件进行命名，便于处理系统调用不同地块文件［4］。

2.3 纹理数据存储处理

为提供逼真的地形显示效果，还需在地形表面粘贴纹理图片。因此，需为各级分辨率地形数据准备一块对应的纹理图片并进行存储，纹理图片处理步骤如下［5］。

1)定位。根据地形数据块覆盖的区域，确定相应的纹理图片，即选取该地域的纹理图片进行处理。

2)纹理文件处理。为确保地形显示正确、不变形，纹理图片像素需和地形数据采样的行列数成正比关系。如对行列数为500×300(地域内的高程数据按照纵向500行、横向300列采样获取)的地形数据，纹理图片需处理为a×b(像素)，a与b满足条件a/500=b/300。

3)合并处理。若低分辨率纹理短缺时，该纹理文件还可由高分辨率纹理文件合并生成。

4)存储。将生成的纹理文件按照对应的DEM数据存储模式进行存储，生成大数据文件及索引文件，以供调度使用。

通过以上4个步骤，即可生成纹理文件，纹理文件的组织方式与地形数据相类似。

3 地形多分辨率四叉树模型调度机制

3.1 模型调度策略

并行处理技术是在同一时刻或同一时间间隔内执行或完成2种或2种以上性质相同或不同的工作［6］。从工程角度考虑，采用计算机实现并行处理，多是在程序设计中构建多线程机制，给各个线程分配任务，并利用约束条件使线程运行达到同步，由此实现线程的并行运行。

采用多线程并行机制对地形多分辨率四叉树模型进行调度，关键是如何分配任务，任务划分不合理，反而会适得其反，另外多个调度任务还需设计机制进行同步。多线程并行调度机制设计思路如图9所示。

图9 多线程调度模式

除主线程外，另创建9个分线程，其中:8个分线程负责调度区域1-8的地形数据;剩余的1个分线程负责读取索引文件，读取结果供8个调度线程使用。

采用上述调度机制，线程9需与其余线程达到同步，线程9读取到数据地址后，其余线程才可按照地址访问数据，同步采用共享内存的方式进行实施，在内存中共开辟10个状态标志位，分别记录10个线程的工作状态，操作关系如图10所示。

图10 线程-状态标志位操作关系

线程9对标志位9进行读写操作，记录数据地址是否找到，主线程及线程1-8读取标志位9信息，而后判断是否可读取地形数据;主线程及线程1-8对标志位10及1-8进行读写操作，线程9读取标志位10及标志位1-8信息，而后可判断是否可读取新的地址信息。

3.2 调度触发器

对于观察者而言，视点距离决定调用不同级别的分辨率数据。人眼视角通常为120°，集中注意力时约为25°，视点越高，人眼可观察区域越大，人眼观察物体时，能清晰看清的视场区域对应的分辨率为2 169×1 213(像素)，加上上下、左右比较模糊的区域，总的分辨率约在6 000×4 000(像素)［7］。从上述人眼的可视条件考虑，当视点较高、观察区域较大时，可调用低分辨率地形数据，若调用高分辨率地形数据，人眼无法辨析;当视点拉近时，观察区域变小，可充分利用人眼观察能力，调用高分辨率地形数据。不同级别分辨率地形数据调度与观察者视点高低存在映射关系，结合多次试验，3个级别分辨率地形数据切换设置如图11所示。