genrec_blog
Panfeng Cao/

Accelerating 3D Convex Hull Computation with the Quickhull Algorithm on the GPU

5 min read

Introduction

This project leverages a GPU-accelerated Quickhull algorithm to compute the convex hull of a 3D point set, optimizing computational speed by executing in parallel on an NVIDIA GTX 960M. Utilizing CUDA 8.0 and the Thrust library, the algorithm achieves significant efficiency gains across various point distributions, such as cuboid and sphere samples. Convex hull computation is crucial in various fields, and its parallelizable nature makes it suitable for GPU implementation. The Quickhull algorithm, adapted to divide-and-conquer operations on the GPU, processes the convex hull efficiently with minimized CPU-GPU interaction.

Algorithm and Implementation

Divide and Conquer with Quickhull on the GPU

The GPU-based Quickhull approach utilizes the divide-and-conquer technique through the Thrust library, which simplifies array operations and enables massive parallelism. Core functions include Flag Permute and Compact, which handle segmentation and point permutation for efficient convex hull calculation.

Flag Permute

The flagPermute function groups points into segments based on their state values. Each point is flagged and rearranged into segments, with permutation positions calculated via forward and backward scans.

Compact

The compact function removes points deemed unnecessary for the convex hull, improving performance by focusing on key points only. It rearranges segments based on boolean values, filtering out redundant points and segments.

Results and Analysis

Experiment was performed on two datasets: cuboid and sphere point samples.

hull_example_1
Cuboid Convex Hull
hull_example_2
Sphere Convex Hull
hull_cube_perf
Performance for Cuboid Convex Hull
hull_sphere_perf
Performance for Sphere Convex Hull

Experiments highlight that efficiency decreased with higher thread counts but increased as the number of points rose. The sphere point samples took longer to calculate the convex hull due to inclusion of all points.

Conclusion

This project demonstrates that while the GPU-optimized Quickhull algorithm improves performance, challenges remain in managing load balance with higher thread counts. Future work will focus on refining segment processing to further enhance parallel efficiency.

author-profile-imageAbout the article

I worked on this project when I was studying at University of Michigan. This was my final project of the Parallel Computing course.