# Distributed Combinatorial Maps for Parallel Mesh Processing
## 4 A Parallel Algorithm of Mesh Processing Based on \(3\)-dmaps
### Generic Parallel Algorithm  
The considered algorithm is the adaptive hexahedral subdivision of a given 3D mesh. Considering a hexahedral mesh, the main principle is the following: (a) iterate through each hexahedron \(h\) of the mesh; (b) ask to an oracle if \(h\) must be subdivided or not; (c) if the answer is yes, subdivide \(h\) in 8 hexahedra (for a 1:8 subdivision). Note that this algorithm can not be accomplished by using half-edges data structure. Indeed, this model allows us only to describe surfaces (i.e., a set of faces glued together) embedded in 3D space, while the hexahedral subdivision method needs to represent volumes glued together. This main principle can be retrieved in Algorithm 1 corresponding to one parallel task of our parallel algorithm. \(k\) tasks are run independently and simultaneously, one for each block of the 3-dmap, generating some communication (exchanging messages) between the different parallel tasks. Looking at Algorithm 1, the first loop (line 1) iterates through each hexahedron \(h\) of the current block (corresponding to a part of the whole mesh). When \(h\) must be subdivided (this question is given to an oracle), we first split each edge of \(h\) in two (lines 3-10), then we split each face of \(h\) in four (lines 11-17). Then, \(h\) is split itself in eight hexahedra (line 18), and all the messages that \(M^{b}\) has received are read and handled before considering the next hexahedron (line 19). Note that for each edge (_resp._ face) to split, we first test if the edge (_resp._ face) is already subdivided or not (line 4, _resp._ line 12). Indeed, one cell of \(h\) can be already subdivided in a previous step when considering a hexahedron adjacent to \(h\). Note also that this could occur both for critical and non critical darts. The principle of Algorithm 1 is very simple. The only difficult parts concern the critical darts management (lines 6-10 for edges; 15-17 for faces). Indeed, when a hexahedron has no critical dart, its subdivision is only local to its block and thus it can be done locally without any problem. However, when the hexahedron has some critical darts, additional work must be done to guarantee the global validity of the 3-dmap. **Management of critical darts. ** Let us focus on the division of a face \(f\) having critical darts e.g., the face with critical darts labeled a,..., d in Figure 5. The two steps of this division are shown in Figure 6. To split \(f\), we need to:* split the four edges of \(f\) (line 5):
* this splits the four critical darts labeled a,..., d;
* the old darts are relabeled a00,..., d00 (line 9, _cf._ Figure 5(a));
* the new darts are labeled a01,..., d01 (line 10, _cf._ Figure 5(a));
* four messages are sent (line 8) in order to split also the corresponding edges in cluster \(M^{3}\) (which is mandatory in order to preserve the global validity of the 3-dmap);
* split \(f\) in four (line 14):
* the four corner darts of \(f\) are critical (by definition they are either all or none critical);
* the message \"split face\" with the labels of the four corner darts as parameter is sent to \(M^{3}\), the other block containing the critical darts. This guarantees that each face matches in both blocks (line 16);
* new darts created during the split of face \(f\) are all critical and are labeled in a unique way by using the label of the original darts of \(f\) (line 17, _cf._ Figure 5(b) to see how this labeling is done). The special way that the labeling and re-labeling of critical darts is done ensures that the properties of distributed combinatorial maps are preserved. When splitting an edge, all the darts of the edge are split. As illustrated in Figure 5(a), this can lead to splitting several critical darts. For each critical dart concerned by a split, a message is sent in order to perform the same modification in the other block having this critical dart. This message takes the label of the critical darts as parameter.