I work on computational geometry algorithms for the GPU. My PhD thesis is on massively parallel algorithms to construct the 3D Delaunay and regular triangulations on the GPU. These algorithms have been implemented using CUDA and tested on NVIDIA GPUs.
Delaunay triangulation in R³ on the GPU
Ashwin Nanjappa, "Delaunay triangulation in R³ on the GPU", PhD thesis, School of Computing, National University of Singapore, 2012.
We present the first 3D Delaunay triangulation and 3D regular triangulation algorithms that effectively utilize the massive parallelism of the GPU.
The gStar4D algorithm uses the neighbourhood information in the digital Voronoi diagram as an approximation of the Delaunay triangulation. It uses this to perform massively parallel creation of stars of each input point lifted to R4 and employs an unique star splaying approach to splay these 4D stars in parallel and make them consistent. Our CUDA implementation of gStar4D achieves a speedup of up to 5 times over the 3D Delaunay triangulator of CGAL.
The gDel3D is a hybrid GPU-CPU algorithm that performs massively parallel point insertion and flipping on the GPU to obtain a nearly-Delaunay triangulation. It then repairs this on the CPU using a conservative star splaying approach to obtain the 3D Delaunay triangulation. Our implementation of gDel3D achieves a speedup of up to 6 times over the 3D Delaunay triangulator of CGAL.
We extend the star splaying concepts of gStar4D and gDel3D algorithms to devise the gReg3D algorithm that can construct the 3D regular triangulation on the GPU. This algorithm allows stars to die, finds their death certificate and uses methods to propagate this information to other stars. Our implementation of gReg3D achieves a speedup of up to 4 times over the 3D regular triangulator of CGAL.