EBGeometry_PointCloudBVH.hpp

Go to the documentation of this file.

// SPDX-FileCopyrightText: 2026 Robert Marskar <robert.marskar@sintef.no>
//
// SPDX-License-Identifier: GPL-3.0-or-later
 
#ifndef EBGEOMETRY_POINTCLOUDBVH_HPP
#define EBGEOMETRY_POINTCLOUDBVH_HPP
 
// Std includes
#include <cstddef>
#include <cstdint>
#include <limits>
#include <vector>
 
// Our includes
#include "EBGeometry_BVH.hpp"
#include "EBGeometry_BoundingVolumes.hpp"
#include "EBGeometry_PointAoSoA.hpp"
#include "EBGeometry_PointSoA.hpp"
#include "EBGeometry_Vec.hpp"
 
namespace EBGeometry {
 
template <class T,
          class Meta = std::size_t,
          size_t K   = BVH::DefaultBranchingRatio<T>(),
          size_t W   = PointSoA::DefaultWidth<T>()>
class PointCloudBVH
  : public BVH::PackedBVH<T, PointAoSoA<T, std::size_t, W>, K, BVH::ValueStorage<PointAoSoA<T, std::size_t, W>>>
{
public:
  using PointGroup = PointAoSoA<T, std::size_t, W>;
 
  using Base = BVH::PackedBVH<T, PointGroup, K, BVH::ValueStorage<PointGroup>>;
 
  using Node = typename Base::Node;
 
  using AABB = BoundingVolumes::AABBT<T>;
 
  struct Hit
  {
    std::size_t index           = 0;                             
    T           distanceSquared = std::numeric_limits<T>::max(); 
  };
 
  PointCloudBVH() = delete;
 
  inline PointCloudBVH(const std::vector<Vec3T<T>>& a_positions,
                       const std::vector<Meta>&     a_metadata,
                       std::size_t                  a_targetLeafSize = 16 * W);
 
  [[nodiscard]] inline Hit
  closestPoint(const Vec3T<T>& a_query) const noexcept;
 
  inline std::size_t
  closestPoints(const Vec3T<T>& a_query, std::size_t a_k, Hit* a_out) const noexcept;
 
  [[nodiscard]] inline Hit
  nearestNeighbor(std::size_t a_point) const noexcept;
 
  inline std::size_t
  nearestNeighbors(std::size_t a_point, std::size_t a_k, Hit* a_out) const noexcept;
 
  [[nodiscard]] inline std::vector<Hit>
  allNearestNeighbors(std::size_t a_k = 1) const;
 
  [[nodiscard]] inline Hit
  closestPointBruteForce(const Vec3T<T>& a_query) const noexcept;
 
  inline std::size_t
  closestPointsBruteForce(const Vec3T<T>& a_query, std::size_t a_k, Hit* a_out) const;
 
  [[nodiscard]] inline Hit
  nearestNeighborBruteForce(std::size_t a_point) const noexcept;
 
  inline std::size_t
  nearestNeighborsBruteForce(std::size_t a_point, std::size_t a_k, Hit* a_out) const;
 
  [[nodiscard]] inline std::size_t
  numPoints() const noexcept
  {
    return m_positions.size();
  }
 
  [[nodiscard]] inline const Vec3T<T>&
  position(std::size_t a_index) const noexcept
  {
    return m_positions[a_index];
  }
 
  [[nodiscard]] inline const Meta&
  metadata(std::size_t a_index) const noexcept
  {
    return m_metadata[a_index];
  }
 
private:
  struct BuildResult
  {
    std::vector<Node>          nodes;      
    std::vector<PointGroup>    primitives; 
    std::vector<std::uint32_t> leafOff;    
    std::vector<std::uint32_t> leafCnt;    
    std::vector<std::uint32_t> order;      
  };
 
  inline PointCloudBVH(BuildResult&&                a_build,
                       const std::vector<Vec3T<T>>& a_positions,
                       const std::vector<Meta>&     a_metadata);
 
  static inline BuildResult
  buildTree(const std::vector<Vec3T<T>>& a_positions, std::size_t a_leafSize);
 
  inline void
  query(const Vec3T<T>& a_query,
        std::size_t     a_k,
        Hit*            a_out,
        std::size_t&    a_found,
        std::size_t     a_exclude,
        std::uint32_t   a_seedOff,
        std::uint32_t   a_seedCnt) const noexcept;
 
  [[nodiscard]] inline Hit
  bruteForceOne(const Vec3T<T>& a_query, std::size_t a_exclude) const noexcept;
 
  inline std::size_t
  bruteForceK(const Vec3T<T>& a_query, std::size_t a_k, Hit* a_out, std::size_t a_exclude) const;
 
  static constexpr std::size_t s_none = std::numeric_limits<std::size_t>::max();
 
  std::vector<Vec3T<T>> m_positions;
 
  std::vector<Meta> m_metadata;
 
  std::vector<std::uint32_t> m_leafOff;
 
  std::vector<std::uint32_t> m_leafCnt;
 
  std::vector<std::uint32_t> m_order;
};
 
} // namespace EBGeometry
 
#include "EBGeometry_PointCloudBVHImplem.hpp"
 
#endif