obvhs/ploc/
morton.rs

1// http://www.graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN
2// TODO evaluate Extended Morton Codes for High Performance Bounding Volume Hierarchy Construction:
3// https://www.dcgi.fel.cvut.cz/projects/emc/emc2017.pdf
4// https://www.highperformancegraphics.org/wp-content/uploads/2017/Papers-Session3/HPG207_ExtendedMortonCodes.pdf
5
6//---------------------------------------------------
7// --- 10 bit resolution per channel morton curve ---
8//---------------------------------------------------
9
10use glam::DVec3;
11
12#[inline]
13pub fn split_by_3_u32(a: u16) -> u32 {
14    let mut x = a as u32 & 0x3ff; // we only look at the first 10 bits
15    x = (x | x << 16) & 0x30000ff;
16    x = (x | x << 8) & 0x300f00f;
17    x = (x | x << 4) & 0x30c30c3;
18    x = (x | x << 2) & 0x9249249;
19    x
20}
21
22#[inline]
23/// Encode x,y,z position into a u64 morton value.
24/// Input should be 0..=2u16.pow(10) (or 1u16 << 10)
25/// (only included for reference, this isn't reasonably accurate for most BVHs)
26pub fn morton_encode_u32(x: u16, y: u16, z: u16) -> u32 {
27    split_by_3_u32(x) | split_by_3_u32(y) << 1 | split_by_3_u32(z) << 2
28}
29
30//---------------------------------------------------
31// --- 21 bit resolution per channel morton curve ---
32//---------------------------------------------------
33
34#[inline]
35pub fn split_by_3_u64(a: u32) -> u64 {
36    let mut x = a as u64 & 0x1fffff; // we only look at the first 21 bits
37    x = (x | x << 32) & 0x1f00000000ffff;
38    x = (x | x << 16) & 0x1f0000ff0000ff;
39    x = (x | x << 8) & 0x100f00f00f00f00f;
40    x = (x | x << 4) & 0x10c30c30c30c30c3;
41    x = (x | x << 2) & 0x1249249249249249;
42    x
43}
44
45#[inline]
46/// Encode x,y,z position into a u64 morton value.
47/// Input should be 0..=2u32.pow(21) (or 1u32 << 21)
48pub fn morton_encode_u64(x: u32, y: u32, z: u32) -> u64 {
49    split_by_3_u64(x) | split_by_3_u64(y) << 1 | split_by_3_u64(z) << 2
50}
51
52#[inline]
53/// Encode a DVec3 position into a u128 morton value.
54/// Input should be 0.0..=1.0
55pub fn morton_encode_u64_unorm(p: DVec3) -> u64 {
56    let p = p * (1 << 21) as f64;
57    morton_encode_u64(p.x as u32, p.y as u32, p.z as u32)
58}
59
60//---------------------------------------------------
61// --- 42 bit resolution per channel morton curve ---
62//---------------------------------------------------
63
64#[inline]
65pub fn split_by_3_u128(a: u64) -> u128 {
66    let mut x = a as u128 & 0x3ffffffffff; // we only look at the first 42 bits
67    x = (x | x << 64) & 0x3ff0000000000000000ffffffff;
68    x = (x | x << 32) & 0x3ff00000000ffff00000000ffff;
69    x = (x | x << 16) & 0x30000ff0000ff0000ff0000ff0000ff;
70    x = (x | x << 8) & 0x300f00f00f00f00f00f00f00f00f00f;
71    x = (x | x << 4) & 0x30c30c30c30c30c30c30c30c30c30c3;
72    x = (x | x << 2) & 0x9249249249249249249249249249249;
73    x
74}
75
76#[inline]
77/// Encode x,y,z position into a u128 morton value.
78/// Input should be 0..=2u64.pow(42) (or 1u64 << 42)
79pub fn morton_encode_u128(x: u64, y: u64, z: u64) -> u128 {
80    split_by_3_u128(x) | split_by_3_u128(y) << 1 | split_by_3_u128(z) << 2
81}
82
83#[inline]
84/// Encode a DVec3 position into a u128 morton value.
85/// Input should be 0.0..=1.0
86pub fn morton_encode_u128_unorm(p: DVec3) -> u128 {
87    let p = p * (1u64 << 42) as f64;
88    morton_encode_u128(p.x as u64, p.y as u64, p.z as u64)
89}
obvhs/ploc/morton.rs

obvhs/ploc/
morton.rs
