Computing Delaunay Refinement Using the GPU

**Zhenghai****
Chen ^{1}, Meng Qi^{2}, Tiow-Seng Tan^{3} **

^{1,3}**School of Computing,
National University of Singapore
{chenzh | tants} @
comp.nus.edu.sg**

^{2}**School of Information
Science and Engineering, Shandong Normal University
qimeng0914 @ gmail.com**

Abstract

We propose the first
working GPU algorithm for the 2D Delaunay refinement problem. Our algorithm
adds Steiner points to an input planar straight line graph (PSLG) to generate a
constrained Delaunay mesh with no angle in triangles smaller than a minimum
allowable angle Ɵ. It is shown to run from a few times to an order of magnitude
faster than the well-known *Triangle*
software, which is the fastest CPU Delaunay mesh generator. Our implementation
handles degeneracy and is numerically robust. It is proven to terminate with
finite output size for
PSLG with no input angle smaller than 60^{o} and Ɵ ¡Ü 20.7^{o}.
In addition, we notice the meshes generated by our algorithm are of similar
sizes to that by *Triangle*, which has
incorporated good considerations in keeping output sizes small.

**Keywords: GPGPU, Computational Geometry,
Mesh Refinement, Finite Element Analysis **

Paper and ppt The Proceedings of ACM Symposium on Interactive 3D Graphics and Games (I3D 2017), Feb 25-27, 2017, San Francisco, CA, USA.

**
**

**Software Download: at GitHub (old) (12 Dec 2017),
at GitHub (new) (24 July 2020)
**

** Related Projects:
Delaunay Triangulation,
**Constrained Delaunay Triangulation

**Dated: 27 Feb 2017, 12 Dec 2017, 24 July 2020**

© School of Computing, National University of Singapore