How to compute a 3D Morton number (interleave the

Question

I'm looking for a fast way to compute a 3D Morton number. This site has a magic-number based trick for doing it for 2D Morton numbers, but it doesn't seem obvious how to extend it to 3D.

So basically I have 3 10-bit numbers that I want to interleave into a single 30 bit number with a minimal number of operations.

Answer 1

The following code finds the Morton number of the three 10 bit input numbers. It uses the idee from your link and performs the bit spreading in the steps 5-5, 3-2-3-2, 2-1-1-1-2-1-1-1, and 1-1-1-1-1-1-1-1-1-1 because 10 is not a power of two.

......................9876543210
............98765..........43210
........987....56......432....10
......98..7..5..6....43..2..1..0
....9..8..7..5..6..4..3..2..1..0

Above you can see the location of every bit before the first and after every of the four steps.

public static Int32 GetMortonNumber(Int32 x, Int32 y, Int32 z)
{
    return SpreadBits(x, 0) | SpreadBits(y, 1) | SpreadBits(z, 2);
}

public static Int32 SpreadBits(Int32 x, Int32 offset)
{
    if ((x < 0) || (x > 1023))
    {
        throw new ArgumentOutOfRangeException();
    }

    if ((offset < 0) || (offset > 2))
    {
        throw new ArgumentOutOfRangeException();
    }

    x = (x | (x << 10)) & 0x000F801F;
    x = (x | (x <<  4)) & 0x00E181C3;
    x = (x | (x <<  2)) & 0x03248649;
    x = (x | (x <<  2)) & 0x09249249;

    return x << offset;
}

Answer 2

Good timing, I just did this last month!

The key was to make two functions. One spreads bits out to every-third bit. Then we can combine three of them together (with a shift for the last two) to get the final Morton interleaved value.

This code interleaves starting at the HIGH bits (which is more logical for fixed point values.) If your application is only 10 bits per component, just shift each value left by 22 in order to make it start at the high bits.

/* Takes a value and "spreads" the HIGH bits to lower slots to seperate them.
   ie, bit 31 stays at bit 31, bit 30 goes to bit 28, bit 29 goes to bit 25, etc.
   Anything below bit 21 just disappears. Useful for interleaving values
   for Morton codes. */
inline unsigned long spread3(unsigned long x)
{
  x=(0xF0000000&x) | ((0x0F000000&x)>>8) | (x>>16); // spread top 3 nibbles
  x=(0xC00C00C0&x) | ((0x30030030&x)>>4);
  x=(0x82082082&x) | ((0x41041041&x)>>2);
  return x;
}

inline unsigned long morton(unsigned long x, unsigned long y, unsigned long z)
{
  return spread3(x) | (spread3(y)>>1) | (spread3(z)>>2);
}

Answer 3

Here's a generator I've made in Ruby for producing encoding methods of arbitrary length:

def morton_code_for(bits)
  method = ''

  limit_mask = (1 << (bits * 3)) - 1
  split = (2 ** ((Math.log(bits) / Math.log(2)).to_i + 1)).to_i
  level = 1

  puts "// Coding for 3 #{bits}-bit values"

  loop do
    shift = split
    split /= 2
    level *= 2

    mask = ([ '1' * split ] * level).join('0' * split * 2).to_i(2) & limit_mask

    expression = "v = (v | (v << %2d)) & 0x%016x;" % [ shift, mask ]

    method << expression

    puts "%s // 0b%064b" % [ expression, mask ]

    break if (split <= 1)
  end

  puts
  print "// Test of method results: "
  v = (1 << bits) - 1
  puts eval(method).to_s(2)
end

morton_code_for(21)

The output is suitably generic and can be adapted as required. Sample output:

// Coding for 3 21-bit values
v = (v | (v << 32)) & 0x7fff00000000ffff; // 0b0111111111111111000000000000000000000000000000001111111111111111
v = (v | (v << 16)) & 0x00ff0000ff0000ff; // 0b0000000011111111000000000000000011111111000000000000000011111111
v = (v | (v <<  8)) & 0x700f00f00f00f00f; // 0b0111000000001111000000001111000000001111000000001111000000001111
v = (v | (v <<  4)) & 0x30c30c30c30c30c3; // 0b0011000011000011000011000011000011000011000011000011000011000011
v = (v | (v <<  2)) & 0x1249249249249249; // 0b0001001001001001001001001001001001001001001001001001001001001001

// Test of method results: 1001001001001001001001001001001001001001001001001001001001001