# Distributed Combinatorial Maps for Parallel Mesh Processing
## 5 Experiments  
In this section, we discuss the implementation and results of a hexahedral subdivision of a mesh using 3D distributed combinatorial maps.  
Given a polygon mesh of a closed orientable surface, we consider an initial coarse 3-dmap subdividing its bounding box into a small number of hexahedra. In this initial 3-dmap, the hexahedra are set in different blocks. Thus, our method has two parameters: the initial number of hexahedra, and the number of blocks \(k\). In our implementation, we did not try to optimize the way in which hexahedra are assigned to blocks, but this could be interesting in order to maximize the distribution of work load on the different computers. Then, each hexahedron that is intersected by the polygon mesh is recursively subdivided into 8 sub-volumes. Algorithm 1 is used in parallel on \(k\) computers, one computer for each block of the 3-dmap. This recursive subdivision is executed until either the hexahedron is no more intersected by the surface, or a certain criterion is satisfied. As criterion, we use either a limit of the depth of subdivision, or a limit on the total memory space occupied by the process. Whatever the criterion used, hexahedra are subdivided by level: we consider all hexahedra at depth \(i\) before considering hexahedra at depth \(i+1\).  
Finally, we remove all the hexahedra of the 3-dmap that are in the exterior of the mesh. To do so, the removal operation for 3-maps is used [45] for each hexahedron that is outside of the mesh. This operation erases all the darts of the given hexahedron. Darts previously linked by \(\beta_{3}\) with these removed darts become 3-free. Thanks to the use of a distributed combinatorial map, these removals can be done simultaneously between the different blocks because they are independent (each volume is contained in a single block). When a critical dart is removed in one block, a message is sent to indicate that this dart is no more critical in the other block.  
At the end of this process, the resulting 3-dmap represents an octree of the interior of the mesh, as illustrated in Figure 8.  
Our distributed combinatorial maps were implemented in C++ using the Cgal library [46]. Each block was stored by using the combinatorial map package [27]. The intersection test was performed using the efficient axis-aligned bounding boxes (AABB) tree. An AABB tree is a static data structure that stores a set of geometric objects, and that allows us to perform efficient intersection and  
Figure 8: A block of a 3-dmap obtained by the hexahedral subdivision of Bunny. We can see hexahedra with different levels of subdivision.  
distance queries against these objects [47]. Our goal is to integrate our implementation of distributed combinatorial maps in a future release of Cgal.  
For our experiments, we used six different polygon meshes (usually considered in computer graphics). These polygon meshes are depicted in Figure 9, where we give their number of faces. In all our experiments, we used the same number of initial hexahedra, given in the array below Figure 9.  
We implemented a parallel version of our subdivision and hexahedral removal algorithms by using independent processes, one per block of the distributed combinatorial map, using OpenMPI (MPI stands for \"Message Passing Interface\") to transfer messages, and used mpirun to execute parallel jobs in different computers [48].  
Our software was executed on the grid engine at the IN2P3 computing center [[https://cc.in2p3.fr/en/](https://cc.in2p3.fr/en/)]([https://cc.in2p3.fr/en/](https://cc.in2p3.fr/en/)), on a system made of 16 workers, each one having 32 \"Intel(R) Xeon(R) CPU E5-2698 v3 @ 2.30 GHz\" processors; with 128 GB memory for each worker. On this grid, the limit of parallel processes allowed to be run in parallel is 32, and each process is allowed to use at most 3 GB of memory.