Morton Transcoding
N-Dimensional Morton encoding and decoding for usize. Uses "magic bits" method, encoding and decoding are const and no_std.
Using a z-order curve (wikipedia) to index a multi-dimensional data structure keeps nearby data closer together in memory, improving cache efficiency compared to row or column-major storage.
This implementation focuses on encoding and decoding usize, as that is what is used to index into one dimensional data structures like Vecs and arrays.
The magic bits method inteleaves bits using an O(log(n)) operation, where n is the number of bits. See this blog for more details on encoding and decoding using magic bits.
use ;
let point = ;
let index = encode;
assert_eq!;
// This works for any number of dimensions.
let point = ; // 3D
assert_eq!;
let point = ; // 4D
assert_eq!;
let point = ; // 7D
assert_eq!;
Benchmarks
Compared to the morton_encoding crate, this crate is 100x faster for encoding 2D, 1000x faster for encoding 3D, ~50x faster for decoding 2D, and 100x faster for decoding 3D.
Check for yourself by using cargo bench!