# Distributed Combinatorial Maps for Parallel Mesh Processing
## 3 \(n\)D Distributed Combinatorial Maps
### Definition of \(n\)D Distributed Combinatorial Maps  
An \(n\)D distributed combinatorial map can be defined as a set of independent \(n\)-maps which are called _blocks_. In an \(n\)-dmap: (a) each \(n\)-cell belongs to exactly one block; as a consequence, \(\beta_{i}\) links, for all \(i\), \(0\leq i<n\) are always defined between darts that belong to the same block; (b) some information is added for retrieving the \(\beta_{n}\) links between two \(n\)-cells that belong to two different blocks. Definition 1 gives its mathematical definition. Figure 4: Illustration of a configuration that can occur when using an adaptive subdivision in a hexahedral mesh (image from [28]). **Definition 1**. : _An \(nD\) distributed combinatorial map, \(DM\), is a set of \(k\) independent \(n\)-maps \(M^{b}=(D^{b},\beta_{1}^{b},\ldots,\beta_{n}^{b})\) and \(k\) labeling functions \(id^{b}\), \(b\in\{1,\ldots,k\}\). Each \(M^{b}\) is a block of \(DM\). The domains of functions \(id^{b}\) are subsets \(C^{b}\subseteq D^{b}\). Each dart in \(C^{b}\) is called a critical dart. \(DM\) satisfies the following properties:_  
1. \(C^{b}\) _must be a set of complete_ \((n-1)\)_-cells, i.e.,_ \(\forall d\in C^{b}\)_, all the darts of the_ \((n-1)\)_-cell containing_ \(d\) _must belong to_ \(C^{b}\)_;_
2. _each dart in_ \(C^{b}\) _belongs to the border of_ \(M^{b}\)_, i.e.,_ \(\forall d\in C^{b}\)_,_ \(d\) _is_ \(\mathsf{n}\)_-free;_
3. _for each critical dart_ \(d\) _in_ \(C^{b}\)_, there is exactly one critical dart_ \(d^{\prime}\) _in_ \(C^{c}\)_, with_ \(b\
eq c\)_, such that_ \(id^{b}(d)=id^{c}(d^{\prime})\)_. For all other critical darts_ \(d^{\prime\prime}\) _in any block_ \(z\)_,_ \(id^{b}(d)\
eq id^{z}(d^{\prime\prime})\)_;_
4. _for each pair of critical darts_ \(d,d^{\prime}\) _in blocks_ \(M^{b}\) _and_ \(M^{c}\) _such that_ \(id^{b}(d)=id^{c}(d^{\prime})\)_:_ \(\forall i\in\{0,\ldots,n-2\}\)_,_ \(id^{b}(\beta_{i}(d))=id^{c}(\beta_{i}^{-1}(d^{\prime}))\)_._  
Intuitively, a critical dart is a dart that is linked by \(\beta_{n}\) to a dart belonging to a different block. Note that only critical darts have a label and this label is global for all the different blocks \(M^{b}\), \(b\in\{1,\ldots,k\}\) (two different critical darts in a same block have two different labels, and only the two darts linked by \(\beta_{n}\) between two different blocks have the same label). Property (4) ensures that the labeling of different critical darts are compatible inside the two \((n-1)\)-cells that are separated in two different blocks. **Illustration with an example**. Figure 5 gives an example of a 3-dmap \(DM\) that represents the 3-map \(M\) of Figure 1b. \(DM\) has 3 blocks: \(M^{2}\) containing two cubes; \(M^{1}\) and \(M^{3}\) containing one cube. Each block \(M^{b}\), \(b\in\{1,2,3\}\) has 8 critical darts (labeled with lowercase letters). Looking at the properties of critical darts:  
* Property (1) can be verified as all critical darts of \(DM\) form complete faces of their block. * Property (2) can be verified as all critical darts of \(DM\) belong to the border of their block; each one corresponds to one face in \(M\) which is split in two in \(DM\). * Property (3) can be verified by checking that all critical darts that were linked by \(\beta_{n}\) in \(M\) have the same label in \(DM\), and we can verify that other pairs of critical darts have different labels. * Property (4) ensures that critical darts are labeled in a coherent way between the different blocks. In our example, critical darts of the top cube in block \(M^{2}\) are labeled a, b, c, and d. Corresponding darts in block \(M^{3}\) are also labeled a, b, c, and d. Starting from dart \(d\) labeled a in block \(M^{2}\) and dart \(d^{\prime}\) with the same label in block \(M^{3}\), we can check that darts \(\beta_{1}(d)\) and \(\beta_{0}(d^{\prime})\) have the same label b. Step by step, this ensures the coherent labeling of all the darts of the two faces.