- Libmorton is a C++ header-only library with methods to efficiently encode/decode 64, 32 and 16-bit Morton codes and coordinates, in 2D and 3D. Morton order is also known as Z-order or the Z-order curve.
- Libmorton is a lightweight and portable library - the only dependencies are standard C++ headers. Architecture-specific optimizations are available.
- More info and some benchmarks in these blogposts: Morton encoding, Libmorton and BMI2 instruction set
Just include the header include/libmorton/morton.h
. This will always have stub functions that point to the most efficient way to encode/decode Morton codes. If you want to test out alternative (and possibly slower) methods, you can find them in include/libmorton/morton2D.h
and include/libmorton/morton3D.h
. All libmorton functionality is in the libmorton
namespace to avoid conflicts.
// ENCODING 2D / 3D morton codes, of length 32 and 64 bits inline uint_fast32_t morton2D_32_encode(const uint_fast16_t x, const uint_fast16_t y); inline uint_fast64_t morton2D_64_encode(const uint_fast32_t x, const uint_fast32_t y); inline uint_fast32_t morton3D_32_encode(const uint_fast16_t x, const uint_fast16_t y, const uint_fast16_t z); inline uint_fast64_t morton3D_64_encode(const uint_fast32_t x, const uint_fast32_t y, const uint_fast32_t z); // DECODING 2D / 3D morton codes, of length 32 and 64 bits inline void morton2D_32_decode(const uint_fast32_t morton, uint_fast16_t& x, uint_fast16_t& y); inline void morton2D_64_decode(const uint_fast64_t morton, uint_fast32_t& x, uint_fast32_t& y); inline void morton3D_32_decode(const uint_fast32_t morton, uint_fast16_t& x, uint_fast16_t& y, uint_fast16_t& z); inline void morton3D_64_decode(const uint_fast64_t morton, uint_fast32_t& x, uint_fast32_t& y, uint_fast32_t& z);
No compilation / installation is required (just download the headers and include them), but I was informed libmorton is packaged for Microsoft's VCPKG system as well, if you want a more controlled environment to install C++ packages in.
In the standard case, libmorton only uses operations that are supported on pretty much any CPU you can throw it at. If you know you're compiling for a specific architecture, you might gain a speed boost in encoding/decoding operations by enabling implementations for a specific instruction set. Libmorton ships with support for:
- BMI2 instruction set: Intel: Haswell CPU's and newer. AMD: Ryzen CPU's and newer. Define
__BMI2__
before includingmorton.h
. This is definitely a faster method when compared to the standard case. - AVX512 instruction set (experimental): Intel Ice Lake CPU's and newer. Uses
_mm512_bitshuffle_epi64_mask
. Define__AVX512BITALG__
before includingmorton.h
. For more info on performance, see this PR.
When using MSVC, these options can be found under Project Properties -> Code Generation -> Enable Enhanced Instruction set.
When using GCC (version 9.0 or higher), you can use -march=haswell
(or -march=znver2
) for BMI2 support and -march=icelake-client
for AVX512 support.
The test
folder contains tools I use to test correctness and performance of the libmorton implementation. You can regard them as unit tests. This section is under heavy re-writing, but might contain some useful code for advanced usage.
You can build the test suite:
- With the included Visual Studio 2019 project in
test\msvc*
- Using make:
test\makefile
- Using Cmake (thanks @shohirose)
If you use libmorton in your published paper or work, please reference it, for example as follows:
@Misc{libmorton18, author = "Jeroen Baert", title = "Libmorton: C++ Morton Encoding/Decoding Library", howpublished = "\url{https://github.com/Forceflow/libmorton}", year = "2018"}
I'm always curious what libmorton ends up on. If you end up using it, send me an e-mail!
- Thomas Bläsius, Tobias Friedrich et al, 2019. Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs (link)
- Alexander Dieckmann, Reinhard Klein, 2018. Hierarchical additive poisson disk sampling (link)
- Sylvain Rousseau and Tamy Boubekeur, 2017. Fast lossy compression of 3D unit vector sets (PDF)
- Jan Watter, 2018. Generation of complex numerical meshes using space-filling curves (PDF)
- Esri
- Cesium Ion
- CLAIRE
- To @gnzlbg and his Rust implementation bitwise for finding bugs in the Magicbits code
- @kevinhartman made a C++14 library that supports N-dimensional morton codes morton-nd. He upstreamed a lot of fixes back to libmorton - thanks!
- Everyone making comments and suggestions on the original blogpost
- @Wunkolo for AVX512 implementation
- Fabian Giesen's post on Morton Codes
See Contributing.md
- Add morton operations like described here
- Write better test suite (with L1/L2 trashing, better tests, ...)
- A better naming system for the functions, because m3D_e_sLUT_shifted? That escalated quickly.