5.1.1 Independent Mesh Generation and Interface Merging

The algorithms presented in this section start with already generated mesh templates which do not necessarily yield conforming instance interfaces (cf. Figure 4.4). To obtain a valid templated mesh, potential non-conformities have to be fixed. The process of making these interfaces conforming is called interface sewing and consists of two steps: Vertex merging and refinement.

The first algorithm, being vertex merging, eliminates non-conformities in instance interfaces by identifying vertices which are close to each other and merging them. This vertex merging algorithm requires an auxiliary algorithm, Algorithm 5.1, which creates a tuple of template vertex pairs $W$ which are not related to each other (Line 6), are close to each other (Line 7), and which are in a common geometry instance interface (Line 8). The relation used in Line 6 represents the boundary patch relation. Each element of the tuple is a tuple itself and includes the distance between the vertices, the template vertices, the template index, and the transformation functions (Line 9). In the end, the tuple $W$ is sorted in ascending order by the first argument, i.e., the vertex distance (Line 13).

Figure 5.1: Eliminating non-conformities by vertex merging

The initial structure instance of the templated structure has two non-conformities highlighted in red (top image). These two vertices are merged to their center in the output templated structure on the bottom resulting in a conforming structure instance (bottom image).

Algorithm 5.2 shows the vertex merging algorithm. The maximal distance between two vertices is specified with the parameter $d_{\max}$. At first, the helper variables $V$ (the set of all vertices which are in any instance interface), $\sim_V$ (a relation on $V$ where two vertices are related to each other, if there is a template boundary mapping which maps one to the other), and ${\mathbb{T}}_{\bm{x},\bm{y}}$ (the template boundary mappings which are used to create $\sim_V$) are set up. The set $V$ represents all template vertices which are included in any geometry instance interface (Line 3).

The binary relation $\sim_V$ represents the boundary patch relation, meaning that it links all template vertices which can be mapped to each other by a composition of template boundary mappings (Lines 6). The corresponding composition of template boundary mapping is stored in the ${\mathbb{T}}_{\bm{x},\bm{y}}$ variable sets (Line 7). The function $\operatorname{obtain\_close\_vertex\_pairs}$ (cf. Algorithm 5.1) is used to obtain a sorted tuple $W_1$ of all template vertex pairs which are included in the same geometry instance interfaces and are close to each other (Line 10). The vertex merging algorithm iteratively tests template vertex pairs if they can be moved to their center (Lines 15-19). Additionally, it also evaluates if the corresponding movement of the linked template vertices is valid (Lines 20-29). A vertex movement is considered to be valid, if the movement in the mesh template does not break the validity of that mesh template (cf. Section 5.2.2). If all movements are valid, they are applied (Lines 31-37), the corresponding equivalence classes of relation $\sim_V$ are merged, and the ${\mathbb{T}}_{\bm{x},\bm{y}}$ variables are updated (Lines 38-43). If a template vertex pair with valid movements is found, the sorted tuple $W_n$ is updated (Line 47) and the process starts again until the sorted tuple $W_n$ does not change any more (Line 49). The algorithm is visualized in Figure 5.1.

Figure 5.2: Vertex merging fails to fix all non-conformities

The structure instance has two non-conformities highlighted by the red circles. Although the vertices $T_{1,1}(v_3)$ and $T_{1,2}(v_1)$ can be considered close to each other, neither $v_1$ nor $v_3$ can be moved within template $X_1$ because it would break the geometry-conformity.

Although Algorithm 5.2 reduces non-conformities, it is, in general, not able fix all non-conformities as shown in Figure 5.2. Therefore, two additional algorithms are proposed (cf. Algorithm 5.3 and Algorithm 5.4), which fix all remaining non-conformities for simplex meshes by using refinement and element splitting techniques. It is sufficient to only handle vertex-in-facet non-conformities for triangle meshes (Algorithm 5.3). However, for tetrahedron meshes, non-conformities induced by line-line-intersections have to be handled as well (Algorithm 5.4).

Figure 5.3: Eliminating vertex-in-facet non-conformities

The initial templated structure has four non-conformities (highlighted in red) in its structure instance which cannot be fixed using the vertex merging algorithm (first picture). At first, the vertex $T_{1,1}^{-1} \circ T_{1,2}(\bm{v}_1)$ is inserted in the template edge $e_3$ resulting in the second templated structure (second picture). Then, $T_{2,2}^{-1} \circ T_{2,1}(\bm{v}_3)$ is inserted in the template edge $e_1$ resulting in the third templated structure (third picture). Using the same approach, all other non-conformities are eliminated by transforming and inserting the vertices in the geometry instance interface to the template facet which it intersects. The structure instance of the final templated structure (fourth picture) does not have any non-conformities. However, it can be seen that the element quality is poor. This algorithm terminates, because vertices are only inserted at locations via a finite number of compositions of boundary template mappings.

At first, Algorithm 5.3 generates the set of all vertex-face pairs $(\bm{v},f)$ in the structure instance, where their intersection is not empty and the vertex $\bm{v}$ is not a face of $f$ - and therefore creates a non-conformity (Line 5). As long as there are such pairs, there are non-conformities which must be fixed. For each vertex-face-pair $(\bm{v},f)$ and each template face $f_T$ of the structure instance face $f$, the vertex $\bm{v}_T = T_{i,j}^{-1}(\bm{v})$ is inserted into the corresponding mesh template (Line 11). For every template face $f_T$, every co-face cell $c_T$ is split into new cells by connecting $\bm{v}_T$ to all vertices of $c_T$. These new cells are inserted into the mesh template (Line 13) and $c_T$ is removed (Line 14). Depending on the position of $\bm{v}_T$ within $c_T$, a different number of new cells will arise. If $\bm{v}_T$ is in the interior of $f_T$, the number of new cells is equal to the cell dimension $d_c$. Otherwise, the number of new cells is higher, because there are additional co-face cells of $f_T$. Afterwards, newly introduced non-conformities are added to $V$ (Lines 16-22). Finally, all vertex-face pairs $(\bm{v},f)$ in $V$, where $f$ is no longer present, are removed from $V$ (Lines 24-29). This process is repeated, until $V = \emptyset$ and therefore all vertex-in-facet non-conformities have been eliminated. Although every iteration step inserts additional vertices and therefore potentially non-conformities, Algorithm 5.3 terminates: Vertices are only inserted at locations which are accessible from another vertex via compositions of boundary template mappings, which in turn is a finite number. The algorithm is visualized in Figure 5.3.

Algorithm 5.2 is applicable to quadrilateral and hexahedral meshes without modification. However, this is not true for Algorithm 5.3. Splitting a quadrilateral or hexahedron using edge bisection requires column and sheet operations [88][89]. These operations are, in contrast to simplex splitting, non-local and therefore potentially introduce additional non-conformities which have to be taken care of. Therefore, Algorithm 5.3 has to be modified (Lines 16-22) to include these newly introduced non-conformities.

Figure 5.4: Non-conformity induced by a line-line intersection

Although every vertex in the instance interface ${\operatorname{interf}}(T_{1,1},T_{1,2})$ is conforming, the intersection of edges $e_1$ and $e_2$ induces a non-conformity.

Algorithm 5.3 fixes all non-conformities of templated triangle meshes. However, for templated tetrahedron meshes, Algorithm 5.3 is not sufficient due to non-conformities induced by line-line-intersections at instance interfaces as visualized in Figure 5.4. Therefore, the algorithm for tetrahedrons requires a pre-processing step as presented in Algorithm 5.3.

At first, Algorithm 5.4 generates a set of line-line pairs $(l_1, l_2)$ in the structure instance, which do intersect and where the intersection vertex is not a face vertex of both $l_1$ and $l_2$ (Line 3). For each of these pairs $(l_1, l_2)$ the intersection vertex is calculated (line 5). This vertex is transformed to each template of $l_1$ and $l_2$ and inserted into these templates (Lines 6-12). As $L$ is finite, this algorithm also terminates. To fix all non-conformities of a templated tetrahedron mesh, Algorithm 5.4 is applied first, followed by Algorithm 5.3.

Although Algorithm 5.3 and Algorithm 5.4 fix all non-conformities for triangle and tetrahedron meshes, they have the following issues: First, the algorithms potentially insert a lot of new cell elements at or near the instance interfaces. This might lead to element sizes which are smaller than desired. Additionally, due to the construction rule for simplices in Algorithm 5.3, the newly created cell elements have low quality. These effects can be reduced by applying Algorithm 5.2 right before Algorithm 5.3 and Algorithm 5.4, because the number of non-conformities will potentially be reduced. Another downside of the algorithms presented in this section are numerical issues with the inclusion tests in Algorithm 5.3, Line 5, or the three-dimensional line-line intersections of Algorithm 5.4, Line 3. However, these operations benefit from previous work on numerical stability for computational geometry [24][65][80][120].

For the algorithms presented in this section, arbitrary volumetric mesh generation algorithms can be used without any modification, increasing the flexibility in the templated mesh generation process. However, as mentioned, the element quality of the resulting templated meshes is potentially inferior.