Simplex Mesh Generation

**Figure 3.1:** Advancing front mesh generation
$\begin{subfigure} % latex2html id marker 5720 [b]{0.30\textwidth} \centering \... ...mesh_generation_advancing_front_1} \caption{Starting geometry} \end{subfigure}$ $\begin{subfigure} % latex2html id marker 5727 [b]{0.30\textwidth} \centering \... ...es/mesh_generation_advancing_front_2} \caption{First triangle} \end{subfigure}$ $\begin{subfigure} % latex2html id marker 5734 [b]{0.30\textwidth} \centering \... ...s/mesh_generation_advancing_front_3} \caption{Second triangle} \end{subfigure}$ $\begin{subfigure} % latex2html id marker 5741 [b]{0.30\textwidth} \centering \... ...es/mesh_generation_advancing_front_4} \caption{Third triangle} \end{subfigure}$ $\begin{subfigure} % latex2html id marker 5748 [b]{0.30\textwidth} \centering \... ...eneration_advancing_front_5} \caption{After a couple of steps} \end{subfigure}$ $\begin{subfigure} % latex2html id marker 5755 [b]{0.30\textwidth} \centering \... ...igures/mesh_generation_advancing_front_6} \caption{Final mesh} \end{subfigure}$ In the first picture, the starting geometry is visualized. The boundary of this geometry is used as the initial front, drawn in green. Using this front, new volumetric elements are constructed iteratively on the inside and the front is updated (picture two to picture four). Picture five shows the mesh after several of steps and the final mesh is shown in picture six.

Advancing front algorithms [39][60] require the boundary of the geometry and all region interfaces to be represented by a hull mesh. For each region the meshed region boundary is the starting front. Iteratively, the algorithm constructs volumetric mesh elements on the interior of the front and updates the front. This process is repeated, until the whole interior is filled with mesh elements. Figure 3.1 shows how an advancing front algorithm works on a simple two-dimensional geometry. Advancing front algorithms usually produce elements with high quality at the region boundaries [127]. However, in situations where the fronts collide, the algorithms have less freedom when constructing volumetric elements and therefore the element quality degrades.

**Figure 3.2:** Delaunay refinement mesh generation
$\begin{subfigure} % latex2html id marker 5777 [b]{0.28\textwidth} \centering \... ..._generation_delaunay_refinement_1} \caption{Starting geometry} \end{subfigure}$ $\begin{subfigure} % latex2html id marker 5784 [b]{0.28\textwidth} \centering \... ...ion_delaunay_refinement_2} \caption{Extract geometry vertices} \end{subfigure}$ $\begin{subfigure} % latex2html id marker 5791 [b]{0.2\textwidth} \centering \i... ...mesh_generation_delaunay_refinement_3} \caption{Triangulation} \end{subfigure}$ $\begin{subfigure} % latex2html id marker 5798 [b]{0.3\textwidth} \centering \i... ...es/mesh_generation_delaunay_refinement_4} \caption{Final mesh} \end{subfigure}$ The first picture visualizes the starting geometry. At first, only the vertices of the geometry are considered (picture two) and a triangulation of these vertices is created as shown in picture three. Flip operations and vertex insertions are used to make every simplex of the triangulation Delaunay. To ensure geometry-conformity, additional constraints from the PLC are inserted into the final mesh, again using flipping or splitting operations (cf. Section 3.2). Triangles which are outside of the geometry are removed. The final constrained Delaunay mesh is visualized in picture four.

Using only the vertices of the geometry, Delaunay refinement algorithms [56][127] first create a triangulation which is Delaunay. Then, elements are flipped and/or split to ensure geometry-conformity of the mesh. Mesh elements not included in the underlying space of the geometry are discarded. If needed, Delaunay refinement (see Section 3.2.3) is used to ensure the Delaunay or constrained Delaunay property of the resulting mesh. Figure 3.2 sketches a Delaunay refinement algorithm for a two-dimensional geometry. In contrast to advancing front algorithms, Delaunay refinement algorithms usually produce elements with good quality in the interior while having elements with low quality near the boundary or region interfaces. Additionally, there are Delaunay refinement algorithms which create meshes with mathematical guarantees for mesh element quality [127].

**Figure 3.3:** Overlaying grid mesh generation
$\begin{subfigure} % latex2html id marker 5821 [b]{0.32\textwidth} \centering \... ...igures/mesh_generation_quadtree_1} \caption{Starting geometry} \end{subfigure}$ $\begin{subfigure} % latex2html id marker 5828 [b]{0.32\textwidth} \centering \... ...s/mesh_generation_quadtree_2} \caption{Overlayed regular grid} \end{subfigure}$ $\begin{subfigure} % latex2html id marker 5835 [b]{0.325\textwidth} \centering ... ...h_generation_quadtree_3} \caption{Triangulation of grid cells} \end{subfigure}$ $\begin{subfigure} % latex2html id marker 5842 [b]{0.32\textwidth} \centering \... ...idth]{figures/mesh_generation_quadtree_4} \caption{Final mesh} \end{subfigure}$ The starting geometry is visualized in the first picture. At first, a regular square grid is laid over the geometry (picture two). Square grid cells which do not intersect the geometry boundary can trivially be decomposed into triangles. For all other square grid cells, a triangulation has to be found which respects the boundary (picture three). In contrast, a quadtree algorithm would recursively refine square grid cells which intersect with the geometry boundary, until the intersection is simple enough to construct a valid triangulation for that square grid cell. Elements near the geometry boundary in the final mesh have bad quality (picture four).

Grid, quad-, and octtree algorithms [81][82] use an overlaying regular grid, quad-, or octtree to construct mesh elements. Grid vertices are moved to the geometry boundary or region interfaces to ensure geometry-conformity. Figure 3.3 shows an example of a mesh generated by a mesh generation algorithm using an overlaying grid. Meshes generated by this algorithm produce elements with very high quality in the interior but elements with very bad quality near the boundary or region interfaces [60].

3.1.1 Simplex Mesh Generation