2.2 Meshes

A mesh is defined as a finite, face-complete element complex without any dangling elements.

Requirement (iii) ensures that cell elements are the only elements, which are not faces of any other element (except the cell itself). A mesh ${\mathcal{M}}$ is called $n$-dimensional, if ${\mathcal{M}}\in {\mathcal{P}}({\mathbb{R}}^n)$ and if ${{\operatorname{DIM}}_{\operatorname{cell}}}({\mathcal{M}}) = n$. If ${{\operatorname{DIM}}_{\operatorname{cell}}}({\mathcal{M}}) = n-1$, ${\mathcal{M}}$ is called an $n$-dimensional hull mesh or $n$-dimensional surface mesh. A mesh ${\mathcal{M}}$ with only simplex elements is called a simplex mesh, a two-dimensional (2D) mesh ${\mathcal{M}}$ with all cells being quadrilaterals is called an all-quad mesh, and a three-dimensional (3D) mesh ${\mathcal{M}}$ with all cells being hexahedrons is called an all-hex mesh.

Lemma 1 (Intersection of meshes)   The intersection of two meshes ${\mathcal{M}}_1$ and ${\mathcal{M}}_2$ is finite, face-complete, and conforming. If the union of both meshes ${\mathcal{M}}_1 \cup {\mathcal{M}}_2$ is conforming, then the underlying space of the intersection is also the intersection of the underlying spaces: ${\operatorname{us}}({\mathcal{M}}_1 \cap {\mathcal{M}}_2) = {\operatorname{us}}({\mathcal{M}}_1) \cap {\operatorname{us}}({\mathcal{M}}_2)$.

Proof. $$

(i)

To prove: $\vert{\mathcal{M}}_1 \cap {\mathcal{M}}_2\vert < \infty$:
${\mathcal{M}}_1 \cap {\mathcal{M}}_2$ is finite, because ${\mathcal{M}}_1$ and ${\mathcal{M}}_2$ are meshes and therefore finite.

(ii)

To prove: ${\mathcal{M}}_1 \cap {\mathcal{M}}_2$ is face-complete:
Every element $E \in {\mathcal{M}}_1 \cap {\mathcal{M}}_2$ is also an element of ${\mathcal{M}}_1$ and ${\mathcal{M}}_2$. Because ${\mathcal{M}}_1$ and ${\mathcal{M}}_2$ are meshes, they are both face-complete and ${\operatorname{faces}}(E)$ is a subset of ${\mathcal{M}}_1$ and ${\mathcal{M}}_2$. Therefore, ${\operatorname{faces}}(E)$ is also a subset of ${\mathcal{M}}_1 \cap {\mathcal{M}}_2$ and ${\mathcal{M}}_1 \cap {\mathcal{M}}_2$ is face-complete.

(iii)

To prove: ${\mathcal{M}}_1 \cap {\mathcal{M}}_2$ is conforming:
Let $E_1, E_2$ be two elements of ${\mathcal{M}}_1 \cap {\mathcal{M}}_2$ with non-empty intersection. Both elements are also in ${\mathcal{M}}_1$. Because ${\mathcal{M}}_1$ is a conforming mesh, $E_1 \cap E_2$ is a face of both $E_1$ and $E_2$. Therefore, ${\mathcal{M}}_1 \cap {\mathcal{M}}_2$ is conforming.

(iv)

To prove: ${\mathcal{M}}_1 \cup {\mathcal{M}}_2$ is conforming $\Rightarrow {\operatorname{us}}({\mathcal{M}}_1 \cap {\mathcal{M}}_2) = {\operatorname{us}}({\mathcal{M}}_1) \cap {\operatorname{us}}({\mathcal{M}}_2)$:
For every point $x \in {\operatorname{us}}({\mathcal{M}}_1 \cap {\mathcal{M}}_2)$ there is an element $E \in {\mathcal{M}}_1 \cap {\mathcal{M}}_2$, which contains $x$. $E$ is an element of both meshes ${\mathcal{M}}_1$ and ${\mathcal{M}}_2$ and $x$ is included in the underlying spaces of ${\mathcal{M}}_1$ and ${\mathcal{M}}_2$. Therefore, $x$ is also included in the intersection of the underlying spaces.

For every $x$ which is in ${\operatorname{us}}({\mathcal{M}}_1)$ and in ${\operatorname{us}}({\mathcal{M}}_2)$, there are elements $E_1 \in {\mathcal{M}}_1$ and $E_1 \in {\mathcal{M}}_2$, which both contain $x$. Because ${\mathcal{M}}_1 \cup {\mathcal{M}}_2$ is conforming, the intersection $E_1 \cap E_2$ (which also contains $x$) is a face of both $E_1$ and $E_2$. Therefore, $E_1 \cap E_2$ is included in both meshes ${\mathcal{M}}_1$ and ${\mathcal{M}}_2$ and also in their intersection ${\mathcal{M}}_1 \cap {\mathcal{M}}_2$. Ultimately, the set $E_1 \cap E_2$, which contains $x$, is a subset of the underlying space of the mesh intersection.

Therefore, ${\operatorname{us}}({\mathcal{M}}_1 \cap {\mathcal{M}}_2)$ is a subset of ${\operatorname{us}}({\mathcal{M}}_1) \cap {\operatorname{us}}({\mathcal{M}}_2)$ and ${\operatorname{us}}({\mathcal{M}}_1) \cap {\operatorname{us}}({\mathcal{M}}_2)$ is a subset of ${\operatorname{us}}({\mathcal{M}}_1 \cap {\mathcal{M}}_2)$, which make these two sets equal.

$\qedsymbol$

Figure 2.7: Mesh intersection

The intersection of these two meshes (colored in green), being two edges and an isolated vertex, is not a mesh, because the isolated vertex is a dangling element.

In general, however, the intersection of two meshes is not a mesh because it may contain dangling elements as shown in Figure 2.7. The second part of this Lemma states, that if the union of two meshes is conforming (i.e. the union is a mesh), then their intersection covers the same space as the intersection of the geometries of the meshes. This is not true for the intersection of two meshes, where their union is not conforming. For example, let ${\mathcal{M}}_1$ be a mesh which contains a line and its boundary vertices and ${\mathcal{M}}_2$ be a mesh which solely contains the vertex located at the center of the line. Then, ${\mathcal{M}}_1 \cap {\mathcal{M}}_2 = \emptyset$ but the intersection of ${\operatorname{us}}({\mathcal{M}}_1)$ and ${\operatorname{us}}({\mathcal{M}}_2)$ is the middle point of the line. The intersection of meshes will play an important role for the boundary patch partition in Section 4.3.

Similar to manifold partitions (cf. Appendix A), meshes can also be partitioned using the following approach:

A mesh partition does not necessarily consist of meshes with the same dimension. For example, a mesh containing one triangle (and all its faces) can have a mesh partition with the triangle (and all its faces) and all triangle edges (and all of their vertices). However, any cell of ${\mathcal{M}}$ is in exactly one element of a mesh partition of ${\mathcal{M}}$. Therefore, the underlying space of ${\mathcal{M}}$ is equal to the union of the underlying spaces of all elements of the partition.

Similar to geometries, meshes are also defined with multi-region support.

Figure 2.8: 2D multi-region mesh

For a multi-region mesh ${({\mathcal{M}}, {\xi})}$, $E \in {({\mathcal{M}}, {\xi})}$ is also written for $E \in {\mathcal{M}}$. An example of a 2D multi-region mesh is shown in Figure 2.8.

Lemma 2 (Region is a mesh)   For a multi-region mesh ${({\mathcal{M}}, {\xi})}$, every region ${\operatorname{region}}({({\mathcal{M}}, {\xi})}, i)$ is a mesh.

Proof. $$

(i)

$\vert{\operatorname{region}}({({\mathcal{M}}, {\xi})}, i)\vert$ is finite:
${\operatorname{region}}({({\mathcal{M}}, {\xi})}, i)$ is a subset of the finite mesh ${({\mathcal{M}}, {\xi})}$ and therefore also finite.

(ii)

${\operatorname{region}}({({\mathcal{M}}, {\xi})}, i)$ is face-complete:
Every element $E \in {\operatorname{region}}({({\mathcal{M}}, {\xi})}, i)$ is, by definition, also in ${\mathcal{M}}$. The faces of $E$ are included in ${\mathcal{M}}$, because ${\mathcal{M}}$ is face-complete. From the definition of ${\xi}$ follows, that for every faces $F$ of $E$, ${\xi}(F)$ contains $i$. Therefore, every face of $E$ is also in ${\operatorname{region}}({({\mathcal{M}}, {\xi})}, i)$ and ${\operatorname{region}}({({\mathcal{M}}, {\xi})}, i)$ is face-complete.

(iii)

${\operatorname{region}}({({\mathcal{M}}, {\xi})}, i)$ is conforming:
Let $E_1, E_2$ be two elements of ${\operatorname{region}}({({\mathcal{M}}, {\xi})}, i)$ with non-empty intersection. Then, $E_1$ and $E_2$ are also in ${\mathcal{M}}$. Because of the conformity of ${\mathcal{M}}$, $E_1 \cap E_2$ is a face of both $E_1$ and $E_2$ and because ${\operatorname{region}}({({\mathcal{M}}, {\xi})}, i)$ is face-complete, $E_1 \cap E_2$ is an element of ${\operatorname{region}}({({\mathcal{M}}, {\xi})}, i)$. Therefore, ${\operatorname{region}}({({\mathcal{M}}, {\xi})}, i)$ is conforming.

(iv)

${\operatorname{region}}({({\mathcal{M}}, {\xi})}, i)$ has no dangling elements (except cells):
From the definition of ${\xi}$ follows, that for every non-cell element $E$ of ${\operatorname{region}}({({\mathcal{M}}, {\xi})}, i)$ there is a co-face cell $C$ of $E$ in ${\operatorname{region}}({({\mathcal{M}}, {\xi})}, i)$. Therefore, ${\operatorname{region}}({({\mathcal{M}}, {\xi})}, i)$ has no dangling elements.

$\qedsymbol$

Every mesh ${\mathcal{M}}$ is also a multi-region mesh ${({\mathcal{M}}, {\xi})}$, where the mesh region indicator function ${\xi}$ maps every element to $\{1\}$. On the other hand, a multi-region mesh ${({\mathcal{M}}, {\xi})}$, with a mesh region indicator function ${\xi}$ mapping all elements to $\{1\}$, can be identified by the mesh ${\mathcal{M}}$. Therefore, all statements for multi-region meshes also hold for meshes.

Similar to geometry interfaces, the interface of mesh regions is equal to:

$${\operatorname{interf}}({({\mathcal{M}}, {\xi})},i_1, \dots ,i_k)... ...E \in {\mathcal{M}}, \forall x \in E: \{i_1, \dots, i_k\} \subseteq {\xi}(x) \}$$ (2.3)

The boundary ${\operatorname{bnd}}({\mathcal{M}})$ of a mesh ${\mathcal{M}}$ is again a mesh with ${{\operatorname{DIM}}_{\operatorname{cell}}}({\operatorname{bnd}}^\star ({\mathcal{M}})) = {{\operatorname{DIM}}_{\operatorname{cell}}}({\mathcal{M}})-1$. Because a mesh region is also a mesh, the definition of the boundary of a mesh region is the same as the boundary of a mesh.

A triangulation of a finite point set $S \subseteq {\mathbb{R}}^n$ is a special type of mesh which is important for constructing high quality meshes. Additionally, proofs for quality-guarantees of mesh generation algorithms usually require a triangulation [127].