BVH2.h

Go to the documentation of this file.

/*************************************************************************
> File Name: BVH2.h
> Project Name: CubbyFlow
> Author: Chan-Ho Chris Ohk
> Purpose: Bounding Volume Hierarchy (BVH) in 2D.
> Created Time: 2017/10/17
> Copyright (c) 2018, Chan-Ho Chris Ohk
*************************************************************************/
#ifndef CUBBYFLOW_BVH2_H
#define CUBBYFLOW_BVH2_H

#include <Core/QueryEngine/IntersectionQueryEngine2.h>
#include <Core/QueryEngine/NearestNeighborQueryEngine2.h>

namespace CubbyFlow
{
    template <typename T>
    class BVH2 final : public IntersectionQueryEngine2<T>, public NearestNeighborQueryEngine2<T>
    {
    public:
        using ContainerType = std::vector<T>;
        using Iterator = typename ContainerType::iterator;
        using ConstIterator = typename ContainerType::const_iterator;

        BVH2();

        void Build(const std::vector<T>& items,
            const std::vector<BoundingBox2D>& itemsBounds);

        void Clear();

        NearestNeighborQueryResult2<T> GetNearestNeighbor(
            const Vector2D& pt,
            const NearestNeighborDistanceFunc2<T>& distanceFunc) const override;

        bool IsIntersects(const BoundingBox2D& box,
            const BoxIntersectionTestFunc2<T>& testFunc) const override;

        bool IsIntersects(const Ray2D& ray,
            const RayIntersectionTestFunc2<T>& testFunc) const override;

        void ForEachIntersectingItem(
            const BoundingBox2D& box, const BoxIntersectionTestFunc2<T>& testFunc,
            const IntersectionVisitorFunc2<T>& visitorFunc) const override;

        void ForEachIntersectingItem(
            const Ray2D& ray, const RayIntersectionTestFunc2<T>& testFunc,
            const IntersectionVisitorFunc2<T>& visitorFunc) const override;

        ClosestIntersectionQueryResult2<T> GetClosestIntersection(
            const Ray2D& ray,
            const GetRayIntersectionFunc2<T>& testFunc) const override;

        const BoundingBox2D& GetBoundingBox() const;

        Iterator begin();

        Iterator end();

        ConstIterator begin() const;

        ConstIterator end() const;

        size_t GetNumberOfItems() const;

        const T& GetItem(size_t i) const;

    private:
        struct Node
        {
            char flags;
            union
            {
                size_t child;
                size_t item;
            };
            BoundingBox2D bound;

            Node();
            void InitLeaf(size_t it, const BoundingBox2D& b);
            void InitInternal(uint8_t axis, size_t c, const BoundingBox2D& b);
            bool IsLeaf() const;
        };

        BoundingBox2D m_bound;
        ContainerType m_items;
        std::vector<BoundingBox2D> m_itemBounds;
        std::vector<Node> m_nodes;

        size_t Build(size_t nodeIndex, size_t* itemIndices, size_t nItems, size_t currentDepth);

        size_t QSplit(size_t* itemIndices, size_t numItems, double pivot, uint8_t axis);
    };
}

#include <Core/Geometry/BVH2-Impl.h>

#endif