Morton Code

It’s is often called Z-order curve and it’s because of the array elements access pattern during iteration from 0 to N. How it works is, depending on a number of dimensions we want to encode it uses every second or third bit to encode coordinate of one of the cardinal axis.

Here is an example of how to encode coordinates into morton code and how to decode it:

The advantage of using Morton Code rather than regular indexing method is that it’s very cache friendly when we are searching through cells that are neighbors to an arbitrary cell. It is much more likely that requesting any neighbor cell data will also contain data for other neigbors within a single cache line.

Please see below image by David Eppstein - Own work, CC0, https://commons.wikimedia.org/w/index.php?curid=53260980 for better understanding: