parry3d/utils/
morton.rs

1//! Morton encoding of 3D vectors.
2
3// From https://github.com/DGriffin91/obvhs/tree/main/src/ploc/morton.rs
4// MIT/Apache 2 license.
5
6use crate::math::Vector;
7
8//---------------------------------------------------
9// --- 21 bit resolution per channel morton curve ---
10//---------------------------------------------------
11
12#[inline]
13fn split_by_3_u64(a: u32) -> u64 {
14    let mut x = a as u64 & 0x1fffff; // we only look at the first 21 bits
15    x = (x | x << 32) & 0x1f00000000ffff;
16    x = (x | x << 16) & 0x1f0000ff0000ff;
17    x = (x | x << 8) & 0x100f00f00f00f00f;
18    x = (x | x << 4) & 0x10c30c30c30c30c3;
19    x = (x | x << 2) & 0x1249249249249249;
20    x
21}
22
23#[inline]
24/// Encode x,y,z position into a u64 morton value.
25/// Input should be 0..=2u32.pow(21) (or 1u32 << 21)
26fn morton_encode_u64(x: u32, y: u32, z: u32) -> u64 {
27    split_by_3_u64(x) | split_by_3_u64(y) << 1 | split_by_3_u64(z) << 2
28}
29
30#[inline]
31/// Encode a 3D position into a u64 morton value.
32/// Input should be 0.0..=1.0
33pub fn morton_encode_u64_unorm(p: Vector<f64>) -> u64 {
34    let p = p * (1 << 21) as f64;
35
36    #[cfg(feature = "dim2")]
37    return morton_encode_u64(p.x as u32, p.y as u32, 0);
38    #[cfg(feature = "dim3")]
39    return morton_encode_u64(p.x as u32, p.y as u32, p.z as u32);
40}