Article ID Journal Published Year Pages File Type
442030 Computers & Graphics 2012 7 Pages PDF
Abstract

In this paper, we present a novel parallel algorithm for computing the convex hull of a set of points in 3D using the CUDA programming model. It is based on the QuickHull approach and starts by constructing an initial tetrahedron using four extreme points, discards the internal points, and distributes the 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, because it requires a very small fraction of the execution time (approximately 1%), and the intensive point redistribution is performed in parallel on the GPU. Our implementation outpaced the CPU-based Qhull implementation by 30 times for 10 million points and 40 times for 20 million points.

Graphical abstractFigure optionsDownload full-size imageDownload high-quality image (80 K)Download as PowerPoint slideHighlights► Parallel Algorithm for constructing the convex hull of a set of points in 3D using CUDA. ► It is based on the QuickHull approach. ► Our implementation is 30–40 times faster that the CPU-based Qhull implementation.

Related Topics
Physical Sciences and Engineering Computer Science Computer Graphics and Computer-Aided Design
Authors
, , ,