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: http://www-graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN
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.
The simplest is probably a lookup table, if you've 4K free space:
static uint32_t t [ 1024 ] = { 0, 0x1, 0x8, ... };
uint32_t m ( int a, int b, int c )
{
return t[a] | ( t[b] << 1 ) | ( t[c] << 2 );
}
The bit hack uses shifts and masks to spread the bits out, so each time it shifts the value and ors it, copying some of the bits into empty spaces, then masking out combinations so only the original bits remain.
for example:
x = 0xabcd;
= 0000_0000_0000_0000_1010_1011_1100_1101
x = (x | (x << S[3])) & B[3];
= ( 0x00abcd00 | 0x0000abcd ) & 0xff00ff
= 0x00ab__cd & 0xff00ff
= 0x00ab00cd
= 0000_0000_1010_1011_0000_0000_1100_1101
x = (x | (x << S[2])) & B[2];
= ( 0x0ab00cd0 | 0x00ab00cd) & 0x0f0f0f0f
= 0x0a_b_c_d & 0x0f0f0f0f
= 0x0a0b0c0d
= 0000_1010_0000_1011_0000_1100_0000_1101
x = (x | (x << S[1])) & B[1];
= ( 0000_1010_0000_1011_0000_1100_0000_1101 |
0010_1000_0010_1100_0011_0000_0011_0100 ) &
0011_0011_0011_0011_0011_0011_0011_0011
= 0010_0010_0010_0011_0011_0000_0011_0001
x = (x | (x << S[0])) & B[0];
= ( 0010_0010_0010_0011_0011_0000_0011_0001 |
0100_0100_0100_0110_0110_0000_0110_0010 ) &
0101_0101_0101_0101_0101_0101_0101_0101
= 0100_0010_0100_0101_0101_0000_0101_0001
In each iteration, each block is split in two, the rightmost bit of the leftmost half of the block moved to its final position, and a mask applied so only the required bits remain.
Once you have spaced the inputs out, shifting them so the values of one fall into the zeros of the other is easy.
To extend that technique for more than two bits between values in the final result, you have to increase the shifts between where the bits end up. It gets a bit trickier, as the starting block size isn't a power of 2, so you could either split it down the middle, or on a power of 2 boundary.
So an evolution like this might work:
0000_0000_0000_0000_0000_0011_1111_1111
0000_0011_0000_0000_0000_0000_1111_1111
0000_0011_0000_0000_1111_0000_0000_1111
0000_0011_0000_1100_0011_0000_1100_0011
0000_1001_0010_0100_1001_0010_0100_1001
// 0000_0000_0000_0000_0000_0011_1111_1111
x = ( x | ( x << 16 ) ) & 0x030000ff;
// 0000_0011_0000_0000_0000_0000_1111_1111
x = ( x | ( x << 8 ) ) & 0x0300f00f;
// 0000_0011_0000_0000_1111_0000_0000_1111
x = ( x | ( x << 4 ) ) & 0x030c30c3;
// 0000_0011_0000_1100_0011_0000_1100_0011
x = ( x | ( x << 2 ) ) & 0x09249249;
// 0000_1001_0010_0100_1001_0010_0100_1001
Perform the same transformation on the inputs, shift one by one and another by two, or them together and you're done.
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;
}
You can use the same technique. I'm assuming that variables contain 32-bit integers with the highest 22 bits set to 0 (which is a bit more restrictive than necessary). For each variable x containing one of the three 10-bit integers we do the following:
x = (x | (x << 16)) & 0x030000FF;
x = (x | (x << 8)) & 0x0300F00F;
x = (x | (x << 4)) & 0x030C30C3;
x = (x | (x << 2)) & 0x09249249;
Then, with x,y and z the three manipulated 10-bit integers we get the result by taking:
x | (y << 1) | (z << 2)
The way this technique works is as follows. Each of the x = ... lines above "splits" groups of bits in half such that there is enough space in between for the bits of the other integers. For example, if we consider three 4-bit integers, we split one with bits 1234 into 000012000034 where the zeros are reserved for the other integers. In the next step we split 12 and 34 in the same way to get 001002003004. Even though 10 bits doesn't make for a nice repeated division in two groups, you can just consider it 16 bits where you lose the highest ones in the end.
As you can see from the first line, you actually only need that for each input integer x it holds that x & 0x03000000 == 0.
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);
}