Morton Codes

Morton Codes

under construction

Draw a line through each cell in a grid of any order and what you have is a space filling curve. What you have effectively done is map an x dimensional space to a one dimensional space. Encoding points in Morton order effectively places them on a z-order curve, named after it's jagged z-like pattern. A popular alternative to Morton codes are Hilbert codes; since they have fewer "jumps" in space, but come with cost of more computationally expensive encoding and decoding.

Representing

Lets create three unsigned integers of n bit size. Thinking in big endian, I'm going to represent the bits as:

x - Xn ... X3 : X2 : X1

y - Yn ... Y3 : Y2 : Y1

z - Zn ...  Z3 : Z2 : Z1

I'll be using using three dimensions, but the ideas can be translated down to two dimensions or up into a higher order.

A Morton code is created by interleaving the bits as such:

Zn:Yn:Xn ... Z3:Y3:X3 : Z2:Y2:X2 : Z1:Y1:X1

Here we run into a problem: what if x, y, and z are all 32 bit? 96 bits won't fit into a 32 or 64 bit uint, so we're going to have to cut corners.

Encoding

Assuming a uniform grid,  there will be space for:

16 bit - 5 bits x, 5 bits y, 5 bits z, 1 bit wasted

32 bit - 10 bits x, 10 bits y, 10 bits z, 2 bits wasted

64 bit - 21 bits x, 21 bits y, 21 bits z, 1 bit wasted

Which translates to:

16 bit - 32 cubed grid resolution

32 bit - 1024 cubed grid resolution

64 bit - 2097152 cubed grid resolution

Morton codes are represented using unsigned integers, each bit :

If out Morton code is represented with 32 bits then we have 10 bits for each dissension.

Z10:Y10:X10 ... Z3:Y3:X3 : Z2:Y2:X2 : Z1:Y1:X1

Negative Values

When dealing with negative values you're going to have to define the bounds of your world space. Lets assume that we'd like to center the grid having half of the values in each range being negative and the other half positive.

The x, y, and z ranges for each representation would be:

16 bit - [-16, 16]

32 bit - [-512, 512]

64 bit - [-1048576, 1048576]

Integer values only

Floating Point Mortons

Most of the time you probably won't be placing objects at integer intervals, so new we'll add a bit of floating point precision to the space, 

One solution is to multiply the floating point by a factor of ten and then cast it to an integer, but as we increase the precision the world space will shrink.

Using our previous 64 bit range of: [-1048576, 1048576]

1 decimal point corresponds to world dimensions of: [-104857.6, 104857.6]

2 decimal point corresponds to world dimensions of: [-10485.76, 10485.76]

3 decimal point corresponds to world dimensions of: [-1048.576, 1048.576]

This ends of being a trade of macro scale for micro scale. So now you'll have to tweak your world resolution to fit the precision you need.