1 Introduction and Motivation

During the last decades, computer-aided engineering (CAE) methods have become very popular for simulating the behavior of science and engineering problems. For the vast majority of these simulations, differential equations, or their higher-dimensional versions - partial differential equations (PDEs) - are used to mathematically describe the desired physical processes [33]. For example, in technology computer-aided design (TCAD), the continuity equation with the drift-diffusion model is used to describe the behavior of the electrostatic potential and electronic charge carriers within a semiconductor [125]. In computational fluid dynamics (CFD), the Navier-Stokes equations are used to describe the motion of fluids [25]. The combinations of Euler's equations of motions and the Euler-Cauchy stress principle yields a system of PDEs, which is used for stress analysis in structural mechanics [110].

Besides the mathematical model, a simulation scenario additionally requires a simulation domain, on which the PDE is applied, and boundary conditions which represent influences from the outside. This is called a boundary value problem or, generally speaking, a simulation problem [23]. However, even if the existence and uniqueness of the solution of a boundary value problem can be proven mathematically, the number of PDEs with an explicit analytical solution is small [51]. The two examples named above, i.e., the drift-diffusion equations and the Navier-Stokes equations, do not have explicit analytical solutions in general. Therefore, numerical approaches have to be used to calculate approximate solutions. Popular numerical approaches are the finite difference method (FDM) [112], the finite volume method (FVM) [111], and the finite element method (FEM) [57]. These methods require that the simulation domain, which in its most general form is represented by a geometry, is decomposed (also referred to as discretized) into a discrete mesh to obtain a finite representation of the simulation domain. Hence, meshes are an integral component of a simulation process.

Figure 1.1: Objects with symmetries used in CAE, gear image by Inductiveload, aircraft image by Kaboldy

Figure 1.2: A sketch of a bridge with similarities, image by Charles Edward Inglis

There are multiple parts of this bridge construction, which are similar to each other, for example the bars $C$ and $C^1$ or $A$ and $A^1$.

Figure 1.3: Re-construction of objects with symmetries

The objects can be reconstructed by using smaller pieces, those being one side of the plane and a jag of the star, respectively. The smaller piece is copied and reflected or rotated around the symmetry center to obtain the desired object.

Geometries of objects in CAE scenarios, like a gear in a stress simulation, are usually designed using computer-aided design (CAD) tools. Many objects in CAE applications inherently require symmetries to function. For example, a gear which is not rotationally symmetric will not work properly. Consequently, symmetries (cf. Figure 1.1) and similarities (cf. Figure 1.2) are of special interest, because they can be used to understand the structure and shape of the geometry. In particular, objects with symmetries and similarities can be constructed from smaller pieces of the object using rigid transformations as shown in Figure 1.3.

Figure 1.4: Symmetric geometry and exemplary non-symmetric mesh

Even though the object itself has a rotational and a reflective symmetry, the mesh has neither.

The main motivation of this work is to leverage symmetries and similarities in objects when creating, using, and storing meshes which are ignored by conventional mesh generation and adaptation algorithms. Using the fact that objects with symmetries and similarities can be constructed from smaller pieces (cf. Figure 1.3), a data structure can be defined, where that piece is only stored once hence saving memory. The same idea can be applied for mesh generation processes, where generating a mesh of smaller pieces is considerably less time consuming than meshing the entire geometry.

$\phantom{ }$

Aside from memory and runtime aspects, ignoring symmetries during the mesh generation process potentially results in non-symmetric meshes (cf. Figure 1.4). If the simulation domain is symmetric, the boundary conditions can be transformed by the symmetry transformation. The mathematical solution to the simulation problem with transformed boundary conditions is equal to the transformed solution to the initial problem. However, this is not the case for a numerical solution if a non-symmetric mesh is used. It is therefore a central goal of this work to provide algorithms which generate high-quality meshes having the same symmetry as the corresponding simulation domain.

Figure 1.5: Templated meshes

The resulting mesh is obtained by applying the transformation functions on the mesh templates. Non-conformities are visualized by red circles.

The ideas for the main approaches presented in this work originate from the field of computer graphics. In particular, the approach is motivated by a technique called geometry instancing [92], where a mesh template is used to render a high number of instances into a scene. Every instance has its own location and orientation within the scene and potentially additional differences, like scaling, color, or textures. In this work, the concepts of geometry instancing are applied to volumetric meshes used for simulations. The theories developed in this work are focused on similarities as they also are able to represent symmetries. For example, the slice of an object with a rotational symmetry is similar to all other slices of that object. A set of mesh templates each coupled with a set of transformations, called a templated mesh, is used to define a resulting mesh as visualized in Figure 1.5a. However, most algorithms for meshes used in computer graphics cannot be directly applied to volumetric meshes used in simulations. In computer graphics and rendering applications, surface meshes are used rather than volumetric meshes. These surface meshes are not required to be conforming, meaning that, e.g., the surface mesh is allowed to have holes or self-intersections. The conformity property, however, is an important requirement for meshes used in science and engineering as it is mandatory for discretization-based simulation methods like the FEM. This property is not automatically guaranteed when using templated meshes as can be seen on the right of Figure 1.5b. Therefore, algorithms for templated mesh generation and templated mesh adaptation have to take special care to ensure element conformity.

Theoretical approaches for templated meshes are developed in this work. These approaches are used to formulate new mesh generation and adaptation algorithms for their application with templated meshes. This work focuses on templated mesh generation algorithms, where two new general algorithms are proposed. Special (less complicated) mesh generation algorithms for geometries with symmetries are formulated as well. Additionally, data structures for storing templated meshes are developed, which optimize memory usage. The proposed data structures and mesh generation algorithms have been implemented in the open source meshing framework ViennaMesh [19]. Using these implementations, a benchmark-based survey is performed to evaluate improvements in memory usage and algorithm runtime as well as element quality and errors in simulation solutions. In particular, this work addresses the following research questions with a focus on challenges in micro- and nanoelectronics:

(i)

How can templated meshes and templated geometries be defined? Are there any restrictions or issues? Which restrictions and which issues apply to objects with symmetries?

(ii)

How can properties, like the Delaunay property, be abstracted to templated meshes?

(iii)

Which algorithms for conventional meshes also work for templated meshes? Which modifications are required for these algorithms?

(iv)

How can a templated mesh be generated based on symmetric geometries?

(v)

What are the effects on mesh element quality of a templated mesh generation algorithm compared to a conventional mesh generation algorithm? How do non-symmetric meshes (of symmetric geometries) affect the solution of simulation processes?

(vi)

How much memory can be saved when using templated meshes?

(vii)

What are the effects on the runtime performance for templated mesh generation algorithms?

Chapter 2 introduces general definitions and theorems for geometries and meshes with a special focus on mesh properties which are important for discretization-based simulation methods, like the Delaunay property or mesh element quality. The necessary mathematical basics are covered in Appendix A.

Related work on meshes as well as algorithms for generating and adapting meshes is covered in Chapter 3. Additionally, the results of a literature search on automatic similarity and symmetry detection and symmetry-aware mesh processing is provided.

The theoretical background for templated structures, including definitions and theorems, is presented in Chapter 4. In this chapter, the major theoretical results of this work are deduced and discussed.

Two volumetric mesh generation algorithms for templated structures are presented in Chapter 5. Additionally, this chapter investigates a popular selection of mesh adaptation algorithms for their use with templated meshes and discusses restrictions and modifications.

In Chapter 6, decomposition methods for shapes, especially shapes with similarities and symmetries, are presented and special properties of objects with symmetries are discussed. Additionally, the theoretical results and the proposed algorithms presented in the previous chapters are applied to symmetric meshes and geometries.

A benchmark-based survey is presented in Chapter 7, which investigates the benefits of the data structures and algorithms proposed in this work.

The last chapter, Chapter 8, concludes the work by evaluating the research questions and gives an outlook on possible future work.