Parallel Constrained Delaunay Mesh (PCDM) Generation


Delaunay refinement is a widely used method for the construction of guaranteed quality triangular and tetrahedral meshes. We present an algorithm and a software for the parallel constrained Delaunay mesh generation in two dimensions. Our approach is based on the decomposition of the original mesh generation problem into N smaller subproblems which are meshed in parallel. The parallel algorithm is asynchronous with small messages which can be aggregated and exhibits low communication costs. On a heterogeneous cluster of more than 100 processors our implementation can generate over one billion triangles in less than 3 minutes, while the single-node performance is comparable to that of the fastest to our knowledge sequential guaranteed quality Delaunay meshing library (Triangle). See Figure 1 and Figure 2 for some results.


Figure 1 shows the Chesapeake bay model decomposed into 1024 subdomains, which are mapped onto 8 processes. The assignment of subdomains to processes is shown with different colors.

Chesapeake 1024 8

Figure 2 demonstrates the scaled speedup measurements. The number of triangles is approximately 10P, i.e., for 2 processors 20M, and for 144 processors about 1.4B.

Pcdm speedup


The following software is used in this project.

Generalized Delaunay Refinement


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.


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.

Slice zoomout Slice zoomin

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.

2cavs 1 2cavs 2

Figure 2. Challenges in parallel Delaunay refinement


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

Pipe pgdr Key pgdr

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

Related Papers

TODO after complete the publication!

Parallel Advancing Front Method


The primary focus of this project is to design and implement a parallel framework for an unstructured mesh generator based on the advancing front method (AFM). In particular, we target large-scale Computational Fluid Dynamics (CFD) simulations of complex problems. The desire to perform better quality and high-accuracy numerical simulations more efficiently is enabled by: (1) the widespread availability of parallel machine architectures and (2) the ability of numerical solvers to take advantage of parallel machine architectures. The quality of the simulation produced by the solver depends on the particular mesh that is provided by the mesh generator. In order to accurately capture complex physical phenomena, a large-scale high-resolution mesh is required. Furthermore, for time-dependant flow problems involving moving bodies, aero-elastic analysis of aircraft undergoing surface deflections, interactive CFD/design analysis resulting in geometry perturbation, etc., re-meshing is performed during the simulation. In this scenario, the mesher and the solver co-exist at the same time and both compete for resources. Moreover, generating such a mesh on a single machine is a challenging task due to both CPU and memory limitations. A parallel mesh generator, with distributed memory is more suitable for this task.


1. Parallel Mesh Generation For CFD Simulations Of Complex Real-World Aerodynamic Problems
George Zagaris, Shahyar Pirzadeh, Andrey Chernikov and Nikos Chrisochoides. In Proceedings of 6th Symposium on Trends in Unstructured Mesh Generation (MeshTrends VI), 2007.


NASA (LaRC) GSRP Fellowship 2006, 2007

Related Links