Finding Convex Hulls Using Quickhull on the GPU

Stanley Tzeng, John D. Owens
University of California, Davis
arXiv:1201.2936v1 [cs.CG] (13 Jan 2012)


   author={Tzeng}, S. and {Owens}, J.~D.},

   title={"{Finding Convex Hulls Using Quickhull on the GPU}"},

   journal={ArXiv e-prints},




   keywords={Computer Science – Computational Geometry, Computer Science – Data Structures and Algorithms, Computer Science – Graphics},




   adsnote={Provided by the SAO/NASA Astrophysics Data System}


Download Download (PDF)   View View   Source Source   



We present a convex hull algorithm that is accelerated on commodity graphics hardware. We analyze and identify the hurdles of writing a recursive divide and conquer algorithm on the GPU and divise a framework for representing this class of problems. Our framework transforms the recursive splitting step into a permutation step that is well-suited for graphics hardware. Our convex hull algorithm of choice is Quickhull. Our parallel Quickhull implementation (for both 2D and 3D cases) achieves an order of magnitude speedup over standard computational geometry libraries.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: