三维地形模型生成的多核并行算法*

2011-05-17郑晓薇邵英安张建强

网络安全与数据管理 2011年8期

郑晓薇，李喆，邵英安，张建强

（辽宁师范大学计算机与信息技术学院，辽宁大连116081）

计算机体系结构正向多处理器以及多核架构方向发展，多核平台应用越来越普及。因此，多核并行计算技术及其应用已成为计算机领域新的发展趋势，充分利用多核硬件可以有效提高系统应用程序的性能。计算机硬件绘图技术一直在高速发展，特别强调实时性、低延迟、稳定的图像速度以及图像清晰度，但是现有技术仍然不能满足3D场景的实时绘制。

地形是自然界最复杂的景物之一，要实时模拟具有真实感的大范围三维地形，最大的难点是如何精简并有效地组织地形数据，以达到高速度、高精确度的可视化目的。为了获得高效和理想的视觉效果和计算机处理的速度，需要采用一种技术对场景中的模型进行有效的处理。细节层次模型LOD（Level of Detail）是一种可以解决简化地形、加快渲染速度的绘制方法。然而大部分图形系统或其他类型的应用程序仍然使用单线程，这就使多核系统平台的资源并不能得到完全的利用。针对细节层次模型采用四叉树（Quad Tree）的数据结构、待处理的数据量和计算量都非常大的特点，本文提出了一种在多核计算机上基于四叉树划分的并行模型简化算法，对三维地形系统进行优化。

1 多核并行程序设计

多核并行计算技术是当前计算机领域的研究热点，在未来数年内，随着芯片内核数量持续增长，多核计算将成为一种广泛普及的计算模式[1]。要想真正获得多核处理器带来的高效率，软件的发展必须跟上硬件的步伐，而当前多核处理器软件总体滞后于硬件。多核处理器为实施计算任务的细粒度并行机制提供了必要的硬件基础，只有在算法设计及软件开发能够充分利用多核处理器的特性时，其优势才能真正体现出来。并行计算是指同时对多个任务或多条指令，或多个数据项进行处理[2]。目前适应多核处理器并行算法的可行的解决方案是多线程化计算任务，并使计算负载能尽量均衡地分配到各个内核上。而计算任务的线程化存在的两个难点是寻找任务中可并行计算成分与线程化工具的选择。

OpenMP为共享地址空间的并行计算提供支持，具有使用简单的特点。它由一组小型的编译器命令集组成，包括一套编译指令和一个用来支持它的函数库，对于同步共享变量、合理分配负载等任务，都提供了有效支持，具有简单通用、开发快速的特点。Intel Parallel Amplifier是Intel新推出的性能测试工具，使用Intel Parallel Amplifier可以简单快速找到多核性能瓶颈。生成应用程序后，用Parallel Amplifier可对多种类型函数进行分析，收集不同类型的性能数据，查看结果并深入观察造成某个问题的相关源代码。其中热点分析功能可识别出最耗时的函数以及是否有效利用了所有处理器内核。

LOD细节层次是指对同一场景或场景中的物体，使用具有不同细节的描述方法得到一组模型，供绘制时选择使用[3]。LOD层次细节简化作为一种通用而有效的四叉树算法，已在地理信息系统、虚拟现实、灾害仿真和战场环境仿真等领域中有着重要的应用。大规模地形LOD模型的预处理系统是一个完整、稳定的算法框架，内含的剖分、划点、连线等操作都是一些并行性非常强的运算过程，满足并行化的要求。在多核处理器计算环境中将这些操作进行线程并行化，可使LOD的运行效率得到极大提高，使系统资源得到充分利用。

2 LOD模型简化

为了满足大规模虚拟地形应用在渲染速度和显示分辨率等方面的要求，应采取一定的算法来简化地形数据。细节层次LOD是一种非常有效的控制场景复杂度的方法。该方法由Clark于1976年提出[4]，其基本思想是用具有多层次结构要素的集合描述目标。其基本原理是在不影响场景视觉效果的基础上，通过逐级简化景物的表面细节来减少场景的几何复杂度，以提高绘制算法的效率。当物体覆盖较小区域时，可以使用该物体描述较粗的模型并给出一个用于可见面判断算法的几何层次模型，以便对复杂场景进行快速的绘制。在场景的动态显示中，当视点距离某一物体很近时，它的图像在屏幕上占据较多的像素，而当视点距离它很远时，图像在屏幕上占据很少的像素，甚至是一个像素。在这种情况下用大量的三角形网格去精确地表示物体已经没有必要，可以适当合并一些三角形，而不损失画面的视觉效果。这样既保证场景的视觉效果，又能提高场景的绘制帧速，改善系统的实时性。

LOD建模是采用一定的算法思想将原有的网格地形数据重组，得到一种更加便于实时绘制使用的数据结构。本文所用到的LOD细节层次模型采用四叉树的数据结构，逐级划分四叉树直到某一种条件得到满足为止。在用来描述地形的数据结构中，四叉树非常有效，它的每个节点（除叶子节点外）都有4个子节点，这4个子节点平均地划分它们的父节点所占据的区域，依次类推，直到叶子节点[5]。叶子节点是渲染和贴图的最小单位。分割的深度越大，得到的分辨率就会越高，即分割深度每提高一层，采样的密度便提高一倍[6]。本文实验程序选用的四叉树的深度为8，即采样的密度为256×256个网格空间，算法空间剖分如图1所示。图中每一个正方形为四叉树的一个节点。每个节点保存了一定区域的信息，包括经纬度、中心点的高度、边节点的高度等。

3 LOD多线程并行模型生成

3.1 四叉树的构建

在利用四叉树方法进行LOD建模的过程中，其关键就在于怎样对原有的网格数据进行四叉树分层。四叉树分层方法是从整个完整的地形出发，递归地把地形不断地分割成相等的四个区域，分割的深度越大，则得到的分辨率越高。在进行四叉树分层的过程中，由于四叉树分层是针对(2n+1)×(2n+1)的规则网格而言的，数据格式应尽量满足规则网格的要求，即网格数据必须是间隔均匀的正方形区域。如果网格数据的大小不满足该条件，则需要扩展其几何图形，扩展部分的像素用空值填充。其次在四叉树分层过程中，还必须满足四叉树中相邻的两个节点的层次最大不能相差1，否则在LOD模型连续拼接的地方就会出现裂缝。其基本思路是先把地形一分为四，用递归的方法对每个网格渲染。对每个网格，如果达到最高精度，则退出，如果不在视野内也退出；再对符合条件的网格递归下去。本文实验利用OpenGL实现的地形场景渲染效果如图2所示，对应的地形网格模型如图3所示。

3.2 模型生成并行化

OpenMP应用程序接口是针对共享内存多处理器体系结构的可移植并行编程模型，能够支持并行计算时对线程和变量的灵活设置和控制。OpenMP经常用于循环层并行，但它同样支持函数层并行，在并行绘制系统中存在一些函数调用，可使用OpenMP提供的sections子句进行函数级并行化，前提是并行的函数之间无依赖性。

LOD并行模型简化算法需要考虑的因素主要是模型的剖分。对模型进行适当的剖分，从而实现各模型分块的并行简化、任务分配与负载平衡，合理的任务分配能充分发挥并行计算的优势。为了使简化后的模型在LOD显示时方便地调用，直接应用四叉树对模型进行并行剖分成为一种选择。本文采用多线程的方法在初始化阶段将地形模型进行剖分，四叉树每个叶子节点所对应的分块内的模型即为一个元任务块。每个四叉树节点对应一个任务块，由主节点按照任务分配策略将一个个元任务块发送给子节点进行并行简化。实验环境选用的是四核计算机，且采用四叉树结构对原始模型进行平均剖分；根据线程数等于CPU核数时性能最好原则，设定为4线程。在四叉树第一层剖分时把原任务块平均分成四个子块，分别独立地在四个工作区线程上完成指定深度的剖分任务，即把整个地形的工作量分配到四个处理核上同时工作。

3.3 OpenMP分块设置过程

在并行构造中，可以设置条件决定是否对可并行区域中的代码块作并行。OpenMP提供了if子句来实现条件并行。设置条件并行先给每个线程平均分配一个任务块，把整个区域的地形平均地分成四块工作区，再用if子句把地形分成四个均等的任务块。sections和section命令是OpenMP里用来设置分区的一种方式，先用sections定义一个区块，然后用section将区块划分成几个不同的段，每段都并行执行。在每一个并行区域中都会有一个隐含的同步屏障，执行此并行区域的线程组在执行完本区域代码之前需要同步并行区域的所有线程。因此要充分考虑任务分块的均衡，以免浪费CPU资源。并行划分程序部分代码如下：

4 实验结果

实验环境：Intel(R)Core(TM)2 Quad CPU Q9400@2.66 GHz(4 CPUs)，3.00 GB内存；Microsoft Visual Studio 2008，Intel Parallel Amplifier(并行放大器)，OpenGL 图形库，DirectX应用程序接口。

实验数据为256 bit×256 bit的地形高度图，以分析draw、draw_point、setup_quadtree函数为例，测出单线程、双线程和四线程的运行时间。对优化前后的结果进行比较，获得加速比和CPU效率。函数运行测试数据如表1所示，分析比较结果如图4所示。

从实验结果可以看出，四叉树算法的场景渲染函数经过多线程优化后执行时间有很大的改进，性能得到了较大的提升。总的来说，系统不仅实现了高分辨率的显示效果，而且实现了渲染速度的显著提高。将工作任务平均地分配到四个线程上，加速比和CPU利用率都得到了改进，也看出多线程程序设计对于大型三维场景创建来说是加快运行速度、提高效率的很好的方法。

表1 函数运行数据

本算法提高了三维地形场景渲染系统生成的速度，实现了高真实度的三维地形场景的可视化和快速漫游，并采用了OpenGL编程实现了这个算法。通过实验说明了该方法充分利用了多核平台的优势，有效提高了系统的性能。在LOD技术中，多核平台的应用将越来越广泛，还有很多内容需要进一步研究，例如物体表面属性色彩、纹理等的统一处理，多分辨率模型的管理，视点和视区有关的LOD生成和绘制算法，模型近似误差度量标准以及多分辨率模型简化的并行化研究等，因此本文的方法具有广阔的应用前景。