6.1 Meshing Strategy and Overall Concept

The implemented meshing strategy follows the concept of Delaunay methods as described in Chapter 4. The design consists of four parts respectively placing mesh points, preprocessing the surface, tetrahedralization, and further insertion of Steiner points for adaptation purposes and quality improvement (Fig. 6.1).

Figure 6.1: Overall concept

No restrictions are imposed on the generated and/or provided initial mesh point distribution. Mesh points may overlap the structure boundary or cover the entire bounding box. Fully unstructured meshes can be constructed. The tetrahedralization engine does not require to remove or change mesh points. Among the advantages of such a logical separation in a place points and link [169] approach are stability, modularity, and a higher flexibility in combining different techniques for various applications. An example for the success of this approach in two dimensions is the triangulation engine described in [160].

The goal of surface preprocessing is the actual management of complex structure boundaries in an intelligent way, consistency checks, conversion issues, and the generation of a high quality Delaunay surface mesh. The minimum information defining a multi-segment geometry such as one unsorted list of general polygons is a sufficient input. In fact, only the non-convex regions of the structure boundaries have to be specified. It is not required to provide a closed surface. For example the surface of the top region of a semiconductor structure after etching and deposition simulation without the bulk boundary suffices to generate a volume mesh. Various discretization criteria for surface elements as discussed in Section 3.2 can be applied. The initial distribution of mesh points is taken into account by the surface preprocessor. Situations where unconnected points are too close to the boundary or collapse with the boundary can be cleaned up on the fly. The developed surface refinement algorithm ensures the integration of the boundary into the Delaunay mesh.

The tetrahedralization engine uses the modified advancing front Delaunay algorithm as briefly introduced in Section 5.5. The preprocessed surface description provides the initial front. The mesh generation process is constrained to the regions of interest by the Delaunay boundary representation. The tetrahedralization of the convex hull of the vertices and mesh points is not even temporarily necessary. It also means that initial mesh points which are located outside of structure boundaries never affect the meshing procedure. A robust implementation was developed for degenerate cases combined with an efficient non-uniform point bucketing scheme. Many existing variations of the advancing front style Delaunay algorithm are either two-dimensional or experience difficulties with cospherical point sets [122,43,42,39,31,33]. A recent three-dimensional implementation uses a perturbation approach to handle degenerate cases [81].

Other advantages of the modified advancing front algorithm are an easier parallelization [32] and the possible real time visualization of the meshing process for debugging purposes. The process can be interrupted at any time and the resulting snapshot is a valid mesh of part of the domain. Those parts of the domain which are not of interest are never meshed which saves computation time especially for extremely non-convex domains. The approach is therefore also well suited for local mesh adaptation. The cavities in the mesh where elements have been discarded due to local modifications form local fronts which can directly be used as advancing fronts to grow tetrahedra and to remesh the gaps. In such a way Steiner points can be inserted to improve geometrical quality measures.