## Parallel Constrained Delaunay Mesh (PCDM) Generation

- Details
- Category: Parallel Mesh Generation

### Description

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.

### 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.

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.

### Software

The following software is used in this project.

- pcdm-1.0.tgz
- meDDec
- Triangle
- Exact Arithmetic And Robust Geometric Predicates
- Metis