A 2D GPU Mesh Generator

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.