邵　宁，张德珍

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

0　引言

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

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

本文通过对有关三维凸包的相关文献的研究，分析快速凸包算法的计算任务，将求解凸包的问题划分为可并执行的子问题。利用GPU的通用计算能力，对计算量多且可以独立的部分进行并行的任务设计。……