3D Delaunay Triangulation on the GPU

Ashwin Nanjappa, Thanh-Tung Cao, Mingcen Gao and Tiow-Seng Tan

School of Computing, National University of Singapore


Abstract

We present the first 3D Delaunay triangulation algorithms that effectively utilize the massive parallelism of the GPU.

The gDel3D algorithm 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 10 times over the 3D Delaunay triangulator of CGAL. Following the same approach (less the need for star splaying), the gDel2D algorithm constructs the 2D Delaunay triangulation on the GPU; it also uses flipping to further insert constrained edges.

As another approach, the gStar4D algorithm uses the neighbourhood information in the digital Voronoi diagram to approximate the Delaunay triangulation. It then performs massively parallel creation of stars of each input point lifted to 4D space, and employs a unique star splaying approach to splay these 4D stars in parallel and make them consistent. The algorithm runs completely on the GPU. Our CUDA implementation of gStar4D achieves a speedup of up to 5 times over the 3D Delaunay triangulator of CGAL. We also extend the star splaying concepts of gStar4D 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.

Downloads

Related Projects


© 2014 School of Computing, National University of Singapore, 22 January 2014, August 2014, Oct 2015