A GPU Algorithm for 3D Convex Hull

Mingcen Gao, Thanh-Tung Cao, Ashwin Nanjappa, Tiow-Seng Tan, Zhiyong Huang
National University of Singapore
ACM Transactions on Mathematical Software, 2012


   title={A GPU Algorithm for 3D Convex Hull},

   author={Gao, M. and Cao, T.T. and Nanjappa, A. and Tan, T.S. and Huang, Z.},



Download Download (PDF)   View View   Source Source   



A novel algorithm is presented to compute the convex hull of a point set in R3using the graphics processing unit (GPU). By exploiting the relationship between the Voronoi diagram and the convex hull, the algorithm derives the approximation of the convex hull from the former. The missed points are found back by using a two-round checking in digital and continuous space successively. The algorithm does not need explicit locking or any other concurrency control mechanism, thus it can maximize the parallelism available on the modern GPU. The implementation using the CUDA programming model on Nvidia GPUs is robust, exact, and efficient. The experiments show that it is up to an order of magnitude faster than other sequential convex hull implementations running on the CPU for inputs of millions of points. The works demonstrate that the GPU can be used to solve non-trivial computational geometry problems with significant performance benefit, without sacrificing accuracy or robustness.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: