Adapt to Delaunay Mesh

An algorithm is presented in this section, which adapts a templated mesh in a way that its structure instance is Delaunay. As shown in Section 4.4, it is not sufficient that all templates are Delaunay. Additionally, every facet in the boundary of a mesh template has to be template-aware locally Delaunay for ${\operatorname{AT}}({\Gamma})$ to be Delaunay (cf. Lemma 4.5).

Technique 5.8 recursively inserts vertices in template boundary facets to make them template-aware locally Delaunay. At first, all mesh templates are made Delaunay using flip and Delaunay refinement operations (Line 4). Then, the set of all template facets which are not template-aware locally Delaunay is determined (Line 7). For each template facet in , its centroid $\bm{v}$ is computed (Line 9). In Line 10 this centroid is inserted in the template facet using the Bowyer-Watson algorithm (cf. Section 3.2.3). For every template boundary facet $\tilde{f}$ , which is related to , the vertex $\bm{v}$ is inserted using a template composition of boundary mappings ${\mathbb{T}}_{\tilde{f},f}$ , which maps to $\tilde{\bm{v}}$ (Lines 11-16). The Bowyer-Watson algorithm preserves the Delaunay property of the mesh templates and does not introduce new vertices (except the centroid which is handled separately) and therefore does not break the conformity of the structure instance. This process is repeated, until is empty.

**Figure 5.16:** A templated mesh is made template-aware Delaunay
$\begin{subfigure} % latex2html id marker 9865 [b]{0.9\textwidth} \centering \i... ...ke_templated_mesh_delaunay_1} \caption{Initial templated mesh} \end{subfigure}$ $\begin{subfigure} % latex2html id marker 9871 [b]{0.90\textwidth} \centering \... ...mplated_mesh_delaunay_2} \caption{Mesh templates are Delaunay} \end{subfigure}$ $\begin{subfigure} % latex2html id marker 9877 [b]{0.90\textwidth} \centering \... ...ated_mesh_delaunay_3} \caption{Structure instance is Delaunay} \end{subfigure}$ A valid templated mesh with one mesh template is visualized (top picture). Neither the mesh template nor the structure instance is Delaunay (triangles which are not Delaunay are highlighted in red). At first, the mesh template is made Delaunay using algorithms presented in Section 3.2. The resulting mesh template is Delaunay but the structure instance is not (middle picture). Inserting vertices at template faces which are not template-aware locally Delaunay yields the final templated mesh, the structure instance of which is Delaunay (bottom picture).

**Figure 5.17:** The ping-pong encroachment effect near small angles
Starting with vertices $\bm{x}$ , $\bm{v}_1$ and $\bm{w}_1$ , bisecting the facet edge ${\operatorname{simplex}}(\bm{x}, \bm{w}_1)$ using its centroid $\bm{w}_2$ potentially results in an edge ${\operatorname{simplex}}(\bm{x}, \bm{v}_1)$ not being locally Delaunay. When inserting vertex $\bm{v}_2$ into that edge, the edge ${\operatorname{simplex}}(\bm{x},\bm{w}_2)$ might not be locally Delaunay and so on. This iterative process potentially never stops.

A visualization of Technique 5.8 is sketched in Figure 5.16. There is no formal guarantee that Technique 5.8 stops for arbitrary (valid) inputs. For geometries without acute angles, vertex insertion using the Bowyer-Watson algorithm does not influence other facets which are already template-aware locally Delaunay. However, for geometries with angles less or equal to $45\degree$ , a phenomenon called ping-pong encroachment potentially occurs as visualized in Figure 5.17. A technique called protection balls is used to avoid this issue for classical simplex meshes [90][119][128]. The same approach can also be applied to templated meshes, where the smallest protection ball of all instance vertices and edges is used to determine a better location for the vertex (Line 9).

5.2.5 Adapt to Delaunay Mesh