MortonCode.h

Go to the documentation of this file.

#pragma once
#include <cstdint>
 
namespace Cogs
{
  // Morton Code, aka. Z-order curve:
  //  https://en.wikipedia.org/wiki/Z-order_curve
   
  constexpr uint64_t mortonCode(uint16_t i, uint16_t j, uint16_t k)
  {
    uint64_t I, J, K;                     //       40       32       24       16        8        0
    I = i;                                // -------- -------- -------- -------- FEDCBA98 76543210
    J = j;
    K = k;
    I = (I << 16 | I) & 0x0000ff0000ff;   // -------- -------- FEDCBA98 -------- -------- 76543210
    J = (J << 16 | J) & 0x0000ff0000ff;
    K = (K << 16 | K) & 0x0000ff0000ff;
    I = (I << 8 | I) & 0x00f00f00f00f;    // -------- FEDC---- ----BA98 -------- 7654---- ----3210
    J = (J << 8 | J) & 0x00f00f00f00f;
    K = (K << 8 | K) & 0x00f00f00f00f;
    I = (I << 4 | I) & 0x0c30c30c30c3;    // ----FE-- --DC---- BA----98 ----76-- --54---- 32----10
    J = (J << 4 | J) & 0x0c30c30c30c3;
    K = (K << 4 | K) & 0x0c30c30c30c3;
    I = (I << 2 | I) & 0x024249249249;   // --F--E-- D--C--B- -A--9--8 --7--6-- 5--4--3- -2--1--0
    J = (J << 2 | J) & 0x024249249249;
    K = (K << 2 | K) & 0x024249249249;
    return K << 2 | J << 1 | I;
  }
 
  constexpr uint32_t mortonCode(uint16_t a, uint16_t b)
  {
     uint64_t res = a | (uint64_t(b) << 32);
     res = (res | (res << 8)) & 0x00ff00ff00ff00ff;
     res = (res | (res << 4)) & 0x0f0f0f0f0f0f0f0f;
     res = (res | (res << 2)) & 0x3333333333333333;
     res = (res | (res << 1)) & 0x5555555555555555;
     return uint32_t(res | (res >> 31));
  } 
}