Spatial Partitioning - Real-Time Collision Detection - page 317

// n = ------98----76----54----32----10 : After (3)
// n = ----9--8--7--6--5--4--3--2--1--0 : After (4)
n=(n ∧ (n << 16)) & 0xff0000ff; // (1)
n=(n ∧ (n << 8)) & 0x0300f00f; // (2)

n=(n ∧ (n << 4)) & 0x030c30c3; // (3)

n=(n ∧ (n << 2)) & 0x09249249; // (4)

return n;

}

The equivalent code for interleaving 2D coordinates (for a quadtree) follows.

// Takes two 16-bit numbers and bit-interleaves them into one number
uint32 Morton2(uint32 x, uint32 y)
{

return (Part1By1(y) << 1) + Part1By1(x);

}

// Separates low 16 bits of input by one bit
uint32 Part1By1(uint32 n)
{

// n = ----------------fedcba9876543210 : Bits initially
// n = --------fedcba98--------76543210 : After (1)
// n = ----fedc----ba98----7654----3210 : After (2)
// n = --fe--dc--ba--98--76--54--32--10 : After (3)
// n = -f-e-d-c-b-a-9-8-7-6-5-4-3-2-1-0 : After (4)
n=(n ∧ (n << 8)) & 0x00ff00ff; // (1)

n=(n ∧ (n <<

4)) & 0x0f0f0f0f; // (2)

n=(n ∧ (n <<

2)) & 0x33333333; // (3)

n=(n ∧ (n << 1)) & 0x55555555; // (4)

return n;

}

If sufficient bits are available in the CPU registers, the calls to the support function
can be done in parallel. For example, using a modified Part1By1() function that
operates on 32-bit numbers giving a 64-bit result, the Morton2() function presented
previously can be written as:

uint32 Morton2(uint32 x, uint32 y)
{

// Merge the two 16-bit inputs into one 32-bit value
uint32 xy = (y << 16) + x;