Skip to content
Arithmetic for morton ordering
C++ CMake
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
include Update BMI2 to be defined only with visual studio Jan 22, 2017
tests Update BMI2 to be defined only with visual studio Jan 22, 2017
.gitattributes 💥🐫 Added .gitattributes & .gitignore files May 11, 2015
.gitignore
.travis.yml Enable tests with TravisCI Jan 22, 2017
CMakeLists.txt Enable Travis CI Jan 21, 2017
LICENSE.txt initial commit May 11, 2015
README.md Enable tests with TravisCI Jan 22, 2017

README.md

Mortonlib

Build Status

A lib for basic arithmetic with morton code.

Encoding/Decoding

If BMI2 instructions set is available on your processor (intel i5, i7 and some Xeon), mortonlib will use pext and pdep instructions to encode/decode morton code. Else, we rely on a precomputed look-up table. This last method is slower but works on all processors. You can set the flag USE_BMI2 to define which strategy you want to use.

If you don't have BMI2 instructions and you don't have to encode coordinates greater than (256,256,256), you can use the morton3d_256(x, y, z) function which is a bit faster than the generic one.

//Encode 2d morton code
morton2 m0 = morton2(x, y);

//Encode 3d morton code
morton3 m1 = morton3(x, y, z);

//if x, y and z < 256 and USE_BMI2 not set
morton3 m2 = morton3d_256(x, y, z);

//Decode 3d morton code
int x, y, z;
m1.decode(x, y, z);

Additions, substractions, increments

You can add and substract morton codes without decoding and re-encoding them.

//Add two morton keys
morton3(0,0,0) + morton3(1,2,3) == morton3(1,2,3);

//Substract two morton keys
morton3(4,5,6) - morton3(1,2,3) == morton3(3,3,3);

If you want to increment or decrement a single coordinate, you can use inc() and dec() function, which are a little bit faster than generic add.

//Increment Y part of morton key
morton3(4,5,6).incX() == morton3(4,5,6) + morton3(1,0,0) == morton3(5,5,6);

//Decrement Y part of morton key
morton3(4,5,6).decY() == morton3(4,5,6) - morton3(0,1,0) == morton3(4,4,6);

Benchmarks

References

You can’t perform that action at this time.