Jet  v1.3.3
octree.h
Go to the documentation of this file.
1 // Copyright (c) 2018 Doyub Kim
2 //
3 // I am making my contributions/submissions to this project solely in my
4 // personal capacity and am not conveying any rights to any intellectual
5 // property of any third parties.
6 
7 #ifndef INCLUDE_JET_OCTREE_H_
8 #define INCLUDE_JET_OCTREE_H_
9 
12 #include <vector>
13 
14 namespace jet {
15 
25 template <typename T>
26 class Octree final : public IntersectionQueryEngine3<T>,
27  public NearestNeighborQueryEngine3<T> {
28  public:
29  typedef std::vector<T> ContainerType;
30  typedef typename ContainerType::iterator Iterator;
31  typedef typename ContainerType::const_iterator ConstIterator;
32 
34  Octree();
35 
38  void build(const std::vector<T>& items, const BoundingBox3D& bound,
39  const BoxIntersectionTestFunc3<T>& testFunc, size_t maxDepth);
40 
42  void clear();
43 
47  const Vector3D& pt,
48  const NearestNeighborDistanceFunc3<T>& distanceFunc) const override;
49 
51  bool intersects(const BoundingBox3D& box,
52  const BoxIntersectionTestFunc3<T>& testFunc) const override;
53 
55  bool intersects(const Ray3D& ray,
56  const RayIntersectionTestFunc3<T>& testFunc) const override;
57 
60  const BoundingBox3D& box, const BoxIntersectionTestFunc3<T>& testFunc,
61  const IntersectionVisitorFunc3<T>& visitorFunc) const override;
62 
65  const Ray3D& ray, const RayIntersectionTestFunc3<T>& testFunc,
66  const IntersectionVisitorFunc3<T>& visitorFunc) const override;
67 
70  const Ray3D& ray,
71  const GetRayIntersectionFunc3<T>& testFunc) const override;
72 
75 
78 
81 
83  ConstIterator end() const;
84 
86  size_t numberOfItems() const;
87 
89  const T& item(size_t i) const;
90 
92  size_t numberOfNodes() const;
93 
95  const std::vector<size_t>& itemsAtNode(size_t nodeIdx) const;
96 
109  size_t childIndex(size_t nodeIdx, size_t childIdx) const;
110 
112  const BoundingBox3D& boundingBox() const;
113 
115  size_t maxDepth() const;
116 
117  private:
118  struct Node {
119  size_t firstChild = kMaxSize;
120  std::vector<size_t> items;
121 
122  bool isLeaf() const;
123  };
124 
125  size_t _maxDepth = 1;
126  BoundingBox3D _bbox;
127  std::vector<T> _items;
128  std::vector<Node> _nodes;
129 
130  void build(size_t nodeIdx, size_t currentDepth,
131  const BoundingBox3D& currentBound,
132  const BoxIntersectionTestFunc3<T>& overlapsFunc);
133 
134  bool intersects(const BoundingBox3D& box,
135  const BoxIntersectionTestFunc3<T>& testFunc, size_t nodeIdx,
136  const BoundingBox3D& currentBound) const;
137 
138  bool intersects(const Ray3D& ray,
139  const RayIntersectionTestFunc3<T>& testFunc, size_t nodeIdx,
140  const BoundingBox3D& currentBound) const;
141 
142  void forEachIntersectingItem(const BoundingBox3D& box,
143  const BoxIntersectionTestFunc3<T>& testFunc,
144  const IntersectionVisitorFunc3<T>& visitorFunc,
145  size_t nodeIdx,
146  const BoundingBox3D& currentBound) const;
147 
148  void forEachIntersectingItem(const Ray3D& ray,
149  const RayIntersectionTestFunc3<T>& testFunc,
150  const IntersectionVisitorFunc3<T>& visitorFunc,
151  size_t nodeIdx,
152  const BoundingBox3D& currentBound) const;
153 
155  const Ray3D& ray, const GetRayIntersectionFunc3<T>& testFunc,
156  size_t nodeIdx, const BoundingBox3D& currentBound,
158 };
159 
160 } // namespace jet
161 
162 #include "detail/octree-inl.h"
163 
164 #endif // INCLUDE_JET_OCTREE_H_
jet::Octree::begin
ConstIterator begin() const
Returns the immutable begin iterator of the item.
jet::GetRayIntersectionFunc3
std::function< double(const T &, const Ray3D &)> GetRayIntersectionFunc3
Ray-item closest intersection evaluation function.
Definition: intersection_query_engine3.h:40
jet::Octree::intersects
bool intersects(const BoundingBox3D &box, const BoxIntersectionTestFunc3< T > &testFunc) const override
Returns true if given box intersects with any of the stored items.
jet::BoxIntersectionTestFunc3
std::function< bool(const T &, const BoundingBox3D &)> BoxIntersectionTestFunc3
Box-item intersection test function.
Definition: intersection_query_engine3.h:32
jet::IntersectionVisitorFunc3
std::function< void(const T &)> IntersectionVisitorFunc3
Visitor function which is invoked for each intersecting item.
Definition: intersection_query_engine3.h:44
jet::Octree::Octree
Octree()
Default constructor.
jet::Octree::intersects
bool intersects(const Ray3D &ray, const RayIntersectionTestFunc3< T > &testFunc) const override
Returns true if given ray intersects with any of the stored items.
jet::Octree::item
const T & item(size_t i) const
Returns the item at i.
jet::Octree::childIndex
size_t childIndex(size_t nodeIdx, size_t childIdx) const
Returns a child's index for given node.
jet::BoundingBox< T, 3 >
3-D axis-aligned bounding box class.
Definition: bounding_box3.h:41
intersection_query_engine3.h
jet::NearestNeighborQueryResult3
Nearest neighbor query result.
Definition: nearest_neighbor_query_engine3.h:19
jet::kMaxSize
constexpr size_t kMaxSize
Max size_t.
Definition: constants.h:79
jet::Octree::nearest
NearestNeighborQueryResult3< T > nearest(const Vector3D &pt, const NearestNeighborDistanceFunc3< T > &distanceFunc) const override
jet
Definition: advection_solver2.h:18
jet::Octree::numberOfNodes
size_t numberOfNodes() const
Returns the number of octree nodes.
jet::Octree::end
ConstIterator end() const
Returns the immutable end iterator of the item.
jet::Octree::ContainerType
std::vector< T > ContainerType
Definition: octree.h:29
jet::RayIntersectionTestFunc3
std::function< bool(const T &, const Ray3D &)> RayIntersectionTestFunc3
Ray-item intersection test function.
Definition: intersection_query_engine3.h:36
jet::Octree::ConstIterator
ContainerType::const_iterator ConstIterator
Definition: octree.h:31
jet::Octree::itemsAtNode
const std::vector< size_t > & itemsAtNode(size_t nodeIdx) const
Returns the list of the items for given noide index.
nearest_neighbor_query_engine3.h
jet::Octree::clear
void clear()
Clears all the contents of this instance.
jet::Ray< T, 3 >
Class for 2-D ray.
Definition: ray3.h:21
jet::Octree::closestIntersection
ClosestIntersectionQueryResult3< T > closestIntersection(const Ray3D &ray, const GetRayIntersectionFunc3< T > &testFunc) const override
Returns the closest intersection for given ray.
jet::Octree::maxDepth
size_t maxDepth() const
Returns the maximum depth of the tree.
jet::Octree::boundingBox
const BoundingBox3D & boundingBox() const
Returns the bounding box of this octree.
jet::Octree::begin
Iterator begin()
Returns the begin iterator of the item.
jet::Octree::end
Iterator end()
Returns the end iterator of the item.
jet::Octree::forEachIntersectingItem
void forEachIntersectingItem(const BoundingBox3D &box, const BoxIntersectionTestFunc3< T > &testFunc, const IntersectionVisitorFunc3< T > &visitorFunc) const override
Invokes visitorFunc for every intersecting items.
jet::Octree::build
void build(const std::vector< T > &items, const BoundingBox3D &bound, const BoxIntersectionTestFunc3< T > &testFunc, size_t maxDepth)
jet::Vector< T, 3 >
3-D vector class.
Definition: vector3.h:25
jet::Octree::Iterator
ContainerType::iterator Iterator
Definition: octree.h:30
jet::Octree
Generic octree data structure.
Definition: octree.h:27
jet::NearestNeighborDistanceFunc3
std::function< double(const T &, const Vector3D &)> NearestNeighborDistanceFunc3
Nearest neighbor distance measure function.
Definition: nearest_neighbor_query_engine3.h:27
jet::IntersectionQueryEngine3
Abstract base class for 3-D intersection test query engine.
Definition: intersection_query_engine3.h:48
jet::NearestNeighborQueryEngine3
Abstract base class for 3-D nearest neigbor query engine.
Definition: nearest_neighbor_query_engine3.h:31
jet::Octree::numberOfItems
size_t numberOfItems() const
Returns the number of items.
jet::ClosestIntersectionQueryResult3
Closest intersection query result.
Definition: intersection_query_engine3.h:19
jet::Octree::forEachIntersectingItem
void forEachIntersectingItem(const Ray3D &ray, const RayIntersectionTestFunc3< T > &testFunc, const IntersectionVisitorFunc3< T > &visitorFunc) const override
Invokes visitorFunc for every intersecting items.