sparkl2d_core/utils/
morton3.rs

1//! See https://stackoverflow.com/questions/50210379/3d-morton-encoding-using-bit-interleaving-conventional-vs-bmi2-instruction-set
2
3fn spread(mut w: u64) -> u64 {
4    w &= 0x00000000001fffff;
5    w = (w | w << 32) & 0x001f00000000ffff;
6    w = (w | w << 16) & 0x001f0000ff0000ff;
7    w = (w | w << 8) & 0x010f00f00f00f00f;
8    w = (w | w << 4) & 0x10c30c30c30c30c3;
9    w = (w | w << 2) & 0x1249249249249249;
10    w
11}
12
13pub fn morton_encode3(x: u32, y: u32, z: u32) -> u64 {
14    spread(x as u64) | (spread(y as u64) << 1) | (spread(z as u64) << 2)
15}
16
17///////////////// For Decoding //////////////////////
18
19fn compact(mut w: u64) -> u32 {
20    w &= 0x1249249249249249;
21    w = (w ^ (w >> 2)) & 0x30c30c30c30c30c3;
22    w = (w ^ (w >> 4)) & 0xf00f00f00f00f00f;
23    w = (w ^ (w >> 8)) & 0x00ff0000ff0000ff;
24    w = (w ^ (w >> 16)) & 0x00ff00000000ffff;
25    w = (w ^ (w >> 32)) & 0x00000000001fffff;
26    w as u32
27}
28
29pub fn morton_decode3(code: u64) -> [u32; 3] {
30    [compact(code), compact(code >> 1), compact(code >> 2)]
31}