get coordinates of z point-CodePudding

I'm working on an optimization problem. I have to traverse a 2D matrix using a z-order curve. So I should just get the x and y coordinates correspondent to a counter variable. One way is of course just using for loops to look at the bits of the counter but it's way too slow. Here there are fast implementations but they're made to get the z value (so the 'counter' value) of a coordinate tuple. Are there similar ways to do the other way around? From z to (x,y)? Or can I somehow use the previously linked resource for my goal with some workarounds?

The language I'm using is C.

CodePudding user response：

The page you link for implementations deals with 3D encoding. If I understand your question correctly, you want a 2D Morton decoder.

Here is a simple encoder/decoder pair for 16-bit coordinates (relatively easy to extend to 32-bits, either with a 128-bit type or with double the computations).

typedef struct xy16 {
    uint16_t x;
    uint16_t y;
} xy16;

uint32_t morton_encode(xy16 xy) {
    uint64_t result = xy.x | ((uint64_t)xy.y << 32);
    result |= (result << 8);
    result &= 0x00ff00ff00ff00ff;
    result |= (result << 4);
    result &= 0x0f0f0f0f0f0f0f0f;
    result |= (result << 2);
    result &= 0x3333333333333333;
    result |= (result << 1);
    result &= 0x5555555555555555;
    return (uint32_t)result | (result >> 31);
}

xy16 morton_decode(uint32_t morton) {
    uint64_t result = morton | ((uint64_t)morton << 31);
    result &= 0x5555555555555555;
    result |= (result >> 1);
    result &= 0x3333333333333333;
    result |= (result >> 2);
    result &= 0x0f0f0f0f0f0f0f0f;
    result |= (result >> 4);
    result &= 0x00ff00ff00ff00ff;
    result |= (result >> 8);
    xy16 xy = {(uint16_t)result, (uint16_t)(result >> 32)};
    return xy;
}

And here is a look-up table version.

xy16 morton_decode_lut(uint32_t morton) {
    static const uint8_t lut_x[] = {
        0x0, 0x1, 0x0, 0x1, 0x2, 0x3, 0x2, 0x3, 0x0, 0x1, 0x0, 0x1, 0x2, 0x3, 0x2, 0x3,
        0x4, 0x5, 0x4, 0x5, 0x6, 0x7, 0x6, 0x7, 0x4, 0x5, 0x4, 0x5, 0x6, 0x7, 0x6, 0x7,
        0x0, 0x1, 0x0, 0x1, 0x2, 0x3, 0x2, 0x3, 0x0, 0x1, 0x0, 0x1, 0x2, 0x3, 0x2, 0x3,
        0x4, 0x5, 0x4, 0x5, 0x6, 0x7, 0x6, 0x7, 0x4, 0x5, 0x4, 0x5, 0x6, 0x7, 0x6, 0x7,
        0x8, 0x9, 0x8, 0x9, 0xa, 0xb, 0xa, 0xb, 0x8, 0x9, 0x8, 0x9, 0xa, 0xb, 0xa, 0xb,
        0xc, 0xd, 0xc, 0xd, 0xe, 0xf, 0xe, 0xf, 0xc, 0xd, 0xc, 0xd, 0xe, 0xf, 0xe, 0xf,
        0x8, 0x9, 0x8, 0x9, 0xa, 0xb, 0xa, 0xb, 0x8, 0x9, 0x8, 0x9, 0xa, 0xb, 0xa, 0xb,
        0xc, 0xd, 0xc, 0xd, 0xe, 0xf, 0xe, 0xf, 0xc, 0xd, 0xc, 0xd, 0xe, 0xf, 0xe, 0xf,
        0x0, 0x1, 0x0, 0x1, 0x2, 0x3, 0x2, 0x3, 0x0, 0x1, 0x0, 0x1, 0x2, 0x3, 0x2, 0x3,
        0x4, 0x5, 0x4, 0x5, 0x6, 0x7, 0x6, 0x7, 0x4, 0x5, 0x4, 0x5, 0x6, 0x7, 0x6, 0x7,
        0x0, 0x1, 0x0, 0x1, 0x2, 0x3, 0x2, 0x3, 0x0, 0x1, 0x0, 0x1, 0x2, 0x3, 0x2, 0x3,
        0x4, 0x5, 0x4, 0x5, 0x6, 0x7, 0x6, 0x7, 0x4, 0x5, 0x4, 0x5, 0x6, 0x7, 0x6, 0x7,
        0x8, 0x9, 0x8, 0x9, 0xa, 0xb, 0xa, 0xb, 0x8, 0x9, 0x8, 0x9, 0xa, 0xb, 0xa, 0xb,
        0xc, 0xd, 0xc, 0xd, 0xe, 0xf, 0xe, 0xf, 0xc, 0xd, 0xc, 0xd, 0xe, 0xf, 0xe, 0xf,
        0x8, 0x9, 0x8, 0x9, 0xa, 0xb, 0xa, 0xb, 0x8, 0x9, 0x8, 0x9, 0xa, 0xb, 0xa, 0xb,
        0xc, 0xd, 0xc, 0xd, 0xe, 0xf, 0xe, 0xf, 0xc, 0xd, 0xc, 0xd, 0xe, 0xf, 0xe, 0xf
    };

    static const uint8_t lut_y[] = {
        0x0, 0x0, 0x1, 0x1, 0x0, 0x0, 0x1, 0x1, 0x2, 0x2, 0x3, 0x3, 0x2, 0x2, 0x3, 0x3,
        0x0, 0x0, 0x1, 0x1, 0x0, 0x0, 0x1, 0x1, 0x2, 0x2, 0x3, 0x3, 0x2, 0x2, 0x3, 0x3,
        0x4, 0x4, 0x5, 0x5, 0x4, 0x4, 0x5, 0x5, 0x6, 0x6, 0x7, 0x7, 0x6, 0x6, 0x7, 0x7,
        0x4, 0x4, 0x5, 0x5, 0x4, 0x4, 0x5, 0x5, 0x6, 0x6, 0x7, 0x7, 0x6, 0x6, 0x7, 0x7,
        0x0, 0x0, 0x1, 0x1, 0x0, 0x0, 0x1, 0x1, 0x2, 0x2, 0x3, 0x3, 0x2, 0x2, 0x3, 0x3,
        0x0, 0x0, 0x1, 0x1, 0x0, 0x0, 0x1, 0x1, 0x2, 0x2, 0x3, 0x3, 0x2, 0x2, 0x3, 0x3,
        0x4, 0x4, 0x5, 0x5, 0x4, 0x4, 0x5, 0x5, 0x6, 0x6, 0x7, 0x7, 0x6, 0x6, 0x7, 0x7,
        0x4, 0x4, 0x5, 0x5, 0x4, 0x4, 0x5, 0x5, 0x6, 0x6, 0x7, 0x7, 0x6, 0x6, 0x7, 0x7,
        0x8, 0x8, 0x9, 0x9, 0x8, 0x8, 0x9, 0x9, 0xa, 0xa, 0xb, 0xb, 0xa, 0xa, 0xb, 0xb,
        0x8, 0x8, 0x9, 0x9, 0x8, 0x8, 0x9, 0x9, 0xa, 0xa, 0xb, 0xb, 0xa, 0xa, 0xb, 0xb,
        0xc, 0xc, 0xd, 0xd, 0xc, 0xc, 0xd, 0xd, 0xe, 0xe, 0xf, 0xf, 0xe, 0xe, 0xf, 0xf,
        0xc, 0xc, 0xd, 0xd, 0xc, 0xc, 0xd, 0xd, 0xe, 0xe, 0xf, 0xf, 0xe, 0xe, 0xf, 0xf,
        0x8, 0x8, 0x9, 0x9, 0x8, 0x8, 0x9, 0x9, 0xa, 0xa, 0xb, 0xb, 0xa, 0xa, 0xb, 0xb,
        0x8, 0x8, 0x9, 0x9, 0x8, 0x8, 0x9, 0x9, 0xa, 0xa, 0xb, 0xb, 0xa, 0xa, 0xb, 0xb,
        0xc, 0xc, 0xd, 0xd, 0xc, 0xc, 0xd, 0xd, 0xe, 0xe, 0xf, 0xf, 0xe, 0xe, 0xf, 0xf,
        0xc, 0xc, 0xd, 0xd, 0xc, 0xc, 0xd, 0xd, 0xe, 0xe, 0xf, 0xf, 0xe, 0xe, 0xf, 0xf
    };

    xy16 xy;
    xy.x = lut_x[(morton >> 24) & 0xff];
    xy.y = lut_y[(morton >> 24) & 0xff];
    xy.x = xy.x << 4;
    xy.y = xy.y << 4;
    xy.x |= lut_x[(morton >> 16) & 0xff];
    xy.y |= lut_y[(morton >> 16) & 0xff];
    xy.x = xy.x << 4;
    xy.y = xy.y << 4;
    xy.x |= lut_x[(morton >> 8) & 0xff];
    xy.y |= lut_y[(morton >> 8) & 0xff];
    xy.x = xy.x << 4;
    xy.y = xy.y << 4;
    xy.x |= lut_x[morton & 0xff];
    xy.y |= lut_y[morton & 0xff];
    return xy;
}

I'm not sure which would be the fastest. The look-up tables can easily be extended to 2^16 = 65536 values to save 4 look-ups and shifts. I generated them by simply printing the values I get from the simpler morton_decode above. The same can be done to make a look-up table version of the encoder.

Demo