Parallel Constrained Delaunay 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 1. The Chesapeake Bay Model

 

 

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.

 

Figure 2. Scaled speedup measurements

•  

  ---

 

Software

 

The following software is used in this project.   

•    

        - pcdm-1.0.tgz

•     

        - meDDec

•     

        - Triangle

•     

        - Exact Arithmetic And Robust Geometric Predicates

•     

        - Metis

•  

  ---

 

 

 

 

Related Papers

1. Parallel 2D Constrained Delaunay Mesh Generation

2.  Multigrain Parallel Delaunay Mesh Generation: Challenges and Opportunities for Multithreaded Architectures

  [PDF]          [BibTex]