5.1.2 Templated Mesh Generation Based on the Boundary Patch Partition

In contrast to the algorithms presented in the previous section, this section focuses on first generating surface mesh templates which already result in a conforming structure instance. Afterwards, a mesh generation algorithm generates the volumetric meshes of the geometry templates without touching the surface meshes. The basic idea is the following:

(i)

The boundary patch partition, the boundary relation, and its quotient set of a templated geometry ${\Lambda}$ are created.

(ii)

All equivalence classes, being the elements of the quotient set, are sorted by their dimension.

(iii)

Starting from the lowest dimension, surface meshes for all elements of the quotient set are generated considering already generated surface meshes.

Special care has to be taken in step (iii). Ideally, any representative of an equivalence class can be chosen for surface mesh generation and the resulting mesh can be copied to all other members of the equivalence class to obtain a conforming structure instance. However, this is not true for templated geometries with an irregular instance graph (cf. Figure 4.11).

First, an auxiliary algorithm for initializing a templated mesh based on a templated geometry is presented, which initializes a templated mesh based on a templated geometry (Algorithm 5.5). For each geometry template an empty mesh template is created (Line 4) and all transformation functions and region indicators are copied (Lines 6-10).

The templated mesh generation algorithm for 2D templated triangle meshes is presented in Algorithm 5.6. At first, the resulting templated mesh is initialized based on the templated geometry (Line 3). Afterwards, the quotient set of the boundary patch relation is calculated (Line 4). For each vertex in each vertex equivalence class, the vertex is inserted into the corresponding mesh template (Lines 5-10). Next, for each line equivalence class, a representative $l_T$ is chosen (Line 12) and the vertices $V$ in the corresponding mesh template, which are subsets of $l_T$, are determined (Line 14). In Line 15, a line mesh $L$, which respects $V$, is generated for $l_T$. To support templated geometries with irregular instance graphs, the line mesh $L$ should have a reflective symmetry with a reflecting hyperplane which is orthogonal to the line $l_T$. The created line mesh is then inserted into the templates of the other elements of the line equivalence class (Lines 16-20). At last, a triangle mesh is generated for each mesh template using the created line meshes of the template surface (Line 24) and the resulting triangles are copied to the mesh template (Line 25). Any triangle mesh generation algorithm can be used for this step as long as it does not alter the surface. For example, the mesh generation tool Triangle offers an option which prohibits the insertion of additional vertices on the boundary [17].

Figure 5.5: Templated mesh generation using surface meshes

The initial templated structure consists of one template which is instanced three times (top picture). At first, the boundary patch partition is obtained where a surface mesh is generated for each boundary patch partition element (middle picture). Using this surface mesh, a volumetric mesh is created using an algorithm which does not alter the surface mesh. The final templated mesh is visualized on the bottom (bottom picture).

The resulting templated output structure of this algorithm is a valid templated mesh which geometry-conforms to the templated input geometry (cf. Section 4.3). Algorithm 5.6 terminates for all valid inputs and even works for templated geometries with irregular instance graphs. In comparison to the algorithms presented in the previous section, Algorithm 5.6 has fewer issues with poor element quality for elements on or near instance interfaces, because more explicit control is given to the surface mesh generation process. Additionally, fewer numerical issues arise.
For the inclusion tests, required in Line 14, information from the boundary patch generation process can be re-used to avoid explicit numerical inclusion tests. Figure 5.5 visualizes Algorithm 5.6 applied to the templated geometry presented in Figure 5.3.

Algorithm 5.7 generates 3D templated tetrahedral meshes based on templated geometries with regular instance graphs. This algorithm is similar to Algorithm 5.6. The major difference is in Line 15, where the line mesh is not required to be symmetric. In contrast to Algorithm 5.6, triangles have to be created for the boundary patches which is done in Lines 22-33. This process differs from the creation of line meshes in a way, that for the boundary patch triangle mesh generation previously created lines also have to be taken into account (Line 26). The triangle mesh generation (Line 27) is similar to the final triangle mesh generation in Algorithm 5.6 and therefore the same mesh generation algorithms and tools can be applied. Finally, tetrahedral meshes are generated for each template based on the surface meshes. Like in Algorithm 5.6, any tetrahedral mesh generation algorithm which does not alter the surface can be used here. Possible software choices are the advancing front mesh generation tool Netgen [9] or the Delaunay refinement mesh generation tool Tetgen [14] (with the input surface mesh preservation option enabled).

As mentioned above, Algorithm 5.7 does not support templated geometries with irregular instance graphs. To tackle this issue, the line surface mesh generated in Line 15 and the triangle surface mesh generated in Line 27 have to be symmetric. For the line surface mesh, the same approach as presented in Algorithm 5.6 can be used. However, for the triangle surface mesh, the generation process of a symmetric mesh is more complex as rotational symmetries can occur in addition to reflective symmetries. Algorithms for generating a symmetric mesh are presented in Section 6.2 and Section 6.3.

Algorithm 5.6 and Algorithm 5.7 can also be modified to generate all-quad or all-hex meshes. For all-quad meshes, the only difference in Algorithm 5.6 is the usage of the volumetric mesh generator in Line 24. For all-hex meshes, the triangle surface mesh generator and the tetrahedron volume mesh generator have to be exchanged with their all-quad and all-hex counterparts (Line 27 and Line 36). All-quad and all-hex approaches based on Paving or sweeping (cf. Section 3.1.2) are natural choices for surface and volumetric mesh generation (cf. Section 3.1.2).