大规模虚拟地形数据多线程异步调度算法

任子健，陈 璐

(1.中车青岛四方机车车辆股份有限公司国家高速动车组总成工程技术研究中心,山东 青岛 266111；2.中国海洋大学信息科学与工程学院,山东 青岛 266100)

0 引 言

大规模地形的绘制是虚拟自然场景的重要组成部分，虽然地形环境仿真的研究已经有较长的历史，但海量地形数据的存储和调度仍然是虚拟现实领域的研究重点和难点。在进行局部小范围地形的可视化时，高程数据和影像数据的数据量较小，一般不会超过1 GB，计算机可以一次性地载入全部地形数据并进行处理和渲染。但在大规模地形环境下，地形的数据量随着分辨率的增加成指数级增长，可以达到TB级甚至PB级。即使不断地提高计算机的硬件水平，也很难实现海量地形数据的组织、存储、管理、调度和实时绘制。因此，如何利用计算机有限的处理能力实现海量地形数据实时调度和渲染已成为一个需要面对的重要问题。

1 大规模地形数据组织与存储管理

1.1 分层分块组织策略

在进行虚拟场景的绘制时可以将原始高精度的数据全部载入，以保证场景的细节完整性。但根据人眼观察物体的经验可知，人眼难以看清距离视点较远区域的细节。因此可以设想，在虚拟环境中进行物体的绘制时，可以由远及近采用不同的细节层次。而细节的精细程度，可以用等级的概念进行量化，等级可以根据视点与物体之间的距离进行计算，这就是LOD模型的基本思想。金字塔模型是一种多分辨率层次模型[2]，其概念跟LOD模型的思想非常稳合。图1所示为地形影像数据金字塔示意图，图中不同层级影像所代表的地理区域范围相同，而图像分辨率逐层降低，形式上如金字塔一般。

图1 地形影像和高程金字塔结构

理论上金字塔各层的分辨率应该是连续变化的，但实际上没有必要也很难做到分辨率的连续性。四叉树网格兼具结构网格和非结构网格的特性，一方面具有结构网格的正交性特点，另一方面具有非结构网格的灵活性特点，便于网格的自适应化[8]。因此，本文采用传统的四叉树结构进行金字塔模型多分辨率网格划分，如图2所示。地形数据分为DOM影像数据和DEM高程数据2类。DOM数据为图像格式，而原始DEM数据为规则格网数据。由于OpenGL纹理流水线读入纹理数据的速度非常快，因此为了提高DEM数据的读取速度，本文将DEM数据处理为32位图像进行存储，其中每个DOM瓦片块分辨率设置为256×256，每个DEM瓦片块分辨率设置为257×257。

图2 地形影像和高程数据四叉树结构

随着层级划分的增高，地形数据总量将以指数级增长。由于操作系统的限制，海量数据的移动、更新、查看会非常困难。文献[9]采用了一种Scene Graph(SG)的数据组织结构对地形金字塔数据进行组织，SG中并不存储实际的地形数据，只是作为一个数据的属性描述，在地形渲染时直接读取内存进行数据索引。当数据量较大时，SG文件直接读取内存会占用较大的系统资源，数据检索效率也会极大地下降。本文采用文献[4]中的方法对切割后的瓦片数据进行了再次的数据组织。对于空间上连续的256×256个瓦片数据，将其存储在一个Blockdata文件中，而索引信息存储在一个对应的Blockindex文件中。Blockindex文件顺序存储瓦片在Blockdata文件中的数据偏移量，Blockdata文件顺序存储瓦片数据本身及每个瓦片的长度值。Blockdata和Blockidex文件按照所在层级和编号进行命名。这样通过瓦片的级别、编号就可以读取相应的瓦片数据。通过这种紧凑型的数据组织方式，海量瓦片数据的更新、迁移和创建将更加方便和快速。

1.2 基于Hilbert填充曲线的存储优化策略

虚拟仿真环境中的空间数据往往是多维数据，并且任何一维都不存在一种排序可以完全反映数据之间的空间邻近性，使用传统方法划分并存储空间数据会割裂空间记录之间的内在联系，使空间上相邻的数据对象被划分到不同的存储空间上[10]。虚拟环境中进行交互漫游时，往往需要进行实时空间查询，读取当前视点及周围相邻区域的空间数据。如果空间相邻的数据分布在相隔较远的不同磁盘页面中，磁盘的磁头在读取数据时就需要移动较大的距离，从而增加硬盘寻道时间，降低了空间数据的调度效率。并且空间上邻近的数据若存放在不同的Blockdata文件中，当进行连续数据读取时，系统需要频繁打开不同文件，这会造成很大的系统开销。因此，理想的数据存储方式是让空间上相邻的数据在外存储器中的逻辑地址也保持相邻。

对于虚拟环境中的多维数据，通过平面投影可以降维成二维形式。外存中的数据一般是线性存储结构，可以通过一维索引进行检索。虚拟地形数据从三维表达到一维索引的过程可以用空间填充曲线映射方法表示。空间填充曲线又称为Peano曲线，是一种重要的近似表示方法，它将空间划分为一个个的网格，对每个网格进行唯一编码。这样多维空间数据就可以映射到对应投影位置的网格当中，最后降维成一维形式。普通的关系数据无法对多维数据直接进行查询，通过使用空间填充曲线对空间实体数据集进行降维处理，映射到一维空间进行编码，就可以重复利用已有的B-树索引、Hash索引、Bitmap索引等技术针对一维空间进行查询。理想的空间映射方法是：在多维空间中聚集的空间实体，经过填充曲线编码以后，在一维空间中是仍然是聚集的[11]。常见的空间填充曲线有：Gray码填充曲线、row-wise曲线、Z-order曲线和Hilbert曲线等。Abel和Mark等人认为Z-order曲线和Hilbert曲线非常适合多维空间数据的存储[12]。其中Z-order曲线编码简单，但Hilbert曲线具有更好的聚集能力。将空间数据用Hibert填充曲线填充和编码，然后将混合层数据按Hibert值升序存放到磁盘上，这样在查询某一网格数据时，可以认为其Hilbert码相邻的数据被访问的概率非常大，因此可对其磁盘上逻辑地址相邻的网格块进行预读，这样可以减少数据调度的I/O次数，从而提高数据访问效率[11]。因此本文采用Hilbert空间填充曲线进行数据的存储优化。图3为Hilbert曲线1～4阶填充示意图，高阶曲线填充图可以由低阶曲线填充图按照反射和旋转的方法迭代生成[13]。

图3 Hilbert曲线1～4阶填充示意图

从图3中可以看出，Hilbert曲线的填充原理跟本文基于四叉树的瓦片划分方式十分吻合，完全可以按照Hilbert曲线填充方式对每个地形瓦片进行编码，最后在外存中按照Hilbert编码值升序顺序存储瓦片数据。具体到本文中，地形瓦片数据是以Blockdata和Blockindex为存储单位进行存储的，每个Blockdata和Blockindex都由256×256(即24×24)个瓦片数据组成。因此，采用8阶Hilbert曲线进行编码和填充即可覆盖到每个Blockdata和Blockindex中所有的瓦片数据。

2 大规模地形数据实时调度

2.1 基于IOCP的地形数据异步调度

当地形数据量较大时，无法一次性载入到计算机内存中，这就需要研究大规模地形数据的实时调度机制。数据的“载入+卸载”过程即为数据调度过程[14]。海量数据的实时调度需要将当前视景体内所需渲染的数据读到内存和显存当中，而过期的数据要及时地卸载，以此保证系统的性能平衡、渲染的流畅和稳定。本文设计了基于IOCP的异步策略进行大规模地形数据的实时调度，实现了I/O操作及数据加卸载的合理运作。数据的加卸载主要通过对瓦片数据添加引用计数来实现，引用计数为1进行加载操作，引用计数为0进行卸载操作。如图4所示为地形瓦片数据的调度流程，具体步骤如下：

1)对地形环境进行空间查询，其中通过视锥裁剪确定当前帧需要渲染的地形瓦片，通过预测确定在接下来的漫游中需要渲染的地形瓦片。将视锥裁剪和预测确定的瓦片放入当前帧空间查询瓦片队列。

2)对当前帧空间查询瓦片队列进行遍历，对于新的瓦片引用计数初始化为0，然后对每个瓦片的引用计数加1。此时瓦片的引用计数有1和2这2种可能。引用计数为1的为空间查询后新出现的瓦片，引用计数为2的是上一帧就已存在的瓦片。对瓦片的引用计数进行判断，值为1转向步骤5，否则进行下一个瓦片块的处理。

3)当前帧空间查询瓦片队列遍历结束后，接着遍历上一帧空间查询瓦片队列，将此队列中每个瓦片块的引用计数减1。此时队列中瓦片的引用计数有0和1这2种值。引用计数为0说明此瓦片已不再需要，此时更新瓦片块链表，将该数据从内存中删除。引用计数为1，说明此瓦片同时出现在当前帧和上一帧所需要的集合里，数据可以直接从内存中拿来使用。接着进行下一瓦片块的处理。

4)上一帧空间查询瓦片队列遍历结束后，保存当前结果集，本次地形数据调度结束。

5)更新瓦片块链表，并发送I/O请求到辅线程，辅线程通过直接内存访问技术从外存中读取数据到内存并进行初始化。

6)由于数据读取和场景漫游渲染在不同线程中进行，刚读入到内存的数据可能已经不在当前帧空间查询所需要的队列里了。因此，瓦片块I/O读取完成之后需要判断瓦片块引用计数是否为0，如果为0，则更新瓦片块链表，将该数据从内存中删除。此时辅线程数据处理结束。

上述步骤中提到的预测数据是指不在当前视锥范围内，但可能出现在接下来视锥范围内的数据。可以通过当前漫游方向、速度和渲染帧速等计算需要预加载的瓦片数据，具体可以参考文献[15]中的方法，这里不做详细介绍。在三维可视化程序中，常用的相机漫游方式所使用的空间查询会有局部重复的特征[16]。因此，在数据调度过程中有些数据会不断地被加载、卸载，影响系统性能。通过建立合理的地形数据缓存策略，将暂时不需要渲染的预加载数据和不断被重复加、卸载的这部分数据放到缓存中管理，可以提高系统运行效率和数据的利用率。本文采用LRU缓存算法进行缓存策略设计，缓存结构采用文献[11,16]中的设计，本文不再赘述。

图4 地形瓦片数据调度流程

在数据调度过程中，I/O队列用来接收主线程发送过来的I/O请求，辅线程从I/O队列中提取I/O请求并进行数据的读取。I/O请求的发送和接收采用异步模式，即当进程将I/O请求发送到I/O队列之后，不等待I/O请求的完成，立即返回执行后续程序，大大提高了系统数据调度的效率。I/O队列中的I/O请求处理具有优先级。从用户的心理感知来说，场景由近及远载入和绘制更容易获得良好的视觉体验。而如果按照瓦片数据的距离远近进行排序，必然会大幅增加计算时间，降低系统效率。因此本文按照瓦片LOD等级进行粗略的排序，瓦片LOD等级越高则越优先进行I/O请求处理，这样就基本上满足了近处场景先载入，远处场景延迟载入的设计需求。

2.2 基于IOCP线程池的多线程管理

在辅线程数据处理阶段，采用IOCP的线程池机制进行线程的管理。IOCP的线程池在系统启动时预先创建好多个子线程，线程的数目取CPU数目×2+2[17]。这些子线程一般处于休眠状态，当有新的I/O请求时，系统会自动激活一个空闲线程给I/O请求使用。I/O请求完成后该线程回归线程池并处于休眠状态。如果当前没有空闲线程，则I/O队列处于等待状态，一直等到空闲线程出现为止，如图5所示。这样的分配和处理方式比在I/O请求时临时创建线程更加有效，可以大大提高线程操作的性能和系统的稳定性，并且易于管理和控制，较好地实现了系统的负载平衡。

图5 地形瓦片数据调度线程池结构

3 性能分析对比

为了对本文地形数据调度算法的性能进行评估，本文选取单线程同步I/O算法与本文算法进行对比分析(地形绘制效果如图6所示)。为了验证实验的有效性，分别对比了2种算法的平均数据吞吐量和时间复杂度。实验的硬件平台为Intel Core i5-3570K 3.40 GHz处理器，Nvidia GeForce GTX 650显卡(显存1 GB)、4 GB内存。首先，以数据总量为6 GB的青岛市25 km×20 km范围地形数据为测试数据，随机选取了5条漫游路线，在相同视点高度下，以相同速度在三维地形场景中漫游，然后记录漫游过程中的平均数据吞吐量。然后，选择6 GB，3 GB，1 GB，500 MB和200 MB这5种不同数据量的地形数据按2种不同算法进行数据读取，统计了算法执行总时间。测试结果如表1所示，通过实验对比分析可以看出，本文算法数据实时调度性能优异，较单线程同步I/O算法具有更高的数据加载速度。

图6 地形绘制效果

表1 本文算法与单线程同步I/O算法的性能对比

算 法平均数据吞吐算法量/(MB/s)算法执行总时间/s路线1路线2路线3路线4路线5数据量6GB数据量3GB数据量1GB数据量500MB数据量200MB单线程同步I/O算法7．88．48．97．38．1716．2345．6114．651．119．5本文算法79．882．186．676．880．770．134．311．35．62．2

4 结束语

近年来，随着虚拟现实技术的快速发展，在实际应用中对虚拟地形环境的规模和数据精度要求越来越高。因此，本文提出了一种面向大规模虚拟地形环境的实时数据调度算法。首先，在传统的四叉树数据组织方法基础上对海量地形瓦片数据进行二次组织，并且通过基于Hilbert填充曲线的方法进行了数据的存储优化，提高了数据更新、迁移和调度的效率。此外，设计了基于IOCP的地形数据异步调度机制，实现了海量地形数据的高效管理和快速调度。由实验结果可知，本文算法具有较高的性能优势，适用于大规模虚拟地形环境的实时绘。

[1] Zhao Xuesheng, Bai Jianjun, Chen Jun, et al. A seamless visualization model of the global terrain based on the QTM[C]// Proceedings of the 16th International Conference on Advances in Artificial Reality and Tele-Existence. 2006:1136-1145.

[2] 杜莹. 全球多分辨率虚拟地形环境关键技术的研究 [D]. 郑州:解放军信息工程大学, 2005.

[3] Zhang Liqiang, Yang Chongjun, Liu Suhong, et al. Effective techniques for interactive rendering of global terrain surfaces[J]. IEEE Geoscience and Remote Sensing Letters, 2005,2(2):215-219.

[4] Ren Zijian, Ma Cunyong, Huo Peng, et al. Real-time rendering of global multiple-resolution inlaid terrain based on tessellation[J]. Journal of Computational Information Systems, 2015,10(16):5899-5909.

[5] Lebiedz J, Mieloszyk K, Wiszniewski B. Real terrain visualisation with a distributed PC-Cluster[C]// International Conference on Parallel Processing and Applied Mathematics. 2005:349-356.

[6] Hsieh T J, Kuester F, Hutchinson T. Parallel terrain rendering using a cluster of computers[J]. Journal of the Chinese Institute of Engineers, 2013,36(2):212-223.

[7] Olanda R, Pérez M, Ordua J M, et al. Terrain data compression using wavelet-tiled pyramids for online 3D terrain visualization[J]. International Journal of Geographical Information Science, 2014,28(2):407-425.

[8] 关卓威,张晔. 临近空间平台下地形四叉树优化分割算法[J]. 南京航空航天大学学报, 2015,47(1):59-63.

[9] 张立民,闫文君. 基于GPU的大规模地形数据绘制算法[J]. 计算机与现代化, 2012(1):145-150.

[10] 周艳,朱庆,张叶廷. 基于Hilbert曲线层次分解的空间数据划分方法[J]. 地理与地理信息科学, 2007,23(4):13-17.

[11] 马纯永. 城域景观VRGIS一体化仿真平台研究与实现 [D]. 青岛:中国海洋大学, 2010.

[12] Abel D J, Mark D M. A comparative analysis of some two-dimensional orderings[J]. International Journal of Geographical Information System, 1990,4(1):21-31.

[13] 陆锋,周成虎. 一种基于Hilbert排列码的GIS空间索引方法[J]. 计算机辅助设计与图形学学报, 2001,13(5):424-429.

[14] 刘向南. 海量城市三维模型网络异步调度与实时渲染算法研究[D]. 青岛:中国海洋大学, 2015.

[15] 王海玲. 虚拟自然场景建模与绘制关键技术研究[D]. 哈尔滨：哈尔滨工程大学, 2013.

[16] 周圣川. 大规模城市场景图形图像混合建模与无损渲染技术[D]. 青岛:中国海洋大学, 2014.

[17] 王早. 基于IOCP机制的代理模型与负载均衡算法研究[D]. 武汉:武汉科技大学, 2005.