On the Parallelization of Guaranteed-Quality 3D Delaunay Mesh Generators

2nd Symposium on Trends in Unstructured Mesh Generation, University of Colorado, Boulder, August 1999

MESHING
RESEARCH
CORNER

Computer Science and Engineering, University of Notre Dame
nikos@cse.nd.edu

Abstract
In this paper we address basic problems related to the correctness and efficiency of parallel mesh generators based on 3D sequential, quality-guarantee, Delaunay tetrahelization algorithms. We discuss their solution under different computational characteristics: synchronization, strictness, and concurrency. We analyze the complexity and performance of implementations that appear to solve these problems. Finally, based on our experience, we explore possible new approaches for developing efficient parallel 3D mesh generators that maintain the same high-quality as the existing sequential ones.

The Bowyer-Watson (B-W) kernel has been used successfully by Chew and Ruppert to generate guaranteed-quality meshes for 2D domains, and by Shewchuk for 3D piecewise linear complexes (under certain constraints). Variations of this kernel have been used by many others; the main difference between the various algorithms is in the treatment of the domain boundaries (constraints). Traditionally, the B-W kernel is parallelized using domain decomposition; the challenge then is to maintain the Delaunay property across the boundaries of the subdomains. The main step in the B-W kernel, cavity expansion, is based on a breadth-first search over the mesh's data structures; sequentially, this is a very simple task to accomplish. In parallel, however, cavity construction becomes much more difficult, since cavities may extend across the boundaries (interfaces) separating adjacent regions of the mesh.

The expansion of these multi-region (MR) cavities can be synchronous or asynchronous, either halting or allowing the creation of new cavities in regions participating in the cavity expansion. In an asynchronous implementation, it is possible for MR cavities to intersect (share tetrahedra or faces with) local cavities or other MR cavities, which can result in a non-Delaunay retetrahedralization of the intersecting cavities. We analyze the possible intersection cases with respect to four different computational models, and study their impact on (1) the correctness of the algorithm, (2) the resulting concurrency, and (3) the setbacks in the progress of the algorithm.

In addition to the difficulties of cavities which extend over multiple regions, problems with correctly updating a region in the face of concurrency also arise. For example, in a straightforward asynchronous/strict parallelization of Shewchuk's conforming constrained Delaunay tetrahedralization algorithm, one must do away with the ordering on the splitting of edges, faces, and elements called for by the original algorithm. Not only is mesh quality affected by this change, but neither the correctness of the resulting mesh, nor the termination of the algorithm, can be proved. These problems exemplify the need for the creation of a wholly new parallel algorithm for Delaunay mesh generation.

While the parallelization of an existing algorithm seems appropriate at first glance, our experience shows that there is a need for the creation of purely parallel algorithm. This new algorithm will be developed keeping in mind the errors, the inconsistencies, and the inefficiencies that arise due to concurrency. The complexity and the performance of our current parallel implementation clearly demonstrate the need for such an algorithm. Our results also show that parallel Delaunay meshing based on the B-W kernel is a foreseeable goal, although much work remains to be done to realize an efficient guaranteed-quality parallel mesh generator.

CISE Challenge on Crack Propagation for Teraflop Computers, NSF grant #9726388