Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/38747
Title: Delaunay triangulation in R3 on the GPU
Authors: ASHWIN NANJAPPA
Keywords: Delaunay triangulation, GPU, computational geometry, parallel computing, algorithms, star splaying
Issue Date: 28-Nov-2012
Source: ASHWIN NANJAPPA (2012-11-28). Delaunay triangulation in R3 on the GPU. ScholarBank@NUS Repository.
Abstract: This thesis presents massively parallel algorithms to compute the 3D Delaunay triangulation efficiently and robustly on the GPU. Our CUDA implementations of these algorithms obtain a speedup of up to 6 times over comparable methods. gDel3D is a heterogeneous GPU-CPU algorithm that performs massively parallel insertion and flipping on the GPU to compute a nearly-Delaunay triangulation. It fixes this result on the CPU using a conservative star splaying approach to obtain 3D Delaunay. gStar4D is a GPU algorithm that uses the neighbourhood information in the digital Voronoi diagram to create stars of each input point on the GPU. It uses an unique star splaying approach to splay these 4D stars in parallel, make them consistent and extract the 3D Delaunay result. This thesis also shows that these techniques can be adapted to solve other computational geometry problems in R3 and R4 using the GPU.
URI: http://scholarbank.nus.edu.sg/handle/10635/38747
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
AshwinNanjappa.pdf5.23 MBAdobe PDF

OPEN

NoneView/Download

Page view(s)

201
checked on Dec 11, 2017

Download(s)

146
checked on Dec 11, 2017

Google ScholarTM

Check


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