Computing delaunay refinement using the GPU

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 triangles having no angle smaller than an input θ. 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 an input PSLG with no angle smaller than 60° and θ ≤ 20:7°. In addition, we notice meshes generated by our algorithm are of similar sizes to that by Triangle, which has incorporated good consideration in keeping output small in size.