Paper Info
Title
A GPU accelerated algorithm for 3D Delaunay triangulation
Abstract
We propose the first algorithm to compute the 3D Delaunay triangulation (DT) on the GPU. Our algorithm uses massively parallel point insertion followed by bilateral flipping, a powerful local operation in computational geometry. Although a flipping algorithm is very amenable to parallel processing and has been employed to construct the 2D DT and the 3D convex hull on the GPU, to our knowledge there is no such successful attempt for constructing the 3D DT. This is because in 3D when many points are inserted in parallel, flipping gets stuck long before reaching the DT, and thus any further correction to obtain the DT is costly. In contrast, we show that by alternating between parallel point insertion and flipping, together with picking an appropriate point insertion order, one can still obtain a triangulation very close to Delaunay. We further propose an adaptive star splaying approach to subsequently transform this result into the 3D DT efficiently. In addition, we introduce several GPU speedup techniques for our implementation, which are also useful for general computational geometry algorithms. On the whole, our hybrid approach, with the GPU accelerating the main work of constructing a near-Delaunay structure and the CPU transforming that into the 3D DT, outperforms all existing sequential CPU algorithms by up to an order of magnitude, in both synthetic and real-world inputs. We also adapt our approach to the 2D DT problem and obtain similar speedup over the best sequential CPU algorithms, and up to 2 times over previous GPU algorithms.
Year
DOI
Venue
2014
10.1145/2556700.2556710
I3D
Keywords
Field
DocType
gpu speedup technique,delaunay triangulation,appropriate point insertion order,previous gpu algorithm,hybrid approach,parallel point insertion,general computational geometry algorithm,sequential cpu algorithm,existing sequential cpu algorithm,dt problem,gpgpu
Bowyer–Watson algorithm,Computer graphics (images),CUDA,Computer science,Computational geometry,Parallel computing,Algorithm,Convex hull,Triangulation (social science),General-purpose computing on graphics processing units,Speedup,Delaunay triangulation
Conference
Citations 
PageRank 
References 
6
0.46
15
Authors
4
Name
Order
Citations
PageRank
Thanh-Tung Cao11457.31
Ashwin Nanjappa2100.87
Mingcen Gao3192.07
Tiow-Seng Tan439827.99