CudaHull: Fast Parallel 3D Convex Hull on the GPU

Ayal Stein, Eran Geva, Jihad El-Sana
Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, Isreal
China-Israel Bi-National Conference, 2011


   title={CudaHull: Fast Parallel 3D Convex Hull on the GPU},

   author={Stein, Ayal and Geva, Eran and El-Sana, Jihad},



Download Download (PDF)   View View   Source Source   



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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: