Please use this identifier to cite or link to this item:
Title: A GPU accelerated algorithm for 3D Delaunay triangulation
Authors: Cao, T.-T.
Nanjappa, A.
Gao, M.
Tan, T.-S. 
Keywords: Bilateral flipping
Delaunay triangulation
Incremental insertion
Star splaying
Issue Date: 2014
Citation: Cao, T.-T.,Nanjappa, A.,Gao, M.,Tan, T.-S. (2014). A GPU accelerated algorithm for 3D Delaunay triangulation. Proceedings of the Symposium on Interactive 3D Graphics : 47-54. ScholarBank@NUS Repository.
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. Copyright © ACM.
Source Title: Proceedings of the Symposium on Interactive 3D Graphics
ISBN: 9781450327176
DOI: 10.1145/2556700.2556710
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Nov 16, 2018

Page view(s)

checked on Oct 27, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.