Spatial Searching on GPU for CGAL

This project investigates GPU-accelerated approaches for spatial searching and mesh intersection in CGAL, a widely used computational geometry library. These operations are fundamental to applications such as collision detection, mesh processing, and geometric querying, but are currently limited by CPU-based performance, especially for large or dense datasets. The core idea is to leverage the massive parallelism of GPUs to accelerate the broad-phase of spatial queries, where potential interacting primitive pairs are identified. These candidate pairs are then refined using CGAL’s exact geometric predicates to preserve robustness and correctness. The project will explore multiple architectural designs, including hybrid GPU–CPU pipelines, fully GPU-based approaches, and alternative spatial data structures such as bounding volume hierarchies and spatial grids. An initial exploration phase will compare these approaches across diverse input configurations (e.g., overlapping vs non-overlapping meshes) to identify the most effective design. The final outcome will be a modular and reusable GPU-accelerated spatial searching framework integrated with CGAL. Deliverables include a prototype implementation of selected GPU-based spatial data structures, a candidate pair generation system, integration with CGAL’s exact predicates, and a comprehensive benchmarking suite evaluating performance, scalability, and robustness across different workloads.