Three-dimensional Delaunay refinement for multi-core processors

We develop the first ever fully functional three-dimensional guaranteed quality parallel graded Delaunay mesh genera-tor. First, we prove a criterion and a sufficient condition of Delaunay-independence of Steiner points in three dimen-sions. Based on these results, we decompose the iteration space of the sequential Delaunay refinement algorithm by selecting independent subsets from the set of the candidate Steiner points without resorting to rollbacks. We use an oc-tree which overlaps the mesh for a coarse-grained decompo-sition of the set of candidate Steiner points based on their location. We partition the worklist containing poor qual-ity tetrahedra into independent lists associated with spe-cific separated leaves of the octree. Finally, we describe an example parallel implementation using a publicly available state-of-the art sequential Delaunay library (Tetgen). This work provides a case study for the design of abstractions and parallel frameworks for the use of complex labor intensive sequential codes on multicore architectures