A distributed-memory parallel technique for two-dimensional mesh generation for arbitrary domains

• We present a parallel technique for generating two-dimensional triangular meshes.
• Generated meshes show the same quality as those generated with serial approaches.
• Our parallel technique presents a fairly good speed-up.
• Our load estimation is very effective and can be used for efficient load balancing.

This work describes a technique for generating two-dimensional triangular meshes using distributed memory parallel computers, based on a master/slaves model. This technique uses a coarse quadtree to decompose the domain and a serial advancing front technique to generate the mesh in each subdomain concurrently. In order to advance the front to a neighboring subdomain, each subdomain suffers a shift to a Cartesian direction, and the same advancing front approach is performed on the shifted subdomain. This shift-and-remesh procedure is repeatedly applied until no more mesh can be generated, shifting the subdomains to different directions each turn. A finer quadtree is also employed in this work to help estimate the processing load associated with each subdomain. This load estimation technique produces results that accurately represent the number of elements to be generated in each subdomain, leading to proper runtime prediction and to a well-balanced algorithm. The meshes generated with the parallel technique have the same quality as those generated serially, within acceptable limits. Although the presented approach is two-dimensional, the idea can be easily extended to three dimensions.