# Distributed Combinatorial Maps for Parallel Mesh Processing
## Preliminary Notions
### Adaptive Hexahedral Subdivision  
A lot of subdivision schemes have been proposed to adapt meshes, as the use of an adaptive mesh has several advantages. For example we can refine only interesting parts of a mesh, which reduces memory space and computational cost for the parts where a precise description is not required. These subdivision schemes have been used for example in several finite element applications based on hexahedral meshes. The simpler and the most used subdivision scheme is the subdivision 1:8, which is the one used in this paper.  
**Subdivision 1:8.** To subdivide a given hexahedron \(h\) (Figure 3a) in eight, the principle is the following: (1) split each edge of \(h\) in two (Figure 3b); (2) split each face of \(h\) in four (Figure 3c); (3) split \(h\) itself in eight (Figure 3d).  
**3-maps to represent hexahedral meshes.** Using a 3-map to represent an irregular hexahedral mesh has several advantages. (1) We can represent any configuration of hexahedra: there is no constraint on the difference of subdivision level between two adjacent hexahedra; (2) We can use and mix different subdivision schemes. For example, we can split a hexahedron in two, four or eight; but it is easy to consider other types of subdivision; (3) We can retrieve and iterate through all cells of the mesh; and for each cell we can retrieve all its incident and adjacent cells; (4) Several operations exist and can be used to compute some characteristics (both geometrical and topological) and to modify the mesh; (5) Furthermore, we can mix different types of cells in the same mesh. For instance, we can describe and handle a mesh having hexahedra, tetrahedra, pyramids and prisms.  
Figure 3: Hexahedral subdivision 1:8. (**a**) Initial hexahedron. (**b**) Split each edge in two. (**c**) Split each face in four. (**d**) Split the hexahedron in eight.  
Figure 2: Two parts of the 3-map illustrated in Figure 1b, where some darts are numbered. (**a**) Cube representing \(V_{0}\). (**b**) Face between \(V_{0}\) and \(V_{1}\).  
An adaptive subdivision method based on \(3\)-maps.Given a hexahedral mesh represented by a \(3\)-map, an adaptive subdivision method is given in [28] based on a \(1\):\(8\) subdivision of the hexahedra. Note that it is possible to subdivide each hexahedron independently, while keeping the \(3\)-map valid. More precisely, when a cell (edge or face) is split inside a hexahedron, corresponding cells inside adjacent hexahedra are subdivided accordingly in order to satisfy the property of \(3\)-maps in the way that volumes are glued together. This is illustrated in Figure 4. The central hexahedron \(h\) is not yet subdivided. Anyway, since some of its neighbors are already subdivided, some cells incident to \(h\) were already split during these previous subdivisions. This is for example the case for some edges incident to the top face of \(h\), and this is also the case for the face to the right of \(h\). When subdividing \(h\), it is possible to test which cells were already split or not (see [28]). Moreover, \(h\) can be subdivided correctly whatever the level of subdivision of the adjacent hexahedra of \(h\) are.