Please use this identifier to cite or link to this item:
Title: A 2D GPU Mesh Generator
Authors: QI MENG
Keywords: mesh generator, quality mesh, Delaunay refinement, constrained Delaunay triangulaiton, GPU, computational geometry
Issue Date: 16-Jan-2014
Citation: QI MENG (2014-01-16). A 2D GPU Mesh Generator. ScholarBank@NUS Repository.
Abstract: Meshes composed of triangles are used in various applications such as computer graphics, interpolation, finite element method, and terrain databases. There are several successful triangle mesh generators which can generate Delaunay triangulation, constrained Delaunay triangulation, conforming Delaunay triangulation and quality triangulation on the CPU. However, there is no similar generator for the graphics processing unit (GPU) architecture existing at this moment. The GPU has been used not only for graphics processing tasks but also general computations in many disciplines including computational geometry due to its enormous parallel computing power. In computational geometry, early works on the GPU include computing the digital Voronoi diagram and Delaunay triangulation. There has been no prior approach to generate other triangle mesh such as constrained Delaunay triangulation, conforming Delaunay triangulation and quality triangulation efficiently using the parallel computing power of the GPU. The GPU is massively multithreaded, with hundreds of processors, in order to fully utilize the GPU hardware, a parallel algorithm usually needs to have regularized work and localized data access. However it is even not clear how to achieve these criteria while adapting the traditional and usually complex parallel techniques, such as divide-and-conquer to the mesh generation problem. So it is not clear how to efficiently apply traditional parallel algorithms directly on the GPU. In this thesis, we focus on designing mesh generating algorithms in 2D space on the GPU. Two algorithms termed as GPU-QM and GPU-CDT are proposed in the thesis, which can improve the quality of the Delaunay triangulation for a point set, and compute constrained Delaunay triangulation for a set of points and constraints, respectively. Both of these two algorithms are the first GPU algorithms proposed so far. According to our experiments for both synthetic and real-world data, our GPU algorithms are numerically robust and run faster than the fastest sequential algorithm. Comparing to the fastest sequential implementation, the GPU-QM gains up to 5.5 times speedup; the GPU-CDT gains up to two orders of magnitude speedup. Furthermore, we obtain the first GPU mesh generator by integrating the GPU-QM, GPU-CDT algorithms with an existing work GPU-DT, which can compute Delaunay triangulation for a point set using the GPU. Our mesh generator can compute digital Voronoi diagrams, Delaunay triangulation, constrained Delaunay triangulation, conforming Delaunay triangulation and high-quality triangle meshes in 2D space on the GPU. In order to handle numerical error and degenerate input, we implement exact predicates and simulation of simplicity method on the GPU based on the sequential implementations. So our generator can handle exact arithmetic and is numerically robust.
Appears in Collections:Ph.D Theses (Open)

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



Page view(s)

checked on Oct 14, 2021


checked on Oct 14, 2021

Google ScholarTM


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