morton.hpp

Go to the documentation of this file.

#pragma once

 
#include <cstdint>
#include <span>
#include <vector>
 
#include "orrery/backend/executor.hpp"
#include "orrery/core/types.hpp"
#include "orrery/core/vec3.hpp"
#include "orrery/core/vec3_span.hpp"
 
namespace orrery::solvers {

using MortonCode = std::uint64_t;

inline constexpr unsigned kMortonBitsPerAxis = 21;

inline constexpr std::uint32_t kMortonGridSize = std::uint32_t{1} << kMortonBitsPerAxis;

struct BoundingCube {
    core::Vec3 origin;

    core::Real size{};
 
    [[nodiscard]] core::Vec3 centre() const noexcept {
        return origin + core::Vec3{size / 2, size / 2, size / 2};
    }
};

[[nodiscard]] BoundingCube bounding_cube(core::Vec3Span<const core::Real> positions) noexcept;

[[nodiscard]] MortonCode spread_bits(std::uint32_t value) noexcept;

[[nodiscard]] MortonCode morton_code(std::uint32_t x, std::uint32_t y, std::uint32_t z) noexcept;

[[nodiscard]] MortonCode morton_code(core::Vec3 position, const BoundingCube& cube) noexcept;

[[nodiscard]] unsigned morton_octant(MortonCode code, unsigned level) noexcept;

struct MortonKey {
    MortonCode code{};
    core::Index index{};

    [[nodiscard]] friend constexpr auto operator<=>(const MortonKey&,
                                                    const MortonKey&) noexcept = default;
};

class MortonOrdering {
public:
    void build(core::Vec3Span<const core::Real> positions, backend::Executor* executor);

    [[nodiscard]] std::span<const MortonKey> keys() const noexcept { return keys_; }

    [[nodiscard]] const BoundingCube& cube() const noexcept { return cube_; }
 
private:
    void sort(backend::Executor* executor);
 
    std::vector<MortonKey> keys_;
    std::vector<MortonKey> scratch_;
    BoundingCube cube_;
};
 
} // namespace orrery::solvers