CRTC - Generalized Delaunay Refinement Project

Project Category

Generalized Delaunay Refinement

Description

We generalize the existing two-dimensional (2D) and three-dimensional (3D) Delaunay refinement algorithms along with theoretical proofs of mesh quality in terms of element shape and mesh gradation. Existing algorithms are constrained by just one or two specific positions for the insertion of a Steiner point inside a circumscribed disk of a poorly shaped element. We derive an entire 2D or 3D region for the selection of a Steiner point (i.e., infinitely many choices) inside the circumscribed disk. See Figure 1 for some results.

We develop a novel theory which extends both the 2D and the 3D Generalized Delaunay Refinement methods (see 1) for the concurrent and mathematically guaranteed independent insertion of Steiner points. Previous parallel algorithms are either reactive relying on implementation heuristics to resolve dependencies in parallel mesh generation computations or require the solution of a very difficult geometric optimization problem (the domain decomposition problem) which is still open for general 3D geometries. Our theory solves both of these drawbacks. See Figure 2 and Figure 3 for some results.

Using our generalization of both the sequential and the parallel algorithms (see 1 and 2) we implemented prototypes of practical and efficient parallel generalized guaranteed quality Delaunay refinement codes for both 2D and 3D geometries using existing state-of-the-art sequential codes for traditional Delaunay refinement methods. On a heterogeneous cluster of more than 100 processors our implementation can generate a uniform mesh with about a billion elements in less than 5 minutes. Even on a workstation with a few cores, we achieve a significant performance improvement over the corresponding state-of-the-art sequential 3D code, for graded meshes. See Figure 4 for some results.

Results

Figure 1 shows the use of the selection disk for the construction of boundary conformal meshes. (Left) An MRI scan showing a cross-section of a body. (Right) A zoom-in of the selected area containing an artery: the inside is white, the outside has different shades of gray and the black zone is an approximate boundary between these regions. The standard Delaunay refinement algorithm would insert the circumcenter c. However, in order to construct a mesh which conforms to the boundary, another point (p) would be a better choice.


Figure 1. Selection disk for construction of boundary conformal meshes

Figure 2 shows challenges in parallel Delaunay refinement. (Left) Concurrent insertion of p_8 and p_9 leads to a non-conformal mesh. (Right) Concurrent insertion of p_8 and p_10 leads to a non-Delaunay mesh.


Figure 2. Challenges in parallel Delaunay refinement

Figure 3. Buffer zone of an octree leaf which is the solid white box in the center


Figure 4. Meshes of pipe cross-section model & key model overlayed by quadrees