bvh3.h

Go to the documentation of this file.

// Copyright (c) 2019 Doyub Kim
//
// I am making my contributions/submissions to this project solely in my
// personal capacity and am not conveying any rights to any intellectual
// property of any third parties.
 
#ifndef INCLUDE_JET_BVH3_H_
#define INCLUDE_JET_BVH3_H_
 
#include <jet/intersection_query_engine3.h>
#include <jet/nearest_neighbor_query_engine3.h>
 
#include <vector>
 
namespace jet {
 
template <typename T>
class Bvh3 final : public IntersectionQueryEngine3<T>,
                   public NearestNeighborQueryEngine3<T> {
 public:
    using ContainerType = std::vector<T>;
    using Iterator = typename ContainerType::iterator;
    using ConstIterator = typename ContainerType::const_iterator;
 
    Bvh3();
 
    void build(const std::vector<T>& items,
               const std::vector<BoundingBox3D>& itemsBounds);
 
    void clear();
 
    NearestNeighborQueryResult3<T> nearest(
        const Vector3D& pt,
        const NearestNeighborDistanceFunc3<T>& distanceFunc) const override;
 
    bool intersects(const BoundingBox3D& box,
                    const BoxIntersectionTestFunc3<T>& testFunc) const override;
 
    bool intersects(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> closestIntersection(
        const Ray3D& ray,
        const GetRayIntersectionFunc3<T>& testFunc) const override;
 
    const BoundingBox3D& boundingBox() const;
 
    Iterator begin();
 
    Iterator end();
 
    ConstIterator begin() const;
 
    ConstIterator end() const;
 
    size_t numberOfItems() const;
 
    const T& item(size_t i) const;
 
    size_t numberOfNodes() const;
 
    std::pair<size_t, size_t> children(size_t i) const;
 
    bool isLeaf(size_t i) const;
 
    const BoundingBox3D& nodeBound(size_t i) const;
 
    Iterator itemOfNode(size_t i);
 
    ConstIterator itemOfNode(size_t i) const;
 
 private:
    struct Node {
        char flags;
        union {
            size_t child;
            size_t item;
        };
        BoundingBox3D bound;
 
        Node();
        void initLeaf(size_t it, const BoundingBox3D& b);
        void initInternal(uint8_t axis, size_t c, const BoundingBox3D& b);
        bool isLeaf() const;
    };
 
    BoundingBox3D _bound;
    ContainerType _items;
    std::vector<BoundingBox3D> _itemBounds;
    std::vector<Node> _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);
};
}  // namespace jet
 
#include "detail/bvh3-inl.h"
 
#endif  // INCLUDE_JET_BVH3_H_