Unstructured Mesh Generation And Its Parallelization

Mesh generation is the pre-process and one of main performance bottlenecks of numerical simulations. With ever larger problems arising in such areas as Computational Fluid Dynamics (CFD), Computational Electro-Magnetics (CEM), close attention has been paid to parallel mesh generation to overcome the bottlenecks of serial mesh generation in terms of time and memory consuming in the international research community since early 1990s. However, few researchers in China have concentrated on this field so far. For the requirement of more and more large-scale simulations emerging in the industry and research community, in this thesis we will study some practical problems of unstructured mesh generation and its parallelization in depth.Firstly, a robust and efficient pattern module scheme for fully quadrilateral elements is constructed for meshing triangular or quadrilateral domains. The scheme is then applied into the sub-domain mesh generation stage of domain decomposition methods. It overcomes two drawbacks associated with current sub-domain meshing algorithms, i.e. the sub-domain definition being too stringent and the generation rule being too complex. Consequently, a new quadrilateral mesh generation method for arbitrary planar domains is proposed. Furthermore, a parallel version of this method is proposed by parallelizing the domain decomposition process and introducing the SubDomain Graph (SDG). It could generate distributed meshes with high partitioning quality simultaneously with parallel mesh generation, therefore to accelerate the whole process of parallel simulations greatly.Secondly, serial Delaunay mesh generation algorithms are discussed, and high-quality 2D and 3D serial Delaunay mesh generators using the Bowyer-Watson point insertion kernel are coded, named DTIso2D and DTIso3D, respectively. Issues of time and memory complexities, robustness, data structures and important implementation details are explored in this thesis.Boundary recovery is one of main problems in applying Delaunay algorithms into mesh generation. All constraint missing cases are illustrated, and the corresponding recovery techniques are given as well based on the idea of adding Steiner points directly in the missing constraints. Besides, a series of concepts, data structures and operators are introduced to alleviate the coding work of the conformal boundary recovery algorithm.A constrained rather than conformal boundary recovery procedure is required for the coordination of shared data in the artificial interfaces of partitioned meshes. George and Du et al independently present two new indirect constrained boundary recovery algorithms with nearly same idea, which both strive to resolve the robustness problem of George's early classic algorithm. Here indirect algorithms mean that a conformal boundary recovery procedure is prerequisite. We simplify some concepts of the above algorithms and present a new implementation for them.Integrated with the parallel geometry decomposition algorithm obtained from the research of above parallel quadrilateral mesh generation, a general parallel planar mesh generation framework is constructed, where a dynamic SDG partitioning module is involved. A 2D parallel Delaunay mesh generator, named PDMG-2D, is developed by combining the framework with DTIso2D, which could generate more than hundreds of millions of elements in the parallel computers with medium size resources. Moreover, considerably good partitioning quality could be achieved for the resulting distributed meshes.For 3D problems, the computational domain is decomposed into many sub-domains recursively by intersecting a plane with the domain. Robust problems arising from complex geometry computations involved in the domain decomposition procedure are investigated. A roll-back scheme of moving the separation plane is utilized to overcome unrecoverable errors in domain decomposition. DTIso3D is linked together with the recursive domain decomposition framework to form the 3D parallel Delaunay mesh generator, named PDMG-3D, which could generate partitioned meshes with more than one hundred millions of elements in the parallel computers with medium size resources.The design of data structures is important in practice for parallel mesh generators to save memory usages, to accelerate algorithms, and to simplify the mergence of sub-meshes or distributed meshes on various sub-domains or processors. We devise a three-level data structure to help fulfill such goals conveniently. It also enables the resulting mesh to be smoothed or optimized globally or in a processor level instead of in a sub-domain level.