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.
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.