Linear representation of an octree using the Morton code

Oktotreev is a tree data structure, each node of which has eight descendants. Octree trees are used for spatial indexing, collision detection in three-dimensional space, definition of hidden surfaces, in ray tracing and the finite element method.


Oktotree can be represented as a hierarchical data structure or linearly.
In the hierarchical data structure there is a tree root, nodes and leaves. Each node stores pointers to its descendants.
In the linear representation, pointers are not used — various methods of coding elements are used and only tree leaves are stored.
One of the most common and efficient coding methods is the use of the Lebesgue curve (Z-curve) and the application of the Hilbert curve.
The advantage of the Hilbert curve is its continuity - the neighboring elements are arranged in series. The advantage of the Z-curve is the simplicity and speed of calculation, so it is often used in practice.


2D Lebesgue Curve
')

Three-dimensional Lebesgue curve


Two dimensional hubert curve


Three dimensional Hilbert curve

For coding elements using the Z-curve, the Morton code is used (usually the code is calculated for a node with minimal coordinates). The Morton code for the Z-curve is calculated by offsetting and mixing the bits of the binary representation of each of the coordinates.

An example of calculating the Morton code

Taking into account the properties of the Z-curve, for elements, it is necessary to store only the depth of the element (level in octream) and its order (location on the Z-curve). The elements of the array used to store the cells of the grid are entered into the depth of the element, and the index of the element determines its location on the Z-curve.
To store the depth of the element is enough to use 1 byte (tree depth 256). For many tasks, the depth of the tree 16 may be sufficient (the size of the minimum cell will be 2 ^ 15 = 32768 times smaller than the initial area). Then it’s enough to use 4 bits to store the cell.

To determine the real coordinates of an element, you must perform the following steps:
1. calculating the Morton code for an element
2. decoding
3. translation of the resulting index into the real value of each of the coordinates

Consider the algorithm on the example of coding each of the coordinates with 20 bits, that is, the resulting code of all three coordinates will occupy 60 bits.
Knowing the code and the depth of the previous element, you can calculate the code of the current element. The code of the first element is always 0. We define the offset for each depth level:

for ( unsigned char i = 0; i < 21; ++i ) { levelOffset[20 - i] = offset; offset *= 8; } 

Now we will determine the index of the element through the depth and the index of the previous element:

 unsigned long getElementIndex( const unsigned long prevIndex, const unsigned char prevLevel ) { return prevIndex + levelOffset[prevLevel]; } 

Decoding function:

 void decodeIndexXYZ( const unsigned long index, unsigned long iXYZ[3]) { iXYZ[0] = decodeIndex( index ); iXYZ[1] = decodeIndex( index >> 1 ); iXYZ[2] = decodeIndex( index >> 2 ); } unsigned long decodeIndex( const unsigned long index ) { unsigned long ind = index & 0x0249249249249249; ind = ( ind | ( ind >> 2 ) ) & 0x00C9219243248649; ind = ( ind | ( ind >> 2 ) ) & 0x00386070C0E181C3; ind = ( ind | ( ind >> 4 ) ) & 0x0003E007C00F801F; ind = ( ind | ( ind >> 10 ) ) & 0x000000FFC00003FF; ind = ( ind | ( ind >> 20 ) ) & 0x00000000000FFFFF; return ind; } 

iXYZ [0], iXYZ [1], iXYZ [2] - determine the coding order (in this case, first the x coordinate, then y, then z).
The constants and the number of steps in the decodeIndex function are determined by the number of bits and the dimension of space (in this example, the constants are given for three-dimensional space and 20 bits per coordinate).
There are various coding methods, examples on
Bit Twiddling Hacks
How to compute a 3D Morton number (interleave the bits of 3 ints)

To obtain real values ​​of the cell top with minimal coordinates, the resulting indices are multiplied by the step size. The step size is the size of the minimum allowable grid cell.
Cell size can be determined by its depth. The remaining values ​​are determined by adding the size of the elements to the corresponding minimum coordinates.

The element is divided by increasing its depth and inserting after it 7 elements of the same depth.
Combining - reducing the depth and removal of the next 7 elements.

Oktoderevo is an actively studied data structure and algorithms for working with it (searching for neighbors, intervals, visualization, etc.) become the subject of doctoral theses and research.