2.2.2 Boundary Representation and Piecewise Linear Complexes

A geometry ${\mathcal{G}}\subseteq {\mathbb{R}}^n$ with ${\operatorname{DIM}}({\mathcal{G}}) = n$ can also be represented by its boundary. Because a geometry has to be a bounded set (cf. Appendix A), it is always clear on which side of the boundary the inside of the geometry is located. The geometry ${\mathcal{G}}$ can be reconstructed from a boundary representation by using the convex hull of the boundary ${\operatorname{conv}}({\operatorname{bnd}}({\mathcal{G}}))$. ${\operatorname{conv}}({\operatorname{bnd}}({\mathcal{G}}))$ is then intersected with the boundary ${\operatorname{bnd}}({\mathcal{G}})$ to obtain a finite number of connected manifolds: $\mathcal{M} = \{ M_1, \dots, M_k \}$. Each of these connected manifolds $M_i \in \mathcal{M}$ is discarded, if the manifold $M_i$ is outside of ${\operatorname{bnd}}({\mathcal{G}})$. Then, starting from the outside, the remaining manifolds in $\mathcal{M}$ are alternating either part of the geometry ${\mathcal{G}}$ or holes. This reconstruction process is visualized in Figure 2.3.

Figure 2.3: Reconstruction process of a boundary representation

The boundary is visualized on the left. At first, the convex hull is generated. Then, the boundary is used to slice the convex hull into a manifold partition. Manifold partition elements outside are discarded. Starting from outside, the remaining manifolds are alternating either part of the geometry or holes. Unassigned manifold partition elements are visualized gray, manifold partition elements assigned to the geometry are colored in blue.

Figure 2.4: Reconstruction process of a multi-region boundary representation

The union of all region boundaries and the hole and seed points are visualized on the left, using colored circles to depict seed points and white circles for hole points. At first, the convex hull is generated. Then, the union of the region boundaries is used to slice the convex hull into a manifold partition. Manifold partition elements outside of the union of the region boundaries or, where a hole point is inside, are discarded. All other manifold partition elements are assigned to the corresponding region using the seed points.

When representing multi-region geometries with boundaries, additional information is required, because the boundary of the geometry does not include information of the region interfaces. Therefore, each region has to be represented on its own with its boundary. Another approach is to unite all region boundaries and specify additional hole and seed points.

Let ${({\mathcal{G}}, {\widetilde{\xi}})}$ be a multi-region geometry, $B = \bigcup_{i=1}^{\operatorname{rc}({({\mathcal{G}}, {\widetilde{\xi}})})} {\... ...e{bnd}}^\star ({\operatorname{region}}({({\mathcal{G}}, {\widetilde{\xi}})},i))$ be the union of the region boundaries, $H = \{\bm{h}_1, \dots \bm{h}_m\} \subseteq {\mathbb{R}}^n$ be the set of hole points, and $S_i = \{\bm{s}_{i,1}, \dots, \bm{s}_{i,p_i}\} \subseteq {\operatorname{region}}({({\mathcal{G}}, {\widetilde{\xi}})},i)$ be the set of seed points for each region: Then $(B,H,S)$ is a boundary representation of ${({\mathcal{G}}, {\widetilde{\xi}})}$ using hole and seed points. In general, $B$ is not a manifold, because there does not exist a homeomorphism to ${\mathbb{R}}^n$ at points where a region interface and the geometry boundary meet. The reconstruction process for a multi-region geometry represented with its boundary and additional hole and seed points is similar to the algorithm above. The only difference is, that the hole points are used to discard additional manifolds and seed points are used to assign the remaining $M_i$ to a region, as shown in Figure 2.4. The reconstruction for multi-region geometries with boundary representation is unique when using hole and seed points.

In practice, the boundary itself is often described using piecewise linear functions (for linear geometries) or splines [118]. Boundary representations are very popular in industrial and CAD applications. In particular, two important types of boundary representations are named: triangular hulls and piecewise linear complexes (PLC). Triangular hulls in ${\mathbb{R}}^n$ are commonly used in computer graphics, but are also popular in CAD applications, e.g., the STereoLithography (STL) format [93].

A PLC is an abstraction of an element complex with the property that the boundary of an element and the intersection of two distinct elements can be the union of other elements rather than a single element. A PLC uses linear $k$-cells as mesh elements.

The underlying space of a PLC is a linear geometry. Therefore, a PLC represents a linear geometry and every polyhedron can be represented by a PLC. A PLC ${{\mathcal{P}}}$ is often represented with its boundary facets and additional hole and seed points to support multiple regions and holes. Additionally, PLCs play an important role in mesh generation algorithms based on Delaunay refinement (cf. Section 2.3) as a lot of mathematical statements for meshes have been proven for PLCs [127].