A 3D Convex Hull Algorithm for Graphics Hardware

hgpu.org » Programming » Algorithms » A 3D Convex Hull Algorithm for Graphics Hardware

A 3D Convex Hull Algorithm for Graphics Hardware

Mingcen Gao, Thanh-Tung Cao, Tiow-Seng Tan, Zhiyong Huang

National University of Singapore

National University of Singapore, Technical Report, 2011

@article{gao20113d,

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

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

year={2011}

}

View

Download (PDF)

Source

Source codes

Package:

3DConvexHull

This report presents a novel approach, termed gHull, to compute the convex hull for a given point set in R3 using the graphics processing units (GPUs). While the 2D problem can easily and efficiently be solved in the GPU, there is no known obvious, classical parallel solution that works well in the GPU for the 3D problem. Our novel parallel approach exploits the relationship between the 3D Voronoi diagram and the 3D convex hull so as to maximize the parallelism available in the GPU to compute the answer from the former rather than directly. Our implementation of the approach using the CUDA programming model on nVidia GPUs shows that it is robust and efficient. Our experiment shows that gHull runs up to 10x faster than the fastest CPU convex hull software, QuickHull, on inputs with millions of points.

Tags: Algorithms, Computer science, CUDA, nVidia, nVidia GeForce GTX 460, OpenGL, Package, Voronoi diagram

December 31, 2011 by hgpu

GD Star Rating
loading...

Most viewed papers (last 30 days)

* * *

Recent source codes

Events

May 18-21, 2014

Denver, USA

ACM SIGSIM Conference on Principles of Advanced Discrete Simulation, ACM SIGSIM PADS 2014

March 17-19, 2014

Lisbon, Portugal

7th International ICST Conference on Simulation Tools and Techniques, SIMUTools 2014

June 26, 2013 9:00 AM - 10:00 AM PDT

Understanding Dynamic Parallelism at Any Scale with Allinea's Unified Tools (webinar)

June 4, 2013 10:00 AM - 11:00 AM PDT

CUDA 5.5 Features and Release Candidate (RC) program (webinar)

June 20, 2013 9:00 AM - 10:00 AM PDT

GPU Accelerated XenDesktop for Designers and Engineers (webinar)

* * *

Free GPU computing node at hgpu.org

Registered users can now run their OpenCL application at hgpu.org. We provide 1 minute of computer time per each run on two nodes with two AMD and one nVidia graphics processing units, correspondingly. There are no restrictions on the number of starts.

The platforms are

Node 1

GPU device 0: AMD/ATI Radeon HD 5870 2GB, 850MHz
GPU device 1: AMD/ATI Radeon HD 6970 2GB, 880MHz
CPU: AMD Phenom II X6 @ 2.8GHz 1055T
RAM: 12GB
HDD: 2TB, Raid-0
OS: OpenSUSE 11.4
SDK: AMD APP SDK 2.8

Node 2

GPU device 0: AMD/ATI Radeon HD 7970 3GB, 1000MHz
GPU device 1: nVidia GeForce GTX 560 Ti 2GB, 822MHz
CPU: Intel Core i7-2600 @ 3.4GHz
RAM: 16GB
HDD: 2TB, Raid-0
OS: OpenSUSE 12.2
SDK: nVidia CUDA Toolkit 5.0.35, AMD APP SDK 2.8

Completed OpenCL project should be uploaded via User dashboard (see instructions and example there), compilation and execution terminal output logs will be provided to the user.

The information send to hgpu.org will be treated according to our Privacy Policy

hgpu.org

high performance computing on graphics processing units