Quadtree.hpp

Go to the documentation of this file.

// This code is based on Jet framework.
// Copyright (c) 2018 Doyub Kim
// CubbyFlow is voxel-based fluid simulation engine for computer games.
// Copyright (c) 2020 CubbyFlow Team
// Core Part: Chris Ohk, Junwoo Hwang, Jihong Sin, Seungwoo Yoo
// AI Part: Dongheon Cho, Minseo Kim
// We are making my contributions/submissions to this project solely in our
// personal capacity and are not conveying any rights to any intellectual
// property of any third parties.
 
#ifndef CUBBYFLOW_QUADTREE_HPP
#define CUBBYFLOW_QUADTREE_HPP
 
#include <Core/QueryEngine/IntersectionQueryEngine.hpp>
#include <Core/QueryEngine/NearestNeighborQueryEngine.hpp>
 
namespace CubbyFlow
{
template <typename T>
class Quadtree final : public IntersectionQueryEngine2<T>,
                       public NearestNeighborQueryEngine2<T>
{
 public:
    using ContainerType = std::vector<T>;
    using Iterator = typename ContainerType::iterator;
    using ConstIterator = typename ContainerType::const_iterator;
 
    Quadtree() = default;
 
    Quadtree(const Quadtree&) = default;
 
    Quadtree(Quadtree&&) noexcept = default;
 
    virtual ~Quadtree() = default;
 
    Quadtree& operator=(const Quadtree&) = default;
 
    Quadtree& operator=(Quadtree&&) noexcept = default;
 
    void Build(const std::vector<T>& items, const BoundingBox2D& bound,
               const BoxIntersectionTestFunc2<T>& testFunc, size_t maxDepth);
 
    void Clear();
 
    [[nodiscard]] NearestNeighborQueryResult2<T> Nearest(
        const Vector2D& pt,
        const NearestNeighborDistanceFunc2<T>& distanceFunc) const override;
 
    [[nodiscard]] bool Intersects(
        const BoundingBox2D& box,
        const BoxIntersectionTestFunc2<T>& testFunc) const override;
 
    [[nodiscard]] bool Intersects(
        const Ray2D& ray,
        const RayIntersectionTestFunc2<T>& testFunc) const override;
 
    void ForEachIntersectingItem(
        const BoundingBox2D& box, const BoxIntersectionTestFunc2<T>& testFunc,
        const IntersectionVisitorFunc<T>& visitorFunc) const override;
 
    void ForEachIntersectingItem(
        const Ray2D& ray, const RayIntersectionTestFunc2<T>& testFunc,
        const IntersectionVisitorFunc<T>& visitorFunc) const override;
 
    [[nodiscard]] ClosestIntersectionQueryResult2<T> ClosestIntersection(
        const Ray2D& ray,
        const GetRayIntersectionFunc2<T>& testFunc) const override;
 
    [[nodiscard]] Iterator begin();
 
    [[nodiscard]] Iterator end();
 
    [[nodiscard]] ConstIterator begin() const;
 
    [[nodiscard]] ConstIterator end() const;
 
    [[nodiscard]] size_t GetNumberOfItems() const;
 
    [[nodiscard]] const T& GetItem(size_t i) const;
 
    [[nodiscard]] size_t GetNumberOfNodes() const;
 
    [[nodiscard]] const std::vector<size_t>& GetItemsAtNode(
        size_t nodeIdx) const;
 
    [[nodiscard]] size_t GetChildIndex(size_t nodeIdx, size_t childIdx) const;
 
    [[nodiscard]] const BoundingBox2D& GetBoundingBox() const;
 
    [[nodiscard]] size_t GetMaxDepth() const;
 
 private:
    struct Node
    {
        [[nodiscard]] bool IsLeaf() const;
 
        size_t firstChild = std::numeric_limits<size_t>::max();
        std::vector<size_t> items;
    };
 
    void Build(size_t nodeIdx, size_t Depth, const BoundingBox2D& Bound,
               const BoxIntersectionTestFunc2<T>& testFunc);
 
    [[nodiscard]] bool Intersects(const BoundingBox2D& box,
                                  const BoxIntersectionTestFunc2<T>& testFunc,
                                  size_t nodeIdx,
                                  const BoundingBox2D& Bound) const;
 
    [[nodiscard]] bool Intersects(const Ray2D& ray,
                                  const RayIntersectionTestFunc2<T>& testFunc,
                                  size_t nodeIdx,
                                  const BoundingBox2D& Bound) const;
 
    void ForEachIntersectingItem(const BoundingBox2D& box,
                                 const BoxIntersectionTestFunc2<T>& testFunc,
                                 const IntersectionVisitorFunc<T>& visitorFunc,
                                 size_t nodeIdx,
                                 const BoundingBox2D& Bound) const;
 
    void ForEachIntersectingItem(const Ray2D& ray,
                                 const RayIntersectionTestFunc2<T>& testFunc,
                                 const IntersectionVisitorFunc<T>& visitorFunc,
                                 size_t nodeIdx,
                                 const BoundingBox2D& Bound) const;
 
    [[nodiscard]] ClosestIntersectionQueryResult2<T> ClosestIntersection(
        const Ray2D& ray, const GetRayIntersectionFunc2<T>& testFunc,
        size_t nodeIdx, const BoundingBox2D& Bound,
        ClosestIntersectionQueryResult2<T> best) const;
 
    size_t m_maxDepth = 1;
    BoundingBox2D m_bbox;
    std::vector<T> m_items;
    std::vector<Node> m_nodes;
};
}  // namespace CubbyFlow
 
#include <Core/Geometry/Quadtree-Impl.hpp>
 
#endif