4.5 Mesh Data Structures for Templated Meshes

Similar to Section 2.4, mesh data structures for templated meshes are presented in this section. Let ${\Gamma}$ be a templated $n$-dimensional mesh. A trivial data structure approach is to simply store an array of meshes with each having a the set of transformation functions and a set of region IDs. However, this approach has the issue, that vertices, which are shared between two instances, cannot be detected in a stable way, because numerical tests are required. Keeping track of these vertex connections requires additional bookkeeping which in turn results in higher memory requirements. Therefore, two different data structures are presented, one using the simple approach and one with shared vertex bookkeeping.

The data structure in Listing 4.1 represents a templated mesh without shared vertex bookkeeping. The mesh data structure presented in Section 2.4 is reused for the mesh templates. Each rigid transformation function can be represented using an $n \times n$ matrix for the affine part of the transformation and an $n$-dimensional translation vector. To save additional memory, transformations in ${\mathbb{R}}^3$ can be represented using unit quaternions [69] instead of the transformation matrix and in ${\mathbb{R}}^2$, a single angle can be used. However, the data structure will be different for meshes in ${\mathbb{R}}^2$ and ${\mathbb{R}}^3$. The affine matrix and translation vector representation is used in this work. All transformation functions are stored in an array located in the TEMPLATED_MESH structure. For each mesh instance, the index of the corresponding transformation function is stored in the transformation_indices array and the region indicator is stored in the region_ids array. The total size of the templated mesh equals the sum of the size of all templates and all transformation functions. The additional memory space required for the pointers of transformation functions and all count variables is negligible.

The data structure in Listing 4.2 stores a templated mesh with additional shared vertex bookkeeping (SVB). Shared vertex connections are represented using an array of global vertices which are all vertices shared by at least two mesh instances. In other words, the global_vertices array holds all vertices which are in any mesh instance interface. The size of the global_vertices array therefore is equal to the number of global interface vertices times the geometric dimension $n$. For each mesh instance and for all vertices which are shared with any neighboring mesh instance, there is an additional mapping from the local mesh template vertices to the global vertices. If the $i$-th vertex of the template of a mesh instance is shared with another mesh, the pair $(i,j)$ is inserted in the local_to_global_vertex_mapping array of the corresponding mesh instance, where $j$ is the index of the global vertex in the global_vertices array. Using this mapping, any vertex which is shared can be uniquely identified without any numerical tests. For each local-to-global mapping, two integers, being the two vertex indices, are stored. The size of the local_to_global_vertex_mapping array therefore is equal to the number of shared local vertices times $2 \times {\operatorname{sizeof}}(\textnormal{int})$. The size of a mesh instance does not only depend on $n$, but also on the number of shared vertices with other mesh instances. The transformation functions are stored similar to the data structure without SVB, i.e., in a global array in the TEMPLATED_MESH_SVB structure. Each mesh instance stores the array index of the corresponding transformation function in the transformation_index variable.

Figure 4.13: Templated mesh stored with and without SVB

The templated mesh has two transformation functions ($T_{1,1}$ being a translation and $T_{1,2}$ being a combination of reflection and translation) where the three vertices $v_3$, $v_4$, and $v_5$ are shared by an instance interface. When using the data structure without SVB (Listing 4.1), only the mesh template $X_1$ is stored as described in Section 2.4. transformation_indices would be $(0,1)$ and region_ids would be equal to $(0,0)$. The two transformation functions, $T_{1,1}$ and $T_{1,2}$, are stored in the transformations array. When using the data structure with SVB (Listing 4.2), the mesh template $X_1$ as well as the transformations functions are stored the same way. The global_vertices array would include $T_{1,1}(v_3)$, $T_{1,1}(v_4)$, and $T_{1,1}(v_5)$. Therefore, the local_to_global_vertex_mapping array of the instance indicated by $T_{1,1}$ is equal to $((3,1),(4,2),(5,3))$, because the local vertex $v_3$ is associated with the global vertex $T_{1,1}(v_3)$ which is the first entry in the global_vertices array, $v_4$ with $T_{1,1}(v_4)$, and $v_5$ with $T_{1,1}(v_4)$. For similar reasons, the local_to_global_vertex_mapping array of the instance indicated by $T_{1,2}$ is also $((3,1),(4,2),(5,3))$.

The total size of a templated mesh with SVB is the sum of all mesh templates, all instances, all transformation functions, and the size of the global_vertices array. All other data types are negligible for sufficiently large meshes. An example for a templated mesh stored with both data structures is visualized in Figure 4.13. It can be seen, that the data structure with SVB requires more memory than the data structure without SVB. A comparison of memory usage of templated meshes is given in Chapter 7.