Finding Convex Hulls Using Quickhull on the GPU
Skip to main content
eScholarship
Open Access Publications from the University of California

Finding Convex Hulls Using Quickhull on the GPU

  • Author(s): Tzeng, S
  • Owens, JD
  • et al.

Published Web Location

http://arxiv.org/abs/1201.2936v1
No data is associated with this publication.
Abstract

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.

Many UC-authored scholarly publications are freely available on this site because of the UC Academic Senate's Open Access Policy. Let us know how this access is important for you.

Item not freely available? Link broken?
Report a problem accessing this item