EBGeometry_PackedBVH.hpp

Go to the documentation of this file.

// SPDX-FileCopyrightText: 2022 Robert Marskar <robert.marskar@sintef.no>
//
// SPDX-License-Identifier: GPL-3.0-or-later
 
#ifndef EBGEOMETRY_PACKEDBVH_HPP
#define EBGEOMETRY_PACKEDBVH_HPP
 
// Std includes
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <memory>
#include <type_traits>
#include <utility>
#include <vector>
 
#if defined(__SSE4_1__) || defined(__AVX__)
#include <immintrin.h>
#endif
 
// Our includes
#include "EBGeometry_Array.hpp"
#include "EBGeometry_BVHQuery.hpp"
#include "EBGeometry_BoundingVolumes.hpp"
#include "EBGeometry_Macros.hpp"
#include "EBGeometry_Math.hpp"
#include "EBGeometry_PODVector.hpp"
#include "EBGeometry_Pool.hpp"
#include "EBGeometry_Vec.hpp"
 
namespace EBGeometry {
 
namespace SFC {
struct Morton;
} // namespace SFC
 
namespace BVH {
 
enum class Construction
{
  CentroidSplit, 
  MidpointSplit, 
  SAH,           
  ClusterSAH,    
  Morton,        
  Nested,        
  Hilbert        
};
 
struct ClusterSpec
{
  size_t maxClusterSize = 8; 
};
 
struct ConstructionOptions
{
  size_t      maxLeafSize    = 0; 
  size_t      targetLeafSize = 0; 
  ClusterSpec cluster{};          
};
 
inline constexpr size_t HostTraversalDepth = 256;
 
inline constexpr size_t DeviceTraversalDepth = 32;
 
template <typename T>
[[nodiscard]] constexpr size_t
DefaultBranchingRatio() noexcept
{
  static_assert(std::is_floating_point_v<T>, "BVH::DefaultBranchingRatio requires a floating-point T");
 
  return 4;
}
 
template <typename T>
[[nodiscard]] constexpr size_t
HostBranchingRatio() noexcept
{
  static_assert(std::is_floating_point_v<T>, "BVH::HostBranchingRatio requires a floating-point T");
#if defined(__AVX512F__)
  if constexpr (std::is_same_v<T, double>) {
    return 8;
  }
  else {
    return 16;
  }
#elif defined(__AVX__)
  if constexpr (std::is_same_v<T, double>) {
    return 4;
  }
  else {
    return 8;
  }
#else
  return 4;
#endif
}
 
template <class T, class P, class BV, size_t K>
class TreeBVH;
 
template <class P>
using PrimitiveList = std::vector<std::shared_ptr<const P>>;
 
template <class T, class P, size_t K>
class PackedBVH;
 
template <class P, class BV>
using PrimAndBV = std::pair<std::shared_ptr<const P>, BV>;
 
template <class P, class BV>
using PrimAndBVList = std::vector<PrimAndBV<P, BV>>;
 
template <class P, class BV, size_t K>
using Partitioner = std::function<Array<PrimAndBVList<P, BV>, K>(PrimAndBVList<P, BV> a_primsAndBVs)>;
 
template <class T, class P, class BV, size_t K>
using LeafPredicate = std::function<bool(const TreeBVH<T, P, BV, K>& a_node)>;
 
template <class P>
using LeafEvaluator = std::function<void(const PrimitiveList<P>& a_primitives)>;
 
template <class NodeType, class NodeKey>
using PrunePredicate = std::function<bool(const NodeType& a_node, const NodeKey& a_nodeKey)>;
 
template <class NodeType, class NodeKey, size_t K>
using ChildOrderer = std::function<void(Array<std::pair<std::shared_ptr<const NodeType>, NodeKey>, K>& a_children)>;
 
template <class NodeType, class NodeKey>
using NodeKeyFactory = std::function<NodeKey(const NodeType& a_node)>;
 
template <class T, class P, size_t K>
class PackedBVH final : public PoolHandle
{
  static_assert(std::is_floating_point_v<T>, "PackedBVH: T must be a floating-point type");
  static_assert(K >= 2, "PackedBVH: branching factor K must be at least 2");
  static_assert(K <= 256, "PackedBVH: branching factor K must be at most 256, so a child slot fits in a byte");
  static_assert(!isPoolHandle<P>,
                "PackedBVH: a primitive stored in a pool must hold no location; store the handle's Layout "
                "and pair it with this BVH's location() (see PoolHandle)");
 
public:
  using BV = EBGeometry::BoundingVolumes::AABBT<T>;
 
  struct Node
  {
    uint32_t m_primOff{};
 
    uint32_t m_numPrims{};
 
    Array<uint32_t, K> m_childOff{};
 
    uint32_t m_childBoxRow{};
 
    uint32_t m_boxSlot{};
 
    EBGEOMETRY_HOST_DEVICE
    inline void
    setPrimitivesOffset(uint32_t a_off) noexcept
    {
      m_primOff = a_off;
    }
 
    EBGEOMETRY_HOST_DEVICE
    inline void
    setNumPrimitives(uint32_t a_n) noexcept
    {
      m_numPrims = a_n;
    }
 
    EBGEOMETRY_HOST_DEVICE
    inline void
    setChildOffset(uint32_t a_off, size_t a_k) noexcept
    {
      EBGEOMETRY_EXPECT(a_k < K);
      m_childOff[a_k] = a_off;
    }
 
    [[nodiscard]] EBGEOMETRY_HOST_DEVICE
    inline uint32_t
    getPrimitivesOffset() const noexcept
    {
      return m_primOff;
    }
 
    [[nodiscard]] EBGEOMETRY_HOST_DEVICE
    inline uint32_t
    getNumPrimitives() const noexcept
    {
      return m_numPrims;
    }
 
    [[nodiscard]] EBGEOMETRY_HOST_DEVICE
    inline const Array<uint32_t, K>&
    getChildOffsets() const noexcept
    {
      return m_childOff;
    }
 
    [[nodiscard]] EBGEOMETRY_HOST_DEVICE
    inline uint32_t
    getChildBoxRow() const noexcept
    {
      return m_childBoxRow;
    }
 
    [[nodiscard]] EBGEOMETRY_HOST_DEVICE
    inline uint32_t
    getBoxSlot() const noexcept
    {
      return m_boxSlot;
    }
 
    [[nodiscard]] EBGEOMETRY_HOST_DEVICE
    inline bool
    isLeaf() const noexcept
    {
      return m_numPrims > 0;
    }
  };
 
  static constexpr uint32_t RootBoxSlot = UINT32_MAX;
 
  PackedBVH() = delete;
 
  struct Layout;
 
  EBGEOMETRY_HOST_DEVICE
  inline PackedBVH(const Layout& a_layout, const PoolLocation& a_location) noexcept;
 
  [[nodiscard]] EBGEOMETRY_HOST_DEVICE
  inline Layout
  layout() const noexcept;
 
  EBGEOMETRY_HOST
  inline PackedBVH(Pool& a_pool, const TreeBVH<T, P, BV, K>& a_tree);
 
  template <class Q, class Converter>
  EBGEOMETRY_HOST
  inline PackedBVH(Pool& a_pool, const TreeBVH<T, Q, BV, K>& a_tree, Converter&& a_converter);
 
  [[nodiscard]] EBGEOMETRY_HOST
  static inline BVH::ConstructionOptions
  defaultConstructionOptions() noexcept
  {
    return BVH::ConstructionOptions{K - 1, K, BVH::ClusterSpec{}};
  }
 
  [[nodiscard]] EBGEOMETRY_HOST
  static inline PackedBVH
  build(Pool&                           a_pool,
        std::vector<std::pair<P, BV>>   a_primsAndBVs,
        BVH::Construction               a_construction,
        const BVH::ConstructionOptions& a_options = defaultConstructionOptions());
 
  template <class S = SFC::Morton>
  [[nodiscard]] EBGEOMETRY_HOST
  static inline PackedBVH
  buildBottomUp(Pool& a_pool, std::vector<std::pair<P, BV>> a_primsAndBVs, size_t a_targetLeafSize);
 
  [[nodiscard]] EBGEOMETRY_HOST
  static inline PackedBVH
  buildTopDown(Pool&                                  a_pool,
               std::vector<std::pair<P, BV>>          a_primsAndBVs,
               const BVH::Partitioner<P, BV, K>&      a_partitioner,
               const BVH::LeafPredicate<T, P, BV, K>& a_stopCrit);
 
  [[nodiscard]] EBGEOMETRY_HOST
  static inline PackedBVH
  buildTopDown(Pool&                             a_pool,
               std::vector<std::pair<P, BV>>     a_primsAndBVs,
               const BVH::Partitioner<P, BV, K>& a_partitioner);
 
  [[nodiscard]] EBGEOMETRY_HOST
  static inline PackedBVH
  buildClusterSAH(Pool& a_pool, std::vector<std::pair<P, BV>> a_primsAndBVs, BVH::ClusterSpec a_spec);
 
  EBGEOMETRY_HOST
  inline PackedBVH(Pool&                    a_pool,
                   const std::vector<Node>& a_linearNodes,
                   const std::vector<BV>&   a_nodeBoxes,
                   const std::vector<P>&    a_primitives)
  {
    this->finalize(a_pool, a_linearNodes, a_nodeBoxes, a_primitives);
  }
 
  inline ~PackedBVH() = default;
 
  PackedBVH(const PackedBVH& a_other) = default;
 
  PackedBVH&
  operator=(const PackedBVH& a_other) = default;
 
  PackedBVH(PackedBVH&& a_other) noexcept = default;
 
  PackedBVH&
  operator=(PackedBVH&& a_other) noexcept = default;
 
  [[nodiscard]] EBGEOMETRY_HOST_DEVICE
  inline PODSpan<const P>
  getPrimitives() const noexcept;
 
  [[nodiscard]] EBGEOMETRY_HOST_DEVICE
  inline PODSpan<P>
  getPrimitives() noexcept;
 
  [[nodiscard]] EBGEOMETRY_HOST_DEVICE
  inline PODSpan<const Node>
  getNodes() const noexcept;
 
  [[nodiscard]] EBGEOMETRY_HOST_DEVICE
  static constexpr size_t
  traversalStackDepth() noexcept
  {
#if defined(EBGEOMETRY_DEVICE_COMPILE)
    return PackedBVH::stackEntriesFor(DeviceTraversalDepth);
#else
    return PackedBVH::stackEntriesFor(HostTraversalDepth);
#endif
  }
 
  using PoolHandle::base;
 
  [[nodiscard]] EBGEOMETRY_HOST
  inline PackedBVH
  rebasedView(const Pool& a_pool) const noexcept;
 
  [[nodiscard]] EBGEOMETRY_HOST
  inline PackedBVH
  deepCopy(Pool& a_dstPool) const;
 
  [[nodiscard]] EBGEOMETRY_HOST_DEVICE
  inline const BV&
  getBoundingVolume() const noexcept;
 
  [[nodiscard]] EBGEOMETRY_HOST_DEVICE
  inline BV
  getBoundingVolume(const Node& a_node) const noexcept;
 
  [[nodiscard]] EBGEOMETRY_HOST_DEVICE
  inline T
  getDistanceToBoundingVolume2(const Node& a_node, const Vec3T<T>& a_point) const noexcept;
 
  [[nodiscard]] EBGEOMETRY_HOST_DEVICE
  inline T
  getDistanceToChildBoundingVolume2(const Node& a_parent, size_t a_k, const Vec3T<T>& a_point) const noexcept;
 
  [[nodiscard]] EBGEOMETRY_HOST_DEVICE
  inline BV
  computeBoundingVolume() const noexcept;
 
  template <class Query,
            class State,
            class LeafEvaluator,
            class BoundFn,
            class VisitFn = DescendAll,
            class Order   = NearestFirst>
  EBGEOMETRY_HOST_DEVICE
  inline void
  traverse(const Query&    a_query,
           State&          a_state,
           LeafEvaluator&& a_leaf,
           BoundFn&&       a_bound,
           VisitFn&&       a_visit = DescendAll(),
           Order           a_order = Order()) const noexcept;
 
  template <class BVConstructor>
  inline void
  refit(const BVConstructor& a_bvConstructor);
 
private:
  EBGEOMETRY_HOST
  inline void
  finalize(Pool&                    a_pool,
           const std::vector<Node>& a_linearNodes,
           const std::vector<BV>&   a_nodeBoxes,
           const std::vector<P>&    a_primitives);
 
  PODVector<Node> m_linearNodes;
 
  PODVector<P> m_primitives;
 
  using ChildAABBSoA = ChildBoxes<T, K>;
 
  PODVector<ChildAABBSoA> m_childAabbSoA;
 
  PODVector<BV> m_rootBox;
 
public:
  struct Layout
  {
    PODVector<Node> m_linearNodes;
 
    PODVector<P> m_primitives;
 
    PODVector<ChildAABBSoA> m_childAabbSoA;
 
    PODVector<BV> m_rootBox;
  };
 
private:
  struct StackEntry
  {
    uint32_t m_node;
 
    uint8_t m_slots[K - 1];
 
    uint8_t m_count;
  };
 
  static_assert(K != 4 || sizeof(StackEntry) == 8, "PackedBVH: a stack entry is 8 bytes at K = 4");
 
  [[nodiscard]] EBGEOMETRY_HOST_DEVICE
  static constexpr size_t
  stackEntriesFor(const size_t a_depth) noexcept
  {
    return a_depth - 1;
  }
 
  [[nodiscard]] EBGEOMETRY_HOST
  inline size_t
  maxNodeDepth(const void* a_base) const;
 
  EBGEOMETRY_HOST
  inline void
  requireDepthFits(const void* a_base, const size_t a_maxDepth, const char* a_context) const;
 
  EBGEOMETRY_HOST
  static inline void
  requireWellFormed(const std::vector<Node>& a_linearNodes, const size_t a_numPrimitives);
 
  EBGEOMETRY_HOST
  inline void
  buildSoA(Pool& a_pool, const std::vector<BV>& a_nodeBoxes);
 
  EBGEOMETRY_HOST_DEVICE
  static inline void
  setRowBox(ChildAABBSoA& a_soa, size_t a_slot, const BV& a_bv) noexcept;
 
  [[nodiscard]] EBGEOMETRY_HOST_DEVICE
  static inline BV
  rowBox(const ChildAABBSoA& a_soa, size_t a_slot) noexcept;
};
 
static_assert(std::is_trivially_copyable_v<PackedBVH<float, Vec3T<float>, 4>>,
              "PackedBVH<float, ...> must be trivially copyable");
static_assert(std::is_trivially_copyable_v<PackedBVH<double, Vec3T<double>, 4>>,
              "PackedBVH<double, ...> must be trivially copyable");
 
} // namespace BVH
 
} // namespace EBGeometry
 
#include "EBGeometry_PackedBVHImplem.hpp"
 
#endif