Computing Delaunay Refinement Using the GPU

Zhenghai Chen¹, Meng Qi², Tiow-Seng Tan³

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

²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