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 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)
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