Sequential and Parallel Generation
of Unstructured 3D Meshes

Daniel Rypl

Department of Structural Mechanics
Faculty of Civil Engineering
Czech Technical University in Prague
Thákurova 7, 166 29 Prague, Czech Republic


The presented work describes design and implementation of algorithms for automatic discretization of 3D domains. Two techniques for the discretization of domains described in terms of a boundary representation using rational Bezier curves and surfaces are presented.

The first method is based on the advancing front technique and it is designated exclusively for processing in sequential environments (single processor computing platforms). The main effort has been directed towards the robustness and performance of the designed and implemented algorithms. The octree data structure is used to control the mesh gradation and to efficiently perform the spatial localization. The mesh generation over surfaces and regions uses the element removal concept with a high quality runtime node placement strategy. The validity of the final mesh is verified in terms of the topological compatibility and geometrical similarity with the underlying model. Meshes of a various density and mesh size gradation consisting of well-shaped elements are produced. The presented approach exhibits a favourable computational complexity, which makes it very competitive in practical applications.

The second technique utilizes the tree-based approach and is designed for a parallel processing on memory distributed computing platforms. The parallelization strategy is based on the domain decomposition concept. Two levels of the domain decomposition have been considered - the model level and the model entity parametric tree level. The discretization is accomplished by application of templates fitted into the cells of a generalized parametric tree data structure built over individual model entities. The actual parallel computing scheme is based on the master and slaves parallel paradigm. Since a dynamic load balancing mechanism is employed, an even distribution of the work load among the processors is ensured. A very favourable ratio between the computation and communication has been achieved and a considerable speedup has been evidenced. The algorithm has been successfully implemented on two massively parallel computing platforms - IBM SP2 and Transtech Paramid.