In this paper, we present a novel parallel algorithm for computing the convex hull of a set of points in 3D using the CUDA programming model. It is based on the QuickHull approach and starts by constructing an initial tetrahedron using four extreme points, discards the internal points, and distributes the 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, because it requires a very small fraction of the execution time (approximately 1%), and the intensive point redistribution is performed in parallel on the GPU. Our implementation outpaced the CPU-based Qhull implementation by 30 times for 10 million points and 40 times for 20 million points.
We have presented a 3D convex-hull-construction algorithm using the CUDA programming model. It is similar to Quick Hull, in that it starts with an initial polyhedron constructed using four extreme points, discards internal points, and redistributes the remaining points among the faces. It then proceeds iteratively. In each iteration, our algorithm reines the faces, discards the internal points, and redistributes the remaining points in parallel. Our experiments on various data sets of different sizes revealed that face refinements and edge swaps consume a very small fraction of the execution time.
Ayal Stein, Eran Geva, Jihad El-Sana, CudaHull: Fast parallel 3D convex hull on the GPU, Computers & Graphics, Volume 36, Issue 4, June 2012, Pages 265-271, [DOI: 10.1016/j.cag.2012.02.012] [Free PDF]