A Hardware-Agnostic GPU Acceleration for the n-Dimensional QuickHull Algorithm

Details

Supervisors

Legat, Benoît

Faculty

Ecole polytechnique de Louvain

Degree label

Master [120] en sciences informatiques, à finalité spécialisée

Abstract

enComputing the convex hull of a point cloud is a fundamental problem in computational geometry, with widespread applications spanning computer vision, collision detection in physical simulations, and anomaly detection in high-dimensional machine learning. While various GPU-accelerated algorithms exist, they are predominantly closed-source, proprietary, and mostly constrained to three-dimensional spaces. This thesis introduces a fully open-source, hardware-agnostic, and n-dimensional parallel implementation of the Quickhull algorithm. Developed using the Julia programming language and leveraging the KernelAbstractions.jl framework, our solution ensures cross-platform compatibility across diverse GPU architectures. We design and optimize essential GPU parallel primitives specifically, multi-block reductions, scans, and segmented scans to handle the highly irregular data structures inherent to dynamic geometric topologies. Our implementation is rigorously benchmarked against the state-of-the-art CPU library, Qhull. Experimental results demonstrate substantial performance speed-ups for large datasets in lower dimensions (2D and 3D). However, as the dimensionality scales (d > 3), a performance crossover is observed where Qhull regains efficiency. We analyze the underlying geometric and architectural bottlenecks. Finally, we discuss prospective architectural enhancements to mitigate these constraints in future GPU-accelerated geometric algorithms.