Morton Code Computation in C++

buildBvh.cpp

// see also https://www.youtube.com/watch?v=LAxHQZ8RjQ4
#include <entt/entt.hpp>
#include <glm/vec3.hpp>
#include <glm/common.hpp>
#include <tuple>

template<int O, int...V>
constexpr uint64_t qstretch(uint64_t src)
{
    return (
        ((src<<(V*O))&(1ull<<(V*O+V)))
    |...);
}

constexpr uint64_t stretch3(int32_t src)
{
    uint64_t m = src & ((1<<20)-1);
    return qstretch<2,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19>(m ^ (1<<19));
}

inline uint64_t mortonCode(glm::ivec3 vec)
{
    return
        (stretch3(vec[0]) << 0) |
        (stretch3(vec[1]) << 1) |
        (stretch3(vec[2]) << 2)
    ;
}

struct Aabb { glm::vec3 bounds[2]; };
struct Center { glm::vec3 pos; };
struct Childs { entt::entity left, right; };
struct Generated {};
struct Top {};

void BuildBvh(entt::registry& reg)
{
    std::vector<std::tuple<uint64_t,entt::entity>> tups;
    for(auto&& [e,a,c] : reg.view<Aabb, Center>().each())
        tups.push_back({mortonCode(glm::ivec3(c.pos)),e});
    std::sort(tups.begin(),tups.end());
    std::vector<entt::entity> a,b;
    a.reserve(tups.size());
    for(auto [m,e] : tups) a.push_back(e);
    auto& sAabb = reg.storage<Aabb>();
    auto& sChilds = reg.storage<Childs>();
    auto& sGenerated = reg.storage<Generated>();
    while(a.size()>1)
    {
        b.clear();
        b.reserve(a.size()/2 + 1);
        auto ae = a.end(), ab = a.begin();
        while((ae-ab)>2)
        {
            entt::entity e1 = *ab++;
            entt::entity e2 = *ab++;
            entt::entity e3 = reg.create();
            Aabb a1 = sAabb.get(e1), a2 = sAabb.get(e2), a3;
            a3.bounds[0] = glm::min(a1.bounds[0],a2.bounds[0]);
            a3.bounds[1] = glm::max(a1.bounds[1],a2.bounds[1]);
            sAabb.emplace(e3) = a3;
            sGenerated.emplace(e3);
            b.push_back(e3);
        }
        if(ab!=ae) b.push_back(*ab);
        std::swap(a,b);
    }
    if(!a.empty())
        reg.emplace<Top>(a[0]);
}

mortonCode.cpp

// CC0 - Public Domain!
// Compute a morton code from an glm::ivec3 integer vector.
// The strech3 function consumes the least significant 9 bits and ignores everything above.
// If -O2 is passed to the compiler (GCC or Clang) this function will be cleverly optimized.
#include <glm/vec3.hpp>
#include <glm/common.hpp>

template<int O, int...V>
constexpr uint32_t qstretch(uint32_t src)
{
    return (
        ((src<<(V*O))&(1<<(V*O+V)))
    |...);
}

constexpr uint32_t stretch3(int32_t src)
{
    uint32_t m = src & ((1<<10)-1);
    return qstretch<2,0,1,2,3,4,5,6,7,8,9>(m ^ (1<<9));
}

uint32_t mortonCode(glm::ivec3 vec)
{
    return
        (stretch3(vec[0]) << 0) |
        (stretch3(vec[1]) << 1) |
        (stretch3(vec[2]) << 2)
    ;
}

mortonCode64.cpp

// CC0 - Public Domain!
// Compute a morton code from an glm::ivec3 integer vector.
// The strech3 function consumes the least significant 19 bits and ignores everything above.
// If -O2 is passed to the compiler (GCC or Clang) this function will be cleverly optimized.
#include <glm/vec3.hpp>
#include <glm/common.hpp>

template<int O, int...V>
constexpr uint64_t qstretch(uint64_t src)
{
    return (
        ((src<<(V*O))&(1ull<<(V*O+V)))
    |...);
}

constexpr uint64_t stretch3(int32_t src)
{
    uint64_t m = src & ((1<<20)-1);
    return qstretch<2,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19>(m ^ (1<<19));
}

uint64_t mortonCode(glm::ivec3 vec)
{
    return
        (stretch3(vec[0]) << 0) |
        (stretch3(vec[1]) << 1) |
        (stretch3(vec[2]) << 2)
    ;
}