快速凸包并行设计与研究

2018-07-13张德珍

软件 2018年6期

邵　宁，张德珍

（大连海事大学，辽宁大连　116026）

0　引言

凸包是计算几何中非常重要的几何结构，非几何的问题往往也可以抽象为几何概念并求解。因此凸包几何结构在科学研究和工程实践中有着非常广泛的应用[1-2]。三维的凸包是指包含所有输入点的最小凸包[3]。许多有关三维凸包的算法，比如，卷包裹算法[4]，是最早处理三维凸包的算法之一，分治算法算法[5]，快包算法[6]等。随着凸包的点集规模逐步增多，耗费的时间增多，无法满足人们对构造凸包时间的要求。

随着计算机的硬件和软件的不断更迭发展，从原先传统化的串行数据处理方式，转变成与GPU大规模并行处理方法相结合的方式。20世纪80年代，由于随机存取并行机器（PRAM）与串行模型相类似，大多数研究者使用的此模型设计算法。现今，依靠 GPU通用计算能力实现大规模数据处理。Srikanth,等人[7]利用并行计算对快包算法的二维凸包问题求解过程进行加速，降低处理器间通信成本。Gao等研究人员[8]提出gHull算法，运用泰森多边形初步求解出六面体内的凸多面体，最后运用Splaying算法对凸多面体再次最终形成完整凸包。Gang[9]根据原始的输入点集状态和多角度旋转后点集的状态，确定边界极值点。以此极值点创建凸多面体；最后内部点被剔除形成凸包。

本文通过对有关三维凸包的相关文献的研究，分析快速凸包算法的计算任务，将求解凸包的问题划分为可并执行的子问题。利用GPU的通用计算能力，对计算量多且可以独立的部分进行并行的任务设计。选取不同规模点集数据分别以串行和并行的方式计算构造凸包消耗的时间。从而印证快速凸包算法在时间性能上的显著提高。

1　三维快速凸包算法

1.1　凸包的相关定义

三维的凸包是指包含所有输入点的最小凸包。其定义为集合C中所有点的凸组合的集合。

集合C的凸包是能够包含C的最小的凸集。同时也是包含S的所有凸集的交。

性质 1空间中给定点集凸包是唯一的，且凸包顶点是给定点集中的点[10]。

性质2极值点必为凸包的顶点中的点。

凸多面体的构造可以描述为：三维空间条件下，对给定点集中选取若干个非线性顶点组成新的点集。顶点所构成的边界面包含给定点集且包含自身。此点集可称为凸包点集。

1.2　三维快速凸包算法

Barber[6]等人提出了快速凸包算法，此算法是以随机增量算法为基础上进行改进的算法，能够在三维和高维空间上应用。相较于其他构建三维凸包算法，此算法初始阶段大幅度的排除非凸包点而不是逐个或者小部分排除。通过实验证明快速凸包算法比随机增量算法的速度更快，需要的存储空间更小，算法的平均复杂度为 O(nlogn)，最坏情况下的复杂度为O(n2)[6]。算法流程：

步骤 1：初始化四个顶点构成的四面体。以坐标X轴方向选取正反方向两个极值点构成线段。然后选取距离线段最远的点形成平面，再取距离平面最远的点。这四个极值点构成初始的凸多面体，且极值点为非退化的极值点。

步骤 2：存储每个面的数据结构。对于四面体的每个面F，遍历点集，找到所有在面F上方的点，保存面F的外部点集中，每个面结构都记录有一个外部点集，把外部点集非空的面保存在一个集合中，称这个集合为待定面集。

步骤3：面F的外部点集中找到与面F距离最远的点p，并且把点p从面F的外部点集中移除。

步骤4：初始可见面集V，且V中每个面中的未被访问过的邻居面N，如果点p在面N的上方，把N加到集合V中。然后把集合V中每个面的外部点集集中在点集L中。

步骤5：集合V中所有可见面的临界边，构成一个集合 V。连接点和集合中的边界边，创建出新的面，更新新的面的相邻面。

步骤 6：对于每个新的面 F′，遍历点集 L，如果对于点集L中未分配的点q，它在F′的上方，则把它添加到面F′的外部点集中。若待定面集Q和可见面集V的交不为空，则从待定面集Q中移除它们的交集。

最后，对于每个新的面F′，若它的外部点集非空，则把它添加到待定面集Q中，进行下次的迭代。

与平面点集相比较，三维空间构造凸包构造过程和计算较为复杂。在构建初始化凸多面体后按照步骤开始迭代，直至所有点集都处理完毕。计算任务相互独立，耦合性较低使得算法可以充分并行展开。

2　基于CUDA快速凸包算法的实现

2.1　三维快速凸包算法并行性分析

快速凸包算法易于理解，对以上步骤分析可知。步骤1求极值点初始化四面体，步骤2区分各个小平面点集是内部点或者外部点的过程和步骤3求可见面的最远极值点是可以独立的部分，耦合性较低。步骤2和步骤3部分所完成的计算任务是全部程序中计算任务中的大部分，耗费时间比较长，尤其是数据规模较大的情况下。以上过程可以高度并行处理，且运用空间几何方法进行判断和操作。并由其中大量的计算单元同时对点集进行计算，从而缩短处理时间。

2.2　基于CUDA快速凸包算法的实现

快速凸包算法在并行上可以分为两个部分。一部分是大量的离散点中按照相应的坐标求取极值点构建初始的四面体。另一部分是将点集按照凸包上的小平面进行分割，然后求取离可见面所对应最远的距离的极值点。

本文中，利用CUDA并行编程模型随快速凸包算法进行重构。首先将点集传输到设备内存中，其次多线程运用不同的数据执行相同的指令来寻找到点集中的四个极值点，然后将极值点传回主机端构建初始化四面体，剔除内部点。将剩余的点集重新依照新的小平面进行分配。在分配好的点集中选出距离小平面最远的极值点，极值点与相应的小平面的边相连组成新的四面体，并且判断点是否在凸包外，如果分布于内侧则剔除。此四面体与原先凸包结合。进行迭代直至所有的外部点都处理过。整个过程结束。

在设备端，调用核函数完成计算量多的并行计算部分。线程网格与线程块的维度依据点集数据和图形处理器所能够承载的数目进行分配(点集数据+线程块数量-2)/线程块数量。实践过程中线程块的数目设置为32的倍数。有文献表明当线程取512时，设备端的占有率实现最大化。合理的对所调用的内核函数线程块和线程维度分配，大幅度缩短因访存导致的时间消耗与延迟。每一个线程块处理以相同的操作来处理部分点集。由于数据存储于全局变量中，存取过程耗时较长，因此利用共享内存实现线程之间的块内通信减少通信访问开销，访存效率得到明显的改善。

计算相对小平面的极值点时，先将点按照小平面顺序进行排序，然后再根据距离远选取。这里利用了归约求和的思想。其思想是对于一个输入数组执行加法运算，产生更小的结果数据，将数据按照规则合并。

每次归约运算位于目前所有线程的一半线程，循环执行，最终在初始线程中得到最终用结果。这种归约方式改进了数据访问不对齐，多线程执行计算的问题。计算大量离散点集情况下降低执行的消耗时间，有效的排除凸包内部点。程序优化的另一方面是，通过原子操作保证每个线程互斥地访问全局存储或共享存储上的计算结果，避免并行程序总多个线程同时修改某一变量出现冲突问题。最终将相应平面的极值点从GPU传回到CPU中以进行接下来的操作。

3　实验结果及分析

本文基于 CUDA实现计算几何的快速凸包算法，通过不同点集数据量的复杂几何模型分别按照串行算法和并行算法进行实验且对数据分析和对比，如下图。实验结果表明利用GPU实现算法能够将算法速度达到几倍的加速。输入点集规模较大时算法加速有着明显的提高。

实验设备参数CPU采用Intel i7处理器，GPU为 Quadro k3100M，线程块的最大线程数为1024。实验选取的三维模型为斯坦福大学大型模型几何库和其他三维几何模型。

图1　实验的三维模型与构造后的凸包Fig.1　3D model and convex hull

表1　快速凸包算法在CPU与GPU性能表现Tab. 1　The performance comparison of quickhull algorithm base on CPU and CUDA

从表中可以看出，数据量较少的的情况下，基于CPU和基于GPU的快速凸包算法时间性能上比较接近。随着实验点集数据的增多，对于不同平台上实验所消耗的时间差距不断扩大。三维模型点集数量越多，CPU构建凸包所消耗的时间成线性增长趋势，而与此同时GPU消耗的时间方面基本持平，时间消耗不明显。在CUDA上实现快速凸包算法处理的速度远超过CPU构建凸包的速度。模型点集规模数量较多时，有着明显的加速效果和优势。