Computing three-dimensional constrained delaunay refinement using the GPU

Abstract

We propose the first GPU algorithm for the 3D constrained Delaunay refinement problem. For an input of a piecewise linear complex G and a constant B, it produces, by adding Steiner points, a constrained Delaunay triangulation conforming to G and containing tetrahedra mostly with radiusedge ratios smaller than B. Our implementation of the algorithm shows that it can be an order of magnitude faster than the best CPU software while using similar quantities of Steiner points to produce triangulations of comparable qualities. It thus reduces the computing time of triangulation refinement from possibly an hour to a few seconds or minutes for possible use in interactive applications.