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
- PhD Thesis: Delaunay Triangulation in R³ on the GPU by Ashwin Nanjappa (2012)
- Conference Paper: A GPU accelerated algorithm for 3D Delaunay triangulation in I3D 2014 presentation slides in pptx by Cao et al.
- Source code: gDel3D
- Source code: gDel2D (October 2015)
- Source code: gStar4D
- Source code: gReg3D
Related Projects
- GPU-DT: 2D Delaunay on GPU
- GPU-CDT: 2D Constrained Delaunay on GPU
- GHull: 3D Convex hull on GPU
- FlipFlop: Flip algorithm of 3D convex hull
© 2014 School of Computing, National University of Singapore, 22 January 2014, August 2014, Oct 2015