The finite element method (FEM) is a fundamental modelling technique in widespread use in the engineering analysis community. This technique is capable of solving field problems governed by partial differential equations in very complex domains. However, successful and efficient use of the finite element method still requires a significant expertise, time, and cost. Many researchers are investigating ways to automate the finite element method, thus allowing an improved productivity, more accurate solution, and use by less trained personnel. Although there is a number of steps in the finite element modelling technique, often the most time consuming and experience requiring task faced by an analyst is the discretization of a general geometric definition of the problem into a valid and well conditioned finite element mesh. The accuracy and cost of the analysis directly depend on the size, shape, and number of elements in the mesh. Automatic generation of consistent, reproducible, high-quality meshes without user intervention makes the power of the finite element analysis accessible to those not expert in mesh generation. Therefore, automation of the mesh generation is an important prerequisite for the complete integration of the finite element method with design processes in computer aided engineering (CAE) and manufacturing (CAM) systems.

The introduction of advanced geometric modelling systems based on
constructive solid geometry (CSG) or boundary representation (B-rep)
modelling techniques has a great impact on the entire design
process. Non-manifold solid models provide the most general form
representing an arbitrary geometry, including simultaneous representation
of wireframe, surface, and solid data. In this framework, the unstructured
grid technology is a promising approach for the discretization of these
models. It offers geometric flexibility for handling both complex
geometry and physics and a possibility to improve solution accuracy
and efficiency through adaptive meshing schemes. Early efforts in this
area suffered from two main deficiencies. Firstly, the algorithms and
their implementations were not entirely robust in that they did not
provide conditions ensuring that the resulting discretization
represented a valid computational mesh of the geometric
domain. Secondly, they were computationally expensive and demonstrated
poor performance rates. Intensive research has
continued in this area and since that time a variety of efficient and reliable
algorithms has been developed, with many of them being used
commercially. Successful application of these algorithms in the
framework of design processes using the finite element modelling
technique has demonstrated the maturity that the automatic
unstructured mesh generation techniques have reached.

Significant progress over the last two decades in the area of numerical methods and software technologies has enabled to solve still more and more demanding and complex problems. As the size of the problems becomes larger, the process of solution on a serial computer becomes problematic both in terms of time and storage. Thus the application of distributed parallel algorithms to the solution process is often the only way to solve huge realistic problems. At present, the size of the largest computations is governed by the ability to automatically generate meshes on serial machines. Once generated, these meshes need to be partitioned, again using a serial machine, and sent to the processors of a parallel machine to carry out the problem solution. Moreover, during an adaptive analysis, the mesh needs to be regenerated either locally or globally many times (possibly hundreds of times when transient analysis is considered) during the whole analysis process. This makes the mesh generation on a single processor problematic, as it does not scale with the number of processors available for the analysis. Therefore, a strategy capable of generating a mesh in parallel, such that when the mesh generation is finished the mesh is already partitioned and in place for the problem solution, is highly desirable.

The presented work is motivated by current trends in the automatic unstructured mesh generation focusing on user friendliness, enhanced versatility, enlarged range of applicability, and improved performance (qualitative and quantitative) including vectorization and parallelization. There are two main objectives of this work. The first one is to design and implement a fully automatic mesh generator of unstructured triangular and tetrahedral meshes. The emphasis during the development has been concentrated mainly on the robustness and computational complexity of the employed methodology and on the quality of resulting meshes. The second objective is to develop an algorithm for parallel mesh generation using memory distributed computing systems. In this case, the main focus is put on the scalability and load balance of the implemented algorithms.

The first part of this work deals with the design and implementation of an automatic mesh generator based on the advancing front technique and designated for sequential processing. The model description, allowing to handle non-manifold topologies, together with a flexible mesh size control is outlined. A detailed strategy of discretization of individual model entities including mesh optimization is provided. The mesh validity and computational complexity of the presented approach are discussed and the performance is demonstrated on a set of examples.

In the second part, the development of a tree-based mesh generation technique for parallel processing is presented. Again, the model description and mesh size control are given. Then the discretization and parallelization strategies are outlined accompanied by a detailed description of a parallel computing scheme. The performance of the presented parallel algorithm, including speedup, efficiency, and load balance, is examined on a memory distributed parallel computing platform.

*Daniel Rypl
2005-12-07*