Heavypilgrim
Heavypilgrim

Reputation: 3

How to compute a 3D morton code from 3 128bit values?

I want to encode a position (x_u128,y_u128,z_u128) into one 3D morton code.

Therefore I chose the bit interleaving/"magic bits" method (also mentioned here for 3x21bit inputs 3d_morton_interleave ).

From my understanding each 128 bit value is spread by the shifting and bitmasking to result in a spreaded 3 * 128bits = 384 bits value:
(128bits,128bits,128bits) --> (384bits,384bits,384bits)
each interleaved by 2 zeros (like 0b..001000001001001 for the input 0b..0010111)

Those 3 spread values then need to be combined to the final morton code:
spread(x) | spread(y)<<1 | spread(z) << 2
Which is then 384bits large, correct?

I've then tried to expand the bitmasks to fit the 128bit input (e.g. add a first shift by 64 bits and the mask_1 and it didn't interleave as expected.
What's wrong?

Here's my code (most important part at the bottom of the spread(..) function):

use num::BigUint;
use num::One;

pub fn spread(v: u128) -> BigUint {
    //bitmask ... 32 ones 64 zeros 32 ones
    let mut mask_1 = BigUint::from(0x0000000000000000ffffffff00000000_u128);
    mask_1 <<= 128;
    mask_1 += 0x00000000ffffffff0000000000000000_u128;
    mask_1 <<= 128;
    mask_1 += 0xffffffff0000000000000000ffffffff_u128;

    //bitmask 0b...11111111 11111111 00000000 00000000 00000000 00000000 11111111 11111111
    let mut mask_2 = BigUint::from(0x00000000ffff00000000ffff00000000_u128);
    mask_2 <<= 128;
    mask_2 += 0xffff00000000ffff00000000ffff0000_u128;
    mask_2 <<= 128;
    mask_2 += 0x0000ffff00000000ffff00000000ffff_u128;

    //bitmask 0b...11111111 00000000 00000000 11111111
     let mut mask_3 = BigUint::from(0x0000ff0000ff0000ff0000ff0000ff00_u128);
    mask_3 <<= 128;
    mask_3 += 0x00ff0000ff0000ff0000ff0000ff0000_u128;
    mask_3 <<= 128;
    mask_3 += 0xff0000ff0000ff0000ff0000ff0000ff_u128;

    //bitmask 0b...1111000000001111000000001111
    let mut mask_4 = BigUint::from(0x00f00f00f00f00f00f00f00f00f00f00_u128);
    mask_4 <<= 128;
    mask_4 += 0xf00f00f00f00f00f00f00f00f00f00f0_u128;
    mask_4 <<= 128;
    mask_4 += 0x0f00f00f00f00f00f00f00f00f00f00f_u128;

    //bitmask 0b...11000011000011
    let mut mask_5 = BigUint::from(0x0c30c30c30c30c30c30c30c30c30c30c_u128);
    mask_5 <<= 128;
    mask_5 += 0x30c30c30c30c30c30c30c30c30c30c30_u128;
    mask_5 <<= 128;
    mask_5 += 0xc30c30c30c30c30c30c30c30c30c30c3_u128;

    //bitmask 0b...1001001001
    let mut mask_6 = BigUint::from(0x14924924924924924924924924924924_u128);
    mask_6 <<= 128;
    mask_6 += 0x92492492492492492492492492492492_u128;
    mask_6 <<= 128;
    mask_6 += 0x49249249249249249249249249249249_u128;

    let mut value = BigUint::from(v);
    value = (value.clone() | (value << 64)) & mask_1;
    value = (value.clone() | (value << 32)) & mask_2;
    value = (value.clone() | (value << 16)) & mask_3;
    value = (value.clone() | (value << 8)) & mask_4;
    value = (value.clone() | (value << 4)) & mask_5;
    value = (value.clone() | (value << 2)) & mask_6;
    return value;
}

pub fn combine_spread(x_spread: BigUint, y_spread: BigUint, z_spread: BigUint) -> BigUint {

    let result = x_spread | y_spread << 1 | z_spread << 2;

    return result;
}

Upvotes: 0

Views: 90

Answers (0)

Related Questions