Computing
Three-dimensional Constrained Delaunay Refinement Using the GPU

**Zhenghai**** Chen
Tiow-Seng Tan**

**School of Computing
National University of Singapore
{chenzh | tants} @
comp.nus.edu.sg**

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
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 28^{th}
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**