# Distributed Combinatorial Maps for Parallel Mesh Processing
## 4 A Parallel Algorithm of Mesh Processing Based on \(3\)-dmaps
### Generic Parallel Algorithm
Similarly, when splitting a face made of critical darts, the \"split face\" message is sent with the four labels of the four corner darts as parameter. The four labels are required in order to detect in the other block sharing this face if the face was already split or not. **Management of messages. ** At the end of Algorithm 1, when a hexahedron \(h\) has just been subdivided, messages sent from other blocks are read and handled (line 19). This is achieved in Algorithm 2. The main principle of this algorithm is to read all the messages that arrived in the message queue associated with block \(M^{b}\). There are only two different types of messages: \"split edge\" and \"split face\". For both types of message, we split the corresponding cell, while using the same rules for labeling and re-labeling of critical darts as the rules used in Algorithm 1 in order to preserve the compatibility between labeling of different blocks. This guarantees the global consistency of the 3-dmap \(DM\), since we apply exactly the same operations on the same cells in each different block of \(DM\). ```
Input:\(M^{b}\): one block of a 3-dmap \(DM\). Result: Receive and handle all the messages in the queue of \(M^{b}\). 1 while a message in existsdo
2 ifm is \"split edge\"(i)then
3 ifi is the label of a critical dart in \(M^{b}\)then
4 split edge \(e\) containing this critical dart in two edges \(e_{1}\) and \(e_{2}\);
5 foreachdart \(d\in e_{1}\)do
6 ifd is criticalthen
7 send message \"split edge\"(i);
8 label of dart \(d\gets i0\);
9 label of dart \(\beta_{1}(d)\gets i01\);
10
11
12
13 elseifm is \"split face\"(\(i_{1},i_{2},i_{3},i_{4}\))then
14 ifi_1...i_4 are 4 labels of critical darts in the same face of \(M^{b}\)then
15 split face \(f\) containing these darts in four faces;
16 label each new dart and mark them as critical;
17
18
```  
**Algorithm 2**Receive and handle all the messages of a given block. Looking at Algorithm 2, before splitting an edge, we first test if the given label is still associated with a critical dart (line 3). This is done simply by testing if the given label still exists in the corresponding associative array of critical darts. Note that this step is required because a critical dart could have already been subdivided (if one incident hexahedron was subdivided) before receiving this message. If the dart has already been subdivided, there is nothing to do because the global consistency of \(DM\) is already correct. When the critical dart with the given label exists, we split the edge containing this dart (line 4), label and relabel critical darts (lines 8 and 9) and send the \"split edge\" message for each critical dart split (line 7). We may wonder why we need to send the \"split edge\" message again. This is to correctly take into account the case where an edge in the initial 3-map is split into two (or more) edges in one block. Figure 6: Block \(M^{2}\) of the 3-dmap \(DM\) shown in Figure 5, for the two steps of the division of the face with critical darts labeled a,..., d. (**a**) After the split of the four edges. (**b**) After the split of the face. Such a case is illustrated in Figure 7. In this example, the central edge between the four cubes belongs to the 3 blocks \(M^{1},M^{2},M^{3}\), and is split in 2 edges in block \(M^{2}\). Indeed, in this block, there is no link between darts labeled a and d and darts labeled b and c (This is due to the definition of \(n\)-maps which allows us only to glue \(n\)-cells along (\(n\)-1)-cells.). In this example, let us suppose that the face containing the critical dart a should be split in four in block \(M^{2}\). Algorithm 1 starts to split the four edges of this face, and thus the face containing this critical dart. During this split, only critical darts labeled a and d are split since critical darts labeled b and c do not belong to the same edge in this block (even if they belong to the same edge in the global 3-map).