3

The first function encodes [x, y] as 64bit wide Morton code where x and y are 32bit wide integers using Interleave bits by Binary Magic Numbers.

What would be the reverse function?

void xy2d_morton_64bits(uint64_t x, uint64_t y, uint64_t *d)
{
    x = (x | (x << 16)) & 0x0000FFFF0000FFFF;
    x = (x | (x << 8)) & 0x00FF00FF00FF00FF;   
    x = (x | (x << 4)) & 0x0F0F0F0F0F0F0F0F; 
    x = (x | (x << 2)) & 0x3333333333333333;
    x = (x | (x << 1)) & 0x5555555555555555;

    y = (y | (y << 16)) & 0x0000FFFF0000FFFF;
    y = (y | (y << 8)) & 0x00FF00FF00FF00FF;
    y = (y | (y << 4)) & 0x0F0F0F0F0F0F0F0F;
    y = (y | (y << 2)) & 0x3333333333333333;
    y = (y | (y << 1)) & 0x5555555555555555;

    *d = x | (y << 1);
}

void d2xy_morton_64bits(uint64_t d, uint64_t *x, uint64_t *y)
{
    // ????
}
Paul R
  • 208,748
  • 37
  • 389
  • 560
Dawid Szymański
  • 775
  • 6
  • 15
  • 1
    The first function will not work. You have apparently confused pointers and values. Your compiler should definitively warn at least (int-ops on pointer). Also, why not return the result directly? What is `function`? – too honest for this site May 31 '15 at 17:51
  • Previously asked question http://stackoverflow.com/questions/4909263/how-to-efficiently-de-interleave-bits-inverse-morton – Weather Vane May 31 '15 at 17:55
  • possible duplicate of [2D morton code encode/decode 64bits](http://stackoverflow.com/questions/30539347/2d-morton-code-encode-decode-64bits). @WeatherVane: he asked the same question thrice within the last days. – too honest for this site May 31 '15 at 18:02
  • :) Olaf - of course u are rigth. Sorry. Made mistake in a hurry mixing javascript code with c. As a matter of fact it is not even my code but borrowed from my previuose post. Already edited. But the queston remains unanswered ... – Dawid Szymański May 31 '15 at 19:29
  • That's right, i'm asking the same question, or at least the same question because cant find the answer. Please help. – Dawid Szymański May 31 '15 at 19:33
  • All answers that i know about on stackoverflow concern 32bit wide Morton code, there is no answer to decode/encode functions concerning 64bit wide Morton codes. Please help. – Dawid Szymański May 31 '15 at 19:40
  • Finally decided to answer myself my own question. – Dawid Szymański May 31 '15 at 21:17
  • You already got the answer. _This_ little thinking yourself will be a great gain in experience for you. Until now, it looks as if you let others do that for you. Asking the same question again and again will not increase your credibility; people here are not stupid! – too honest for this site May 31 '15 at 22:26

1 Answers1

5
void xy2d_morton(uint64_t x, uint64_t y, uint64_t *d)
{
    x = (x | (x << 16)) & 0x0000FFFF0000FFFF;
    x = (x | (x << 8)) & 0x00FF00FF00FF00FF;
    x = (x | (x << 4)) & 0x0F0F0F0F0F0F0F0F;
    x = (x | (x << 2)) & 0x3333333333333333;
    x = (x | (x << 1)) & 0x5555555555555555;

    y = (y | (y << 16)) & 0x0000FFFF0000FFFF;
    y = (y | (y << 8)) & 0x00FF00FF00FF00FF;
    y = (y | (y << 4)) & 0x0F0F0F0F0F0F0F0F;
    y = (y | (y << 2)) & 0x3333333333333333;
    y = (y | (y << 1)) & 0x5555555555555555;

    *d = x | (y << 1);
}

// morton_1 - extract even bits

uint64_t morton_1(uint64_t x)
{
    x = x & 0x5555555555555555;
    x = (x | (x >> 1)) & 0x3333333333333333;
    x = (x | (x >> 2)) & 0x0F0F0F0F0F0F0F0F;
    x = (x | (x >> 4)) & 0x00FF00FF00FF00FF;
    x = (x | (x >> 8)) & 0x0000FFFF0000FFFF;
    x = (x | (x >> 16)) & 0xFFFFFFFFFFFFFFFF;
    return x;
}

void d2xy_morton(uint64_t d, uint64_t *x, uint64_t *y)
{
    *x = morton_1(d);
    *y = morton_1(d >> 1);
}
Dawid Szymański
  • 775
  • 6
  • 15