Computing Delaunay Refinement Using the GPU

Zhenghai Chen1, Meng Qi2, Tiow-Seng Tan3

1,3School of Computing, National University of Singapore
{chenzh | tants} @

2School of Information Science and Engineering, Shandong Normal University
qimeng0914 @


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 60o and Ɵ 20.7o. 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