high performance computing on graphics processing units: hgpu.org

In this paper we present a novel parallel algorithm for computing the convex hull of a set of points in 3D using CUDA programming model. It is based on the QuickHull approach and starts by constructing an initial tetrahedron using four extreme points, discards internal points, and distributes external points to the four faces. It then proceeds iteratively. In each iteration it refines the faces of the polyhedron, discards the internal points, and redistributes the remaining points for each face among its children faces. The refinement of a face is performed by selecting the furthest point from its associated points and generating three children triangles. In each iteration concave edges are swapped and concave vertices are removed to maintain convexity. The face refinement procedure is performed on the CPU, as it takes very small fraction of the execution time (around 1%), and the intensive point redistribution is performed in parallel on the GPU. Our implementation outpaced the CPU-base Qhull implementation by 30 time for 10 million points and 40 times for 20 million points.