4.3 Boundary Patch Partition

Figure 4.7: Indirect neighbors

Although template $X_1$ and $X_3$ are not neighboring, the templated structure induces a dependence between those two templates because of the two instances of template $X_2$. If, for example, a new vertex is inserted on the left edge of template $X_1$, a vertex has to be inserted on the right of template $X_2$, because the interface ${\operatorname{interf}}(T_{1,2},T_{2,1})$ has to be conforming. In turn, this vertex insertion in template $X_2$ requires a new vertex on the left side of template $X_3$ to ensure the conformity of interface ${\operatorname{interf}}(T_{2,2},T_{1,3})$. Therefore, template $X_1$ and $X_3$ are indirect neighbors.

Let ${\Gamma}$ be a templated structure with mesh templates. According to Lemma 4.2, ${\Gamma}$ requires the conformity of two neighboring templates for ${\Gamma}$ to be a templated mesh. However, as visualized in Figure 4.7, a templated structure might induce dependencies between two templates which are not neighboring. If there is such a connection between two templates, these templates are said to be indirect neighbors. Any algorithm which only relies on Lemma 4.2 might induce additional non-conformities at interfaces when trying to fix a non-conformity between two direct neighboring templates. Therefore, there is no guarantee that such an algorithm terminates. An approach to resolve this issue is the boundary patch approach presented in the following.

Figure 4.8: Template boundary mapping

The template boundary mapping ${\mathbb{T}}_{T_{2,1},T_{1,1}}$ maps from a subset of the boundary of template $X_1$ to a subset of the boundary of template $X_2$.

A mapping between the boundary of two neighboring templates $X_i$ and $X_j$ with transformation function $T_{i,g}$ and $T_{j,h}$ can be defined.

Figure 4.9: Composition of template boundary mappings

The composition of template boundary mappings ${\mathbb{T}}_{T_{3,1},T_{2,2}} \circ {\mathbb{T}}_{T_{2,1},T_{1,1}}$ directly maps from a subset of the boundary of template $X_1$ to a subset of the boundary of template $X_3$, although $X_1$ and $X_3$ do not share a common instance interface. If the templates $X_1$ and $X_3$ are both centered and oriented in the same direction, the composition ${\mathbb{T}}_{T_{3,1},T_{2,2}} \circ {\mathbb{T}}_{T_{2,1},T_{1,1}}$ is the identity.

The template boundary mapping maps from $\operatorname{dom}({\mathbb{T}}_{T_{i,g},T_{j,h}}) = T_{j,h}^{-1}({\operatorna... ... T_{j,h})) \subseteq {\operatorname{bnd}}(\operatorname{templ}({\mathbb{X}},j))$ to $\operatorname{img}({\mathbb{T}}_{T_{i,g},T_{j,h}}) = T_{i,g}^{-1}({\operatorna... ... T_{j,h})) \subseteq {\operatorname{bnd}}(\operatorname{templ}({\mathbb{X}},i))$ and therefore maps boundary elements of one template to another neighboring template as visualized in Figure 4.8. For every template boundary mapping ${\mathbb{T}}_{T_{i,g}, T_{j,h}}$ the inverse is also a template boundary mapping: ${\mathbb{T}}_{T_{i,g}, T_{j,h}}^{-1} = {\mathbb{T}}_{T_{j,h}, T_{i,g}}$. Template boundary mappings can also be composed to map from a template to any indirect neighbor template as shown in Figure 4.9. The set of all template boundary mappings and all valid compositions of template boundary mappings of a templated structure ${\mathbb{X}}$ is denoted as ${\mathfrak{T}}_{\mathbb{X}}$.

Figure 4.10: Boundary patch partition

Boundary patch partition elements, which are induced by an instance interface, are visualized in green, yellow, and purple. Boundary patch partition elements (black) are elements which are not in any instance interface. The boundary of template $X_1$ is decomposed into six elements, two induced by the instance interface ${\operatorname{interf}}(T_{1,1},T_{1,2})$ (green), one induced by the instance interface ${\operatorname{interf}}(T_{1,2},T_{2,1})$ (yellow), and three elements which cover the rest of the boundary. The boundary of template $X_2$ is decomposed into five elements, two induced by the instance interface ${\operatorname{interf}}(T_{2,1},T_{2,2})$ (purple), one induced by the instance interface ${\operatorname{interf}}(T_{1,2},T_{2,1})$, and two remaining elements which cover the rest of the boundary. All points within any boundary patch partition element have the same (direct and indirect) neighbor configuration. For example, for every point in the yellow boundary patch partition element, the template $X_1$ is on one side and the template $X_2$ is on the other side.

Using the template boundary mappings (and all compositions of template boundary mappings), a partition of the template boundary is generated. The goal of this partition is to reflect the dependencies of a template with all direct and indirect neighbor templates. The boundary patch partition, visualized in Figure 4.10, is the coarsest partition of the template boundary, where each element of the partition has the same direct and indirect neighbors.

Algorithm 4.1 generates the boundary patch partition of a geometry template. At first (Line 3), all template boundary mappings and their compositions are obtained which map from the input template to any other template (including the input template). Then, the initial boundary patch partition of the template $\mathbb{B}_T$ is set to the boundary of the template (Line 4). For each template boundary mapping $f$ obtained in Line 3, a trivial template boundary partition is generated by using the domain of $f$ and its boundary complement (Line 6). This trivial partition is then refined with the boundary patch partition $\mathbb{B}_T$ (Line 7).

The boundary patch partition of a templated geometry ${\Lambda}$ is defined as the union of the boundary patch partitions of all templates: ${\operatorname{bndpart}}({\mathbb{X}}) := \bigcup_{G \in \operatorname{templ}({\mathbb{X}})} {\operatorname{bndpart}}({\mathbb{X}}, G)$. For every template boundary mapping, its domain can be represented as a union of boundary patch partition elements. This is also true for all compositions of template boundary mappings. Using the template boundary mapping, a binary relation of two boundary patch partition elements can be defined in the following way:

Lemma 3 (Boundary patch relation is an equivalence relation)   The boundary patch relation is an equivalence relation.

Proof. ${\sim}_{\mathbb{X}}$ is reflexive because ${\mathbb{T}}_{T_{i,g}, T_{i,g}} = {\mathbb{I}}$ is a valid template boundary mapping. ${\sim}_{\mathbb{X}}$ is symmetric, because ${\mathbb{T}}_{T_{i,g}, T_{j,h}}^{-1} = {\mathbb{T}}_{T_{j,h}, T_{i,g}}$. ${\sim}_{\mathbb{X}}$ is transitive by definition. Therefore, ${\sim}_{\mathbb{X}}$ is an equivalence relation. $\qedsymbol$

Because the boundary patch relation is an equivalence relation, it naturally has equivalence classes $[a]_{{\sim}_{\mathbb{X}}} := \{ x \in {\operatorname{bndpart}}({\mathbb{X}}) \vert a {\sim}_{\mathbb{X}}x\}$ and a quotient set: ${\operatorname{bndpart}}({\mathbb{X}}) / {\sim}_{\mathbb{X}}:= \{ [x] \vert x \in {\operatorname{bndpart}}({\mathbb{X}}) \}$. In the example given in Figure 4.10, boundary patch partition elements which are related to each other are visualized in the same color. Black elements are just related to themselves. The quotient set of that boundary patch relation includes every black element and one representative for each color (green, yellow, and purple).

The boundary patch partition and the boundary patch relation have the following properties:

Lemma 4 (Template boundary mapping properties)   Let ${\Gamma}$ be a templated mesh:

(i)

For every two elements $A$ and $B$ of the same equivalence class there is a composition of template boundary mappings $T$, which maps $A$ to $B$: $B = T(A)$.

(ii)

Each template boundary mapping ${\mathbb{T}}_{T_{i,g},T_{j,h}}$ maps all boundary mesh template elements which are included in the domain of ${\mathbb{T}}_{T_{i,g},T_{j,h}}$ to boundary mesh template elements which are included in the image of ${\mathbb{T}}_{T_{i,g},T_{j,h}}$:

$${\mathbb{T}}_{T_{i,g},T_{j,h}}\left( {\operatorname{bnd}}\left(X_... ..._j\right) \vert_{\operatorname{img}\left({\mathbb{T}}_{T_{i,g},T_{j,h}}\right)}$$ (4.5)

(iii)

Every template boundary ${\operatorname{bnd}}(X_i)$ of ${\Gamma}$ respects the boundary patch partition of the corresponding geometry template ${\operatorname{geo}}(X_i)$.

Proof. $$

(i)

If $A$ and $B$ are in the same equivalence class, there are sets $C_1, \dots, C_k$ for which there are boundary mappings which map $A$ to $C_1$, $C_1$ to $C_2$, $\dots$, and $C_k$ to $B$. Therefore, their composition maps $A$ to $B$.

(ii)

Follows from Lemma 4.1 (iii).

(iii)

For each composition of template boundary mappings $T$, which's domain is in template $X_i$, iteratively applying (ii) indicates that ${\operatorname{bnd}}(X_i)$ respects $\operatorname{dom}(T)$. From Lemma 2.3 follows, that ${\operatorname{bnd}}(X_i)$ also respects the boundary patch partition.

$\qedsymbol$

Due to these properties, the boundary patch partition of a templated geometry plays a central role in templated mesh generation and adaptation algorithms (cf. Chapter 5).

Figure 4.11: Issues due to boundary template mapping incompatibility

$T_{1,1}$ is a simple translation and $T_{1,2}$ is a combination of rotation and translation. If, for example, the template vertex highlighted by the red circle is moved up on the template boundary it will move up in the instance $T_{1,1}$ but down in the instance $T_{1,2}$ and therefore the structure instance is no longer conforming.

Two different compositions of template boundary mappings might be incompatible, as visualized in Figure 4.11. Formally, such an incompatibility occurs, when two valid compositions of template boundary mappings are different in an instance interface. In that case, the instance graph of the templated structure is called irregular.

In the example given in Figure 4.11, ${\mathbb{T}}_{T_{1,1}, T_{1,2}}$ is not equal to ${\mathbb{T}}_{T_{1,1}, T_{1,1}} = {\mathbb{I}}$ and therefore the instance graph is not regular. However, a non-trivial interface of two instances having the same template is not automatically problematic. For example, if $T_{1,2}$ is a combination of translation and reflection (similar to the example given in Figure 4.5), the instance graph is regular because ${\mathbb{T}}_{T_{1,1}, T_{1,2}} = {\mathbb{T}}_{T_{1,1}, T_{1,1}} = {\mathbb{I}}$.

From the definition above follows, that for every two representatives of an equivalence class (of the quotient set of the boundary patch relation of a templated structure with a regular instance graph) every composition of template boundary mappings is equal:

$$\forall [x]_{{\sim}_{\mathbb{X}}} \in {\operatorname{bndpart}}({\... ...all F_1, F_2 \in \operatorname{tf}({\mathbb{X}},A,B): F_1 \vert_B = F_2 \vert_B$$ (4.6)

For every two elements of the boundary patch partition $A,B$, which are related ( $A {\sim}_{\mathbb{X}}B$), all compositions of template boundary mappings $F \in \operatorname{tf}({\mathbb{X}}, A, B)$ have to fulfill $A = F(B)$. However, for templated structures with an irregular instance graph, there are compositions of boundary template mappings $F_1$ and $F_2$, which are not equal: $F_1 \vert_B \neq F_2 \vert_B$. Because of the definition of the boundary patch partition, $B$ is equal to $F_1^{-1}(F_2(B))$ but at the same time $F_1^{-1} \circ F_2$ is not the identity. Consequently, $F_1^{-1} \circ F_2$ has to be a symmetry for $B$. Although this is not an issue for templated geometries, it induces additional constraints for templated meshes. Algorithms for templated meshes with irregular instance graphs are therefore more challenging.