Search code examples
c++data-structuresoctree

Morton code to store 3D float postitions

I'm trying to implement what's explained in this article: http://devblogs.nvidia.com/parallelforall/thinking-parallel-part-iii-tree-construction-gpu/

// Expands a 10-bit integer into 30 bits
// by inserting 2 zeros after each bit.
unsigned int expandBits(unsigned int v)
{
    v = (v * 0x00010001u) & 0xFF0000FFu;
    v = (v * 0x00000101u) & 0x0F00F00Fu;
    v = (v * 0x00000011u) & 0xC30C30C3u;
    v = (v * 0x00000005u) & 0x49249249u;
    return v;
}

// Calculates a 30-bit Morton code for the
// given 3D point located within the unit cube [0,1].
unsigned int morton3D(float x, float y, float z)
{
    x = min(max(x * 1024.0f, 0.0f), 1023.0f);
    y = min(max(y * 1024.0f, 0.0f), 1023.0f);
    z = min(max(z * 1024.0f, 0.0f), 1023.0f);
    unsigned int xx = expandBits((unsigned int)x);
    unsigned int yy = expandBits((unsigned int)y);
    unsigned int zz = expandBits((unsigned int)z);
    return xx * 4 + yy * 2 + zz;
}

when I'm trying the Morton3D function with the provided example, (0.1010, 0.0111, 0.1100) it's returning 1479990 instead of 101011110010.

Am I missing something that is not explained here?

Thanks! -D

Solution

  • You are missing two main points:

    1. The sample numbers given in the article (0.1010, 0.0111, 0.1100) are actually written in binary. This means that 0.1010 is actually 0.5+0.125=0.625, 0.0111 is 0.25+0.125+0.0625=0.4375 and 0.1100 is 0.5+0.25=0.75. Put these in and you'll see.

    2. The sample figure uses only 4 bits for each component, for a total of 12 in the Morton coding, while the actual code uses 10 bits per component for a total of 30. So, in the result you get, disregard the top 2 bits of the result, and look at the rest of the bits and see if you can figure it out.

    By the way, the code in the article is correct and does what it says it does.