0 引言

随着民航业的迅速发展, 机场噪声对周边环境的影响越来越严重。噪声等值线图能直观反映机场噪声对周边环境的影响程度和范围, 是噪声预防和治理的重要依据, 绘制机场噪声等值线图已成为机场环境评估的关键环节^[1]。现有的机场噪声等值线图大多利用综合噪声模型(integrated noise model, INM)软件绘制^[2-3], 绘制的结果只能以日、月或年平均噪声级的静态形式展现, 不能直观呈现机场噪声对周围环境的实时影响。

根据底层模型的不同, 等值线绘制算法可分为矩形网格法和不规则三角网法两类。围绕矩形网格法等值线实时快速绘制, 文献[4]将等值点存储在显存纹理, 利用索引数组, 实现基于网格的追踪算法在GPU上的加速; 文献[5]使用路径栅格链表避免等值线先开放后封闭的复杂追踪模式, 简化追踪模式的复杂度; 文献[6]基于文献[5]的追踪算法实现顶点编码和并行计算, 但顶点编码和的计算只是算法中的一个小步骤, 并行量并不大, 算法时间性能改进有限; 文献[7]运用逐行追踪的方法生成等值线, 减少内存消耗, 提升时间效率, 但仍需等值线的追踪。文献[8-11]为基于三角网的等值线绘制的改进算法, 均在不同程度上提升绘制速度, 但在三角网内仍然避免不了等值线逐点追踪的复杂和等值线逐条生成的繁琐。

综上, 不论是矩形网格法还是不规则三角网法, 其生成等值线的大体思路都是全局搜索、逐点追踪、逐条生成。这种追踪模式虽然能将等值线以等值点序列的形式表示, 方便之后的平滑和颜色填充, 但追踪过程复杂, 且存在高程值盲目搜索以及网格重复遍历等问题, 因此会增加时间开销, 而针对网格规模巨大的机场, 其无法达到15帧/s的基本绘制要求。考虑到机场噪声等值线图实时动态展现过程中, 人眼对等值线平滑程度并不敏感, 本研究不追求等值线平滑美观, 采用局部到全局策略, 基于网格模型进行改进, 提出一种等值线实时绘制算法:基于网格边标记(grid edge labeling, GEL)的等值线并行生成算法。

1 传统等值线追踪模式及其局限

传统的基于网格模型的等值线生成算法普遍采用逐点追踪的方式来生成等值线^[12-13], 这类追踪算法的大致思路如下: (1)顺序遍历网格, 计算网格边的等值点; (2)根据等值点进行非闭合等值线的追踪; (3)根据等值点进行闭合等值线的追踪; (4)根据追踪路径进行等值线平滑和绘制。

基于网格模型的追踪模式算法用于等值线实时绘制时, 主要存在以下局限:

(1) 高程值盲目搜索

需在给定的高程值范围内, 对每一个特定高程值进行等值线的追踪, 且由于特定高程值的等值线可能不止1条, 为避免遗漏, 需要对所有网格进行查找。也就是说, 假设共有10层高程值, 那么对每个网格都需进行10次遍历, 以确定该网格内是否有某特定高程值对应的等值线经过。这种全高程值、全网格的搜索策略存在盲目性, 会增加算法的时间开销。

(2) 网格重复遍历

需两次遍历网格才能生成等值线, 第1次遍历计算等值点位置, 第2次遍历追踪等值点。也正是因为有两次遍历才能完整地记录每一条等值线的路径, 同时也方便之后等值线的平滑。网格重复遍历事实上是以增加时间开销为代价, 使得等值线更加平滑美观。

(3) 难以实现等值线并行绘制

等值线的追踪主要通过当前网格单元的等值线走向确定其下一个进入的网格单元, 即网格间追踪过程只能串行进行, 因此无法将单个网格的处理作为并行任务单元。又因为同一个网格内可能有多条等值线经过, 不同等值线绘制可能会访问同一个网格, 也不能将单条等值线的绘制作为并行任务单元。因而在等值线追踪模式的基础上难以实现等值线的并行绘制。

2 基于GEL的等值线并行生成

基于GEL的等值线并行生成算法包括以下3个关键步骤。

2.1 高程值搜索范围的过滤

过滤高程值搜索范围可以解决高程值盲目搜索问题。假设拟绘制的噪声等值线为50~110 db, 间距为5 db, 如果某网格4个顶点的噪声为71、81、86、89 db, 则围绕该网格的等值线绘制只需考虑75、80、85 db这3层等值点的判断和计算, 无需遍历50~110 db的每一层。为此, 提出高程值搜索范围过滤算法, 见算法1。该算法将有效过滤高程值H的遍历范围。

算法1  高程值搜索范围过滤算法

输入  4个顶点的噪声值、拟绘制噪声的最大值H_max和最小值H_min, 噪声间距d。

输出  该网格内高程值搜索实际最小值H_bottom和最大值H_top。

(1) 对4个顶点噪声值进行排序, 将最大值记为max, 最小值记为min。

(2) 若min>H_min, 则H_bottom=⌈min÷d⌉×d, 否则H_bottom=H_min。

(3) 若max < H_max, 则H_top=max, 否则H_top=H_max。

2.2 基于GEL的等值线绘制 2.2.1 GEL算法提出

为避免网格的重复遍历, 实现一次遍历即可计算等值点并绘制等值线线段, 提出GEL算法。其基本思想是顺序遍历4条边, 对每条边进行相应的边标记, 根据边标记的和判断网格类型, 直接在各个网格的内部绘制等值线线段。

2.2.2 GEL算法描述

GEL算法包括两步:计算边标记的和, 绘制等值线线段。为方便说明, 给出单元网格图, 见图 1。

(1) 计算边标记的和

为确定网格所属类型, 需先求出边标记的和, 见算法2。算法2中:m₁、m₂、m₃、m₄表示4个点的噪声值与当前高程值H的差值, 若差值为0, 则在差值上加一个很小的数σ。a_.e、b_.e、c_.e、d_.e分别表示4条边的标记值, S表示4个标记值的和。

算法2  GEL求和算法

输入  m₁、m₂、m₃、m₄。

输出  S。

(1) a_.e=0, b_.e=0, c_.e=0, d_.e=0, S=0;//初始;

(2) for i=1 to 4;    //循环处理4条边

(3) case i of;

(4)   case 1: i==1    //处理a;

(5)     if m₁×m₂ < 0, then;

(6)     {if a_.e==0, then;

(7)       {计算a上等值点的位置; };

(8)     令a_.e=1;};

(9)   case 2: i==2    //处理b;

(10)     if m₂×m₃ < 0, then;

(11)     {计算b上等值点的位置, 令b_.e=2;};

(12)   case 3: i==3    //处理c;

(13)     if m₃×m₄ < 0, then;

(14)       {计算c上等值点的位置, 令c_.e=4;};

(15)   case 4: i==4    //处理d;

(16)     if m₄×m₁ < 0, then;

(17)     {if d_.e==0, then;

(18)       {计算d上等值点的位置; };

(19)     令d_.e=8;};

(20) end case;

(21) end for;

(22) S=a_.e+b_.e+c_.e+d_.e。

算法2中, 若计算a的等值点位置如算法2(1)所示, b、c、d边的计算方法类同。

$ \left\{ \begin{array}{l} x = \frac{{\left( {{x_2}-{x_1}} \right)}}{{\left( {{v_2}-{v_1}} \right)}} \times \left( {H-{v_1}} \right) + {x_1}\\ y = {y_1} = {y_2} \end{array} \right., $

(1)

其中:x为横坐标, y为纵坐标, v为点的噪声值, 下标1和2分别表示点P₁和P₂。

在GEL求和算法中, 为避免公共边为a和d的等值点重复插值计算, 对标记值a_.e和d_.e进行进一步判断。需要说明的是在按行优先的顺序遍历网格的过程中, 不可能存在对b和c的重复遍历, 故无需再次判断标记值是否为0。

(2) 绘制等值线线段

按照等值线在网格内的走向, 可将网格分为8种类型, 见图 2, 根据不同的S进行等值线线段的绘制。

当S=15时, 网格会存在二义性的问题, 并且网格内等值线可能交叉^[14], 此时需计算中心点的噪声

$ {v_{\rm{c}}} = \frac{{\left( {{v_1} + {v_2} + {v_3} + {v_4}} \right)}}{4}。$

(2)

若H>v_c且H < v₁, 则选择图 2(g)所示网格类型, 否则选择图 2(h)所示网格类型。

2.3 并行任务单元的设计

设计并行任务需要分析算法中的循环处理部分。通常循环处理是程序执行过程中蕴含并行性最丰富的一种操作, 也往往是程序执行最耗时的部分^[15]。本研究算法采用从局部生成到全局生成的策略, 需对网格进行顺序处理并绘制等值线线段, 因此顺序处理网格这个循环体是算法中蕴含并行性最丰富的部分。又由于网格间具有公共边, 所以如何解耦网格间的关系才是选择并行任务单元、设计并行处理算法的关键。

本研究算法采用单机多核并行机制, 将所有的网格以行为单位进行划分, 将k行网格作为一个并行任务单元, 为其分配一个CPU内核, 每个并行任务单元逐行遍历处理每个网格, 其中k值等于网格的总行数除以CPU内核数。

需要注意的是, 虽然这样的并行任务单元间会有公共横边, 但这并不会影响并行任务的处理, 这是因为划分后的任务按行遍历, 每个任务都会先从第一行开始, 在处理每个任务的最后一行时, 与该任务有公共横边的并行任务的第一行网格已经处理完。考虑到机场噪声网格数据规模巨大这一特性, 每个任务不可能只有一行网格, 从而避免对存在公共横边的网格的同时处理。

3 算法实现 3.1 规则网格的表示

不失一般性, 一个规则的网格由水平方向和竖直方向上的等间距的点构成, 为方便网格的顺序处理, 分别用P[i, j]、P[i, j+1]、P[i+1, j]、P[i+1, j+1]表示网格单元(i, j)的4个顶点, 用E[2×i, j], E[2×i+1, j+1], E[2×i+2, j], E[2×i+1, j]表示网格的上、右、下、左4条边, 见图 3。

3.2 算法的并行实现步骤

基于GEL的机场噪声等值线并行生成算法的步骤如下:

(1) 生成机场噪声网格阵列。读取噪声网格数据, 将所有网格顶点信息保存在二维阵列点P[][]中, 构造相应的二维等值点阵列E[][], 用来记录网格边上等值点的信息和边标记。

(2) 划分并行任务。根据CPU内核个数和网格的总行数对等值线生成任务进行划分, 为每一个并行任务启动一个线程并为其分配不同的CPU内核。

(3) 处理并行任务单元。顺序处理当前并行任务单元中的网格, 对每个网格依次进行高程值搜索范围的过滤, 利用GEL算法求和并绘制等值线。并行任务单元处理的具体流程见图 4, 其中:k表示并行任务单元中网格的行数, n表示网格的列数, i表示网格的行号, j表示网格的列号。

(4) 等待所有并行任务的线程执行结束, 绘制等值线完毕。

4 试验

试验所用噪声网格数据是根据某机场实际航迹信息通过INM软件计算得到的, 共选取6组分别为100×100个、200×200个、400×400个、800×800个、1 000×1 000个、1 200×1 200个的噪声网格数据, 选取噪声为40~110 dB, 噪声间隔为1、2、5 dB, 根据噪声范围和噪声间隔产生的噪声为分别为71、36、15层。试验机器配置:Intel(R) Xeon(R) CPU E5-1603 V4@2.8GHz 2.8 GHz, 4核, 8 G内存, 操作系统为Win7旗舰版。

由于本研究算法是一种多核并行处理的模式, 为对比分析, 试验中首先利用单核串行方式与其他算法进行比较, 然后再将单核串行方式与多核并行方式进行比较。本研究算法在单核串行方式下无需任务划分, 直接顺序处理网格即可。

如表 1所示, 4种算法在6组不同规模数据集上的时耗。试验中的其他算法还包括算文献[16]介绍的传统基于网格模型的等值线追踪算法和文献[5]介绍的基于路径栅格的等值线追踪算法。从表 1可以看出, 本研究算法单核串行方式相对于文献[16]算法和文献[5]算法而言在时间性能方面已经有较明显的提升, 这一方面是由于基于GEL的等值线绘制采用边计算边绘制的方式, 可避免对网格的两次遍历; 另一方面是由于高程值搜索范围的过滤可缩减等值线的搜索范围。正因后一方面的原因, 当噪声层数成倍增加后, 本研究算法的耗时并没有像其他基准算法一样成倍增加。

表 2为在不同规模网格和不同噪声层数下本研究算法并行方式相对于串行方式的加速比。当网格规模较小时, 加速比小于1, 这一方面是由于图形设备接口(graphics device interface, GDI)拥有线程安全机制, 在调用GDI绘图时需要互斥地访问GDI, 从而导致多个进程等待一个资源的现象, 增加时耗; 另一方面是由于并行算法需要对资源进行分配, 这也需要一定的时间开销。当网格为200×200个时, 加速比开始达到1, 而在网格为1 200×1 200个时加速比达到3.8, 出现这种现象是由于随着网格规模的扩大, 利用GEL算法求和计算量增大, 而互斥绘制和资源准备的时间较计算时间而言相对比例低, 因而更能充分使用多个CPU, 最终使得加速比提升。在网格规模确定的情况下, 噪声层数的成倍增加并不会对加速比造成特别大的影响, 主要原因在于本研究算法实现对高程值搜索范围的过滤, 可避免对高程值的盲目搜索, 由于噪声层数增加、间隔减小, 增加的时间开销主要集中在对新增等值线的生成上。

图 5为本研究算法在200×200个网格、15层噪声的条件下绘制的噪声等值线图, 从图 5可看出, 即使在特别密集的区域, 等值线仍符合其基本特点^[17]。噪声分布清晰可见, 越接近机场的地方, 噪声分布越密集, 噪声也越大; 随着距离机场越来越远, 噪声也越来越小。从整体效果来看, 本研究算法在等值线绘制时间性能改善的情况下几乎没有损伤等值线的平滑和美观程度。

5 结论

根据不同的环境, 需采用不同的等值线绘制算法^[18-22], 为实现机场噪声等值线图的动态展现, 提出一种基于GEL的机场噪声等值线并行生成算法。该算法打破传统等值线生成的追踪模式, 利用高程值搜索范围的过滤和边标记网格解决高程值盲目搜索和网格重复遍历的问题, 并通过并行任务单元的合理切分实现等值线在网格中的并行生成, 有效提高等值线生成速度。试验结果表明, 本研究算法在几乎不影响等值线平滑美观度的基础上很大程度上提高等值线绘制效率, 满足机场噪声可视化的实时性需求。该方法在实时性要求高且网格规模大的环境条件下有很好的适用性。