Delaunay Mesh Refinement on the GPU

Zhenghai Chen Tiow-Seng Tan Hong-Yang Ong

School of Computing
National University of Singapore

{dcschai | dcstants} | dcsohy} @ nus.edu.sg

Abstract

We present three GPU algorithms for performing 2D and 3D Delaunay mesh refinement. For 2D, we present a GPU constrained Delaunay algorithm which takes in a plane straight line graph as input and generates a conforming quality mesh. For 3D, we present a GPU constrained Delaunay algorithm and a GPU restricted Delaunay algorithm, which both take in a piecewise linear complex as input and generates a conforming quality mesh and an approximating quality mesh respectively. These algorithms adopt a set of design strategies, aimed at improving GPU utility, which can be possibly applied to other mesh refinement solutions. Experimental results show that our algorithms are faster than the current state-of-the-art counterparts (for both sequential and multi-threading CPU versions) by up to an order of magnitude, while maintaining similar number of Steiner points being inserted. This may make Delaunay mesh refinements feasible in interactive applications.

Keywords: Parallel Meshing, Delaunay Triangulation, Little’s Law

Manuscript (15 pages) – Some experimental results can be found in Chen’s Ph.D thesis (PPT for the Ph.D defence)

Software Download:

· gDP2d: 2D Constrained Delaunay Refinement

o zip file: source and executable + data, 394MB, or

o zip file: executable + data, 380MB (for windows), or

o see github

o Comparison is done with Triangle

· gQM3d: 3D Constrained Delaunay Refinement

o zip file: source and executable + data, 87MB, or

o zip file: executable + data, 45MB (for windows), or

o see github