Computing Three-dimensional Constrained Delaunay Refinement Using the GPU

Zhenghai Chen               Tiow-Seng Tan

School of Computing
National University of Singapore

{chenzh | tants} @



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 radius-edge 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 mesh refinement from possibly an hour to a few seconds or minutes for possible use in interactive applications. 


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


Paper and ppt for The 28th International Conference on Parallel Architectures and Compilation Techniques (PACT 2019), Sept 21-25, 2019, Seattle, WA, USA, pp. 408--419.

Software Download: available at Github here (16 Sept 2019, old)  and here (24 July 2020, new) 

Related Projects: Delaunay Triangulation, Constrained Delaunay Triangulation, 2D Delaunay Refinement


Updated Dates: 13 July 2019, 25 September 2019, 24 July 2020

© School of Computing, National University of Singapore