Octree.h

Go to the documentation of this file.

/*************************************************************************
> File Name: Octree.h
> Project Name: CubbyFlow
> Author: Chan-Ho Chris Ohk
> Purpose: Generic octree data structure.
> Created Time: 2017/10/15
> Copyright (c) 2018, Chan-Ho Chris Ohk
*************************************************************************/
#ifndef CUBBYFLOW_OCTREE_H
#define CUBBYFLOW_OCTREE_H

#include <Core/QueryEngine/IntersectionQueryEngine3.h>
#include <Core/QueryEngine/NearestNeighborQueryEngine3.h>

namespace CubbyFlow
{
    template <typename T>
    class Octree final : public IntersectionQueryEngine3<T>, public NearestNeighborQueryEngine3<T>
    {
    public:
        using ContainerType = std::vector<T>;
        using Iterator = typename ContainerType::iterator;
        using ConstIterator =  typename ContainerType::const_iterator;

        Octree();

        void Build(
            const std::vector<T>& items, const BoundingBox3D& bound,
            const BoxIntersectionTestFunc3<T>& testFunc, size_t maxDepth);

        void Clear();

        NearestNeighborQueryResult3<T> GetNearestNeighbor(
            const Vector3D& pt,
            const NearestNeighborDistanceFunc3<T>& distanceFunc) const override;

        bool IsIntersects(const BoundingBox3D& box,
            const BoxIntersectionTestFunc3<T>& testFunc) const override;

        bool IsIntersects(const Ray3D& ray,
            const RayIntersectionTestFunc3<T>& testFunc) const override;

        void ForEachIntersectingItem(
            const BoundingBox3D& box, const BoxIntersectionTestFunc3<T>& testFunc,
            const IntersectionVisitorFunc3<T>& visitorFunc) const override;

        void ForEachIntersectingItem(
            const Ray3D& ray, const RayIntersectionTestFunc3<T>& testFunc,
            const IntersectionVisitorFunc3<T>& visitorFunc) const override;

        ClosestIntersectionQueryResult3<T> GetClosestIntersection(
            const Ray3D& ray,
            const GetRayIntersectionFunc3<T>& testFunc) const override;

        Iterator begin();

        Iterator end();

        ConstIterator begin() const;

        ConstIterator end() const;

        size_t GetNumberOfItems() const;

        const T& GetItem(size_t i) const;

        size_t GetNumberOfNodes() const;

        const std::vector<size_t>& GetItemsAtNode(size_t nodeIdx) const;

        size_t GetChildIndex(size_t nodeIdx, size_t childIdx) const;

        const BoundingBox3D& GetBoundingBox() const;

        size_t GetMaxDepth() const;

    private:
        struct Node
        {
            size_t firstChild = std::numeric_limits<size_t>::max();
            std::vector<size_t> items;

            bool IsLeaf() const;
        };

        size_t m_maxDepth = 1;
        BoundingBox3D m_bbox;
        std::vector<T> m_items;
        std::vector<Node> m_nodes;

        void Build(size_t nodeIdx, size_t currentDepth,
            const BoundingBox3D& currentBound,
            const BoxIntersectionTestFunc3<T>& overlapsFunc);

        bool IsIntersects(const BoundingBox3D& box,
            const BoxIntersectionTestFunc3<T>& testFunc, size_t nodeIdx,
            const BoundingBox3D& currentBound) const;

        bool IsIntersects(const Ray3D& ray,
            const RayIntersectionTestFunc3<T>& testFunc, size_t nodeIdx,
            const BoundingBox3D& currentBound) const;

        void ForEachIntersectingItem(const BoundingBox3D& box,
            const BoxIntersectionTestFunc3<T>& testFunc,
            const IntersectionVisitorFunc3<T>& visitorFunc,
            size_t nodeIdx,
            const BoundingBox3D& currentBound) const;

        void ForEachIntersectingItem(const Ray3D& ray,
            const RayIntersectionTestFunc3<T>& testFunc,
            const IntersectionVisitorFunc3<T>& visitorFunc,
            size_t nodeIdx,
            const BoundingBox3D& currentBound) const;

        ClosestIntersectionQueryResult3<T> GetClosestIntersection(
            const Ray3D& ray, const GetRayIntersectionFunc3<T>& testFunc,
            size_t nodeIdx, const BoundingBox3D& currentBound,
            ClosestIntersectionQueryResult3<T> best) const;
    };
}

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

#endif