Given a pair of $(x, y, z)$ integer coordinates describing the anchor of a box in level $\ell$ an [[Octrees and Quadtrees]] (the anchor being by convention the bottom left corner in a box aligned with an $(x, y, z)$ coordinate system). The Morton Index is a single integer that encodes the three coordinates $x$, $y$, and $z$, and the level of the associated box. We assume the following preliminaries. - The Morton index is stored in an unsigned 64 bit integer. - The deepest Octree level is $\mathcal{L}^* = 16$. - The maximum number of Octants across each coordinate axis is $2^{16}$. This means we need 16 bits to store each coordinate direction. This gives 48 bits in total, leaving 16 bits for the level information, of which we only require 5 bits to store values up to 16. By restricting to 16 bits for the level information we can use small lookup tables to implement the Morton encoding as shown below. In the following we first discuss encoding a coordinate triplet $(x, y, z)$ into a Morton index. We ignore level information and Octree structure. We then discuss how Morton indices can be used to efficiently index all boxes in an Octree and to move between different levels. ## Encoding into a Morton index Assume our three values $(x, y, z)$ are written as bit sequences of the form $x = \dots x_3 x_2x_1x_0$, and similar for $y$, and $z$. Each value $x_i$ is a single bit. We encode the triplet $(x, y, z)$ into an integer $\tilde{m}$ in the following form $ \tilde{m} = \dots x_3y_3z_3x_2y_2z_1x_1y_1z_1x_0y_0z_0. $ Different variants of Morton indexing are possible by changing the order $x_i, y_i, z_i$ to another permutation such as $z_iy_ix_i$. To get the actual Morton index $m$ we want to append the level information. We are dealing with level information and using Morton indices inside Octrees in the next section. A fast and efficient way to implement the encoding is the use of three look-up tables, one for each coordinate direction. Assume that we have $x=32775$, which in binary form is $x = 0b1000000000000111$. We split the number into its upper 8 bits and its lower 8 bits, giving $x_u = 0b10000000=128$, and $x_{\ell} = 0b00000111$ = 7. $x_u$ and $x_{\ell}$ are separately converted into 24 bits by inserting zeros in between the bit positions of $x$ to create space for the $y$ and $z$ entries. The wanted bit sequence for $x_{u}$ is X_ENCODE[128] = 0b100000000000000000000000 = 8388608. The wanted bit sequence for $x_{\ell}$ is X_ENCODE[7] = 0b000000000000000100100100 = 292. The value $\tilde{m}$ is given as $\tilde{m} = (8388608 << 24) \, ||\, 292$. Hence, we take the value $x_u$, shift it by 24 bits and then add 292 with a bitwise `or` operation. The full Rust function to implement this encoding is given as follows. ```rust pub fn encode_morton(triplet: &[u64; 3]) -> u64 { let x = triplet[0]; let y = triplet[1]; let z = triplet[2]; let key: u64 = X_LOOKUP_ENCODE[((x >> BYTE_DISPLACEMENT) & BYTE_MASK) as usize] | Y_LOOKUP_ENCODE[((y >> BYTE_DISPLACEMENT) & BYTE_MASK) as usize] | Z_LOOKUP_ENCODE[((z >> BYTE_DISPLACEMENT) & BYTE_MASK) as usize]; let key = (key << 24) | X_LOOKUP_ENCODE[(x & BYTE_MASK) as usize] | Y_LOOKUP_ENCODE[(y & BYTE_MASK) as usize] | Z_LOOKUP_ENCODE[(z & BYTE_MASK) as usize]; key } ``` We have `BYTE_DISPLACEMENT=8` and `BYTE_MASK=255`. The latter ensures that only the wanted bits are included in the conversion. ## Decoding a Morton index To decode a Morton index we need to reverse the previous procedure. Remember that a Morton index without level information is given as $\tilde{m} = \dots x_3y_3z_3x_2y_2z_1x_1y_1z_1x_0y_0z_0$. Assume, we want to retrieve the bit information for $x$ from $\tilde{m}$. We proceed in blocks of nine bits. Consider the last 9 bits of $\tilde{m}$. For the relevant bits of $x$ we have the pattern $x_2 \_ \_ x_1 \_ \_ x_0 \_ \_$. With two bits between the x entries. The simplest way to decode this is to create a lookup table containing 512 entries for $x$. Each entry maps the corresponding bit-pattern of $x$ to the bit bittern $x_1x_1x_0$, filtering out the interleaved values for $y$ and $z$ bits. Once we have covered the first 9 bits we proceed to the next 9 and so on. A Rust function to decode a Morton index is given below. ```rust fn decode_key(morton: u64) -> [u64; 3] { let x = decode_key_helper(key, &X_LOOKUP_DECODE); let y = decode_key_helper(key, &Y_LOOKUP_DECODE); let z = decode_key_helper(key, &Z_LOOKUP_DECODE); [x, y, z] } fn decode_key_helper(key: u64, lookup_table: &[u64; 512]) -> u64 { const N_LOOPS: u64 = 7; // 8 bytes in 64 bit key let mut coord: u64 = 0; for index in 0..N_LOOPS { coord |= lookup_table[((key >> (index * 9)) & NINE_BIT_MASK) as usize] << (3 * index); } coord } ``` ## Morton Indexing for Octrees. In the following we assume that we have 48 bits in total available to index the boxes in the tree and that the deepest level is $\mathcal{L}^*=16$. We assign boxes values of the form $ \tilde{m}=x_{\mathcal{L}^-1}y_{\mathcal{L}^*-1}z_{\mathcal{L}^*-1}\dots x_1y_1z_1x_0y_0z_0 $ Assume we are at the root of an Octree. There is only a single box with anchor $(0, 0, 0)$. We assign this box the index $m=0$ by setting all 48 bits to zero. Let us recurse into level $\ell=1$. We now have 8 possible boxes, indexed by the triplet (x, y, z) with $x, y, z \in \{0, 1\}$, and we require 3 bits to uniquely identify each box. We assign each of the boxes on level $\ell=1$ a value of the form $ \tilde{m} = x_{\mathcal{L}^-1}y_{\mathcal{L}^*-1}z_{\mathcal{L}^*-1}000\dots000. $ where after the first three bits we have 45 zeros. All 64 boxes on level $\ell=2$ are indexed with a sequence of the form $ \tilde{m} = x_{\mathcal{L}^-1}y_{\mathcal{L}^*-1}z_{\mathcal{L}^*-1}x_{\mathcal{L}^-2}y_{\mathcal{L}^*-2}z_{\mathcal{L}^*-2}000\dots000, $ where now we have 42 zero bits. The higher three bits index the parent and the next three bits denote which of the 8 boxes the parent has been refined into. Repeating this procedure up to the deepest level $\mathcal{L}^*$ we arrive at a bit sequence of the form $\tilde{m}=x_{\mathcal{L}^-1}y_{\mathcal{L}^*-1}z_{\mathcal{L}^*-1}\dots x_1y_1z_1x_0y_0z_0$. Taking only the x-bits we have the integer value of the x-position, and so on. This is exactly the Morton encoding that we introduced previously. However, this is not quite sufficient to uniquely identify each box in the tree. For example, each level has a box with index $0$. To make the indexing unique we introduce level information. We have 48 bits for the Morton index, and use a further 15 bits for the level information (though we only need 5 of those bits). The full Morton index $m$ on the deepest level is now given as $ m = (\tilde{m} << 15 )\, ||\, 16. $ We shift the Morton index by 15 bits and add the level information via a bitwise `or` operation. ## Moving along an Octree with Morton indices Assume, we have a Morton index without level information $ \tilde{m}=x_{\mathcal{L}^-1}y_{\mathcal{L}^*-1}z_{\mathcal{L}^*-1}\dots x_1y_1z_1x_0y_0z_0 $ on the deepest level. To obtain the parent of this box we simply set the last three bits to zero. This gives $ \tilde{m}=x_{\mathcal{L}^-1}y_{\mathcal{L}^*-1}z_{\mathcal{L}^*-1}\dots x_1y_1z_1000 $ Certainly, for the index $m$ we also need to add the correct level information of the parent. The full Rust function for this operation is very simple. ```rust pub fn parent(morton: usize) -> usize { let level = morton && LEVEL_MASK; let morton = morton >> LEVEL_DISPLACEMENT; let parent_level = level - 1; let bit_multiplier = DEEPEST_LEVEL - parent_level; // Zeros out the last 3 * bit_multiplier bits of the Morton index let parent_morton_without_level = (morton >> (3 * bit_multiplier)) << (3 * bit_multiplier); let parent_morton = (parent_morton_without_level << LEVEL_DISPLACEMENT) | parent_level; parent_morton } ``` The `bit_multiplier` variable is necessary so that we make sure to zero out the correct number of bits depending on what level we are. Moving within a level is best achieved using the representation as (x, y, z) triplet. Simply decode the Morton index, move the triplet indices in the desired direction and encode the result again. Getting the descendents of a box that is not on the deepest level is also straight forward. We just get all the 8 possible combinations of Morton indices by filling the next lower three bits with values, and increase the corresponding level by $1$. A particularly simple special case is the first descendent of a Morton index. Since its next 3 bits are also zero, we only need to increase the level information. Hence we have $ m_{first\_descendent} = 1 + m. $