HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_RTree.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: UT_RTree.h (UT Library, C++)
7  *
8  * COMMENTS:
9  */
10 
11 #ifndef __UT_RTreeGeneric__
12 #define __UT_RTreeGeneric__
13 
14 #include "UT_API.h"
15 #include "UT_Array.h"
16 #include "UT_BoundingBox.h"
17 #include "UT_Vector3.h"
18 #include <SYS/SYS_Math.h>
19 #include <SYS/SYS_Types.h>
20 #include <vector>
21 #include <limits>
22 
23 // UT_BoxT represents either an axis-aligned box or the empty set.
24 // UT_BoxT is closed as a set; all operations assume that
25 // the boundary is included.
26 template< typename T >
27 class UT_BoxT
28 {
29 public:
30  typedef T Scalar;
31 
32  // Default construct: the empty set
33  UT_BoxT();
34 
35  // Construct box containing a single point position,
36  // which is represented by its array of three coordinates.
37  template< typename U >
38  explicit UT_BoxT(const U p[3]);
39  template< typename U >
40  explicit UT_BoxT(UT_Vector3T<U> p);
41 
42  explicit UT_BoxT(const UT_BoundingBox &bbox);
43 
44  // Return whether this represents the empty set
45  bool isEmpty() const;
46 
47  // Get minimum coordinate for given standard axis
48  // Assumes this is not empty!
49  T getMin(const int c) const;
50 
51  // Get maximum coordinate for given standard axis
52  // Assumes this is not empty!
53  T getMax(const int c) const;
54 
56  { return UT_Vector3T<T>(myMin[0], myMin[1], myMin[2]); }
58  { return UT_Vector3T<T>(myMax[0], myMax[1], myMax[2]); }
59 
61  {
62  return UT_Vector3T<T>((myMin[0]+myMax[0])/2,
63  (myMin[1]+myMax[1])/2,
64  (myMin[2]+myMax[2])/2);
65  }
67  {
68  return UT_Vector3T<T>((myMax[0]-myMin[0]),
69  (myMax[1]-myMin[1]),
70  (myMax[2]-myMin[2]));
71  }
72  T getRadius2() const
73  {
75 
76  size *= 0.5;
77  return size.length2();
78  }
79  T getRadius() const
80  {
81  return SYSsqrt(getRadius2());
82  }
83 
84  // Make a box that's a single point
85  template< typename U >
86  void assignPoint(const U p[3]);
87  template< typename U >
89 
90  // Expand the box just enough so that it contains a point p
91  template< typename U >
92  void absorbPoint(const U p[3]);
93  template< typename U >
95 
96  // Expand the box just enough so that it contains a box b
97  void absorbBox(const UT_BoxT<T>& b);
98  void absorbBox(const UT_BoundingBox &b);
99 
100  // Expand in the directions of the axes:
101  // In case this is the empty set, the result is still the empty set
102  // This is equivalent to making *this the union of all cubes with
103  // radius l placed at points of the original set.
104  void expandDistance(const T l);
105 
106  // As above but expand distance in a specific axis
107  void expandDistance(const T l, int axis);
108 
109  // Return whether a point is contained in the closed set
110  bool contains(const T*const p) const;
111 
112  // Return whether the closed set *this intersects the closed set b
113  bool intersects(const UT_BoxT<T>& b) const;
114 
115  // Return the axis in which the box is the widest.
116  // For the empty set, this always returns axis 0
117  int getLargestAxis() const;
118 
119 private:
120  // This represents set of all points x
121  // with myMin[c] <= x[c] <= myMax[c] for each c = 0, 1, 2
122  T myMin[3];
123  T myMax[3];
124 };
125 
126 // UT_VelBoxT represents an axis-aligned box in motion.
127 // UT_BoxT is closed as a set; all operations assume that
128 // the boundary is included.
129 template< typename T >
131 {
132 public:
133  typedef T Scalar;
134 
135  // Default construct: the empty set
136  UT_VelBoxT();
137 
138  // Constructs a stationary box of the given dimensions
139  explicit UT_VelBoxT(const UT_BoundingBox &bbox);
140 
141  // Constructs a moving box moving from one location to the other
143  const UT_BoundingBox &end);
144 
145  // Return whether this represents the empty set
146  bool isEmpty() const;
147 
148  // Get minimum coordinate for given standard axis
149  // Assumes this is not empty!
150  // Returns total size of start & end.
151  T getMin(const int c) const;
152 
153  // Get maximum coordinate for given standard axis
154  // Assumes this is not empty!
155  T getMax(const int c) const;
156 
157  // Get theh speed the box is moving in this coordinate.
158  T getVel(const int c) const;
159 
160  // Expand the box just enough so that it contains a box b
161  void absorbBox(const UT_VelBoxT<T>& b);
162 
163  // Return whether the closed set *this intersects the closed set b
164  bool intersects(const UT_VelBoxT<T>& b) const;
165 
166  // Return the axis in which the box is the widest.
167  // For the empty set, this always returns axis 0
168  int getLargestAxis() const;
169 
170 private:
171  // This represents set of all points x
172  // with myMin[c] <= x[c] <= myMax[c] for each c = 0, 1, 2
173  // Because we commonly perform isect tests, and those should early
174  // exit, we rotate the storage so
175  // x() - min
176  // y() - max
177  // z() - vel
178  UT_Vector3T<T> myBounds[3];
179 };
180 
181 
182 
183 // UT_Sphere represents a simple sphere or the empty set.
184 template< typename T >
186 {
187 public:
188  typedef T Scalar;
189 
190  // The constructor must take a centre point and a radius
191 
192  template< typename U >
193  explicit UT_SphereT(const U p[3], const U r)
194  : myRadius(r)
195  {
196  myCentre[0] = p[0];
197  myCentre[1] = p[1];
198  myCentre[2] = p[2];
199  };
200 
201  // Return whether the closed set *this intersects the closed set b
202  bool intersects(const UT_BoxT<T>& b) const;
203 
204 private:
205  T myCentre[3];
206  T myRadius;
207 };
208 
209 template< int MAX_ORDER >
211 
212 // This is an assigment of a box to each item stored in the R-tree.
213 // It is passed an argument to queries on the R-tree.
214 // This way, an R-tree can be re-used efficiently if the item boxes change.
215 // This will only remain efficient as long as the configuration of boxes
216 // doesn't change dramatically.
217 template< typename BOXTYPE>
219 {
220 public:
223 
225  {
226  // Do not include ourselves.
227  return myBoxesForSharedNodes.capacity() * sizeof(BOXTYPE);
228  }
229 
230 private:
231  typedef BOXTYPE Box;
232  std::vector<BOXTYPE> myBoxesForSharedNodes;
233 
234  template< int MAX_ORDER >
235  friend class UT_RTreeGeneric;
236 };
237 
238 
239 template< typename T >
241 
242 template< int MAX_ORDER >
243 class UT_RNode;
244 
245 // The order of the R-Tree is the number of children that each
246 // internal node in the tree has. Picking a higher value of
247 // MAX_ORDER will reduce the height of the R-tree.
248 // R-tree stores a containment structure for the boxes that are
249 // passed to its contructor, but doesn't store any actual boxes.
250 // That's why UT_RTreeGeneric doesn't take the number type T as a template parameter.
251 template< int MAX_ORDER >
252 class UT_RTreeGeneric
253 {
254 public:
255  // Construct R-tree that contains the range of items [0, size),
256  // During the construction, item_boxes[i] is used as the bounding box
257  // for item #i. These boxes determine the initial structure of the R-tree.
258  // However, the box positions and dimensions are not stored in the R-tree.
259  template< typename BOXTYPE >
260  UT_RTreeGeneric(const BOXTYPE item_boxes[], const int size);
261 
263 
264  // The number of items stored in the tree
265  int getNumItems() const;
266 
268  {
269  return sizeof(*this) + sizeof(Node) * mySharedNodesSize;
270  }
271 
272  // Create an assignment of a box to each item in the tree.
273  // That is, item i is assigned box item_boxes[i].
274  // This box assignment can be used in intersection queries.
275  template< typename T >
277  UT_RTreeBoxAssignmentT<T>& assignment,
278  const UT_BoxT<T> item_boxes[]
279  ) const
280  {
281  createAssignment<UT_BoxT<T> >(assignment, item_boxes);
282  }
283 
284  template< typename BOXTYPE>
285  void createAssignment(
286  UT_RTreeAssignmentT<BOXTYPE>& assignment,
287  const BOXTYPE item_boxes[]
288  ) const;
289 
290  /// For each item i for which item_boxes[i] intersects query_box,
291  /// call result_acceptor(i).
292  /// This assumes that RESULT_ACCEPTOR is a function or a functor.
293  /// A further generlaization of getIntersectingItems that takes
294  /// a queryshape. It is assumed to have an .intersects() method
295  /// which takes a UT_Box<T>
296  /// It is very important that the intersects() method will
297  /// return false for empty nodes.
298  template< typename QUERY_SHAPE, typename RESULT_ACCEPTOR, typename BOXTYPE >
300  RESULT_ACCEPTOR& result_acceptor,
301  const QUERY_SHAPE& query_box,
302  const UT_RTreeAssignmentT<BOXTYPE>& assignment
303  ) const;
304 
305  template< typename QUERY_SHAPE, typename RESULT_ACCEPTOR, typename BOXTYPE, int BATCH_SIZE >
307  RESULT_ACCEPTOR &batch_result_acceptor,
308  const QUERY_SHAPE *query_box,
309  const UT_RTreeAssignmentT<BOXTYPE>& assignment
310  ) const;
311 
312  template< typename BOXTYPE >
313  BOXTYPE boundingBox(const UT_RTreeAssignmentT<BOXTYPE>& assignment) const;
314 
315  /// Returns the number of nodes in the tree.
316  /// NOTE: This does not count the items themselves as nodes,
317  /// because they don't have nodes allocated for them.
318  int getNumNodes() const
319  { return mySharedNodesSize; }
320 
321  /// For each node, this effectively does:
322  /// LOCAL_DATA local_data[MAX_ORDER];
323  /// bool descend = pre_functor(nodei, parent_data);
324  /// if (!descend)
325  /// return;
326  /// for each child {
327  /// if (isitem(child))
328  /// item_functor(getitemi(child), nodei, local_data[child]);
329  /// else if (isnode(child))
330  /// recurse(getnodei(child), local_data);
331  /// }
332  /// post_functor(nodei, parent_nodei, data_for_parent, num_children, local_data);
333  template<typename LOCAL_DATA,typename PRE_FUNCTOR,typename ITEM_FUNCTOR,typename POST_FUNCTOR>
334  void traverse(
335  PRE_FUNCTOR &pre_functor,
336  ITEM_FUNCTOR &item_functor,
337  POST_FUNCTOR &post_functor,
338  LOCAL_DATA *data_for_parent=nullptr) const;
339 
340 private:
341  template<typename LOCAL_DATA,typename PRE_FUNCTOR,typename ITEM_FUNCTOR,typename POST_FUNCTOR>
342  void traverseHelper(
343  int nodei,
344  int parent_nodei,
345  PRE_FUNCTOR &pre_functor,
346  ITEM_FUNCTOR &item_functor,
347  POST_FUNCTOR &post_functor,
348  LOCAL_DATA *data_for_parent=nullptr) const;
349 
350 private:
351  typedef UT_RNode<MAX_ORDER> Node;
352 
353  int mySharedNodesSize;
354  Node* mySharedNodes;
355  Node* myRoot;
356  int myNumItems;
357 
358  // Disallow
359  UT_RTreeGeneric();
361  UT_RTreeGeneric& operator=(const UT_RTreeGeneric&);
362 };
363 
364 //
365 // Helpers for storing query results in containers
366 //
367 
368 // On return, "results" consists of all items i for which item_boxes[i]
369 // intersects query_box.
370 // The contents of "results" from before the call are cleared, so it
371 // is not neccessary to call results.clear() before calling this function.
372 template< typename QUERY_SHAPE, int MAX_ORDER, typename BOXTYPE >
373 inline void UTgetIntersectingItems(
374  UT_Array<int>& results,
375  const UT_RTreeGeneric<MAX_ORDER>& tree,
376  const QUERY_SHAPE& query_box,
377  const UT_RTreeAssignmentT<BOXTYPE>& assignment
378 );
379 
380 // Similar to UTgetIntersectingItems, but does not invoke clear()
381 // allowing you to join multiple searches together.
382 // The new items will all have baseindex added to them.
383 template< typename QUERY_SHAPE, int MAX_ORDER, typename BOXTYPE >
384 inline void UTappendIntersectingItems(
385  UT_Array<int>& results,
386  const UT_RTreeGeneric<MAX_ORDER>& tree,
387  const QUERY_SHAPE& query_box,
388  const UT_RTreeAssignmentT<BOXTYPE>& assignment,
389  exint baseindex
390 );
391 
392 // Does not clear the various isect lists. Will simultaneously
393 // walk the tree for all the batched values.
394 template< typename QUERY_SHAPE, int MAX_ORDER, typename BOXTYPE, int BATCHSIZE >
396  UT_Array<int> *results,
397  const UT_RTreeGeneric<MAX_ORDER>& tree,
398  const QUERY_SHAPE *query_box,
399  const UT_RTreeAssignmentT<BOXTYPE>& assignment
400 );
401 
402 
403 // Return all items i for which item_boxes[i] intersects query_box.
404 // The resulting items will be stored in the range [items_begin, items_end),
405 // where items_end is the return value.
406 // It is assumed that the array starting at items_begin is large enough
407 // to contain the results (at most the total number of items).
408 template< typename QUERY_SHAPE, int MAX_ORDER, typename BOXTYPE >
409 inline int* UTgetIntersectingItems(
410  const UT_RTreeGeneric<MAX_ORDER>& tree,
411  const QUERY_SHAPE& query_box,
412  const UT_RTreeAssignmentT<BOXTYPE>& assignment,
413  int*const items_begin
414 );
415 
416 #if defined( WIN32 ) || defined( LINUX ) || defined( MBSD ) || defined(GAMEOS)
417  #include "UT_RTree.C"
418 #endif
419 
420 // R-tree boxes for various float types
424 
425 // R-tree spheres for float types
429 
430 // R-tree box assignments for various float types
434 
435 // Tree of various orders
439 
440 #endif
441 
T getRadius() const
Definition: UT_RTree.h:79
UT_SphereT< fpreal64 > UT_SphereD
Definition: UT_RTree.h:427
void expandDistance(const T l)
Definition: UT_RTree.C:151
void absorbPoint(UT_Vector3T< U > p)
Definition: UT_RTree.h:94
UT_Vector3T< T > getCenter() const
Definition: UT_RTree.h:60
GLuint start
Definition: glcorearb.h:474
void assignPoint(const U p[3])
Definition: UT_RTree.C:98
bool isEmpty() const
Definition: UT_RTree.C:66
T getRadius2() const
Definition: UT_RTree.h:72
3D Vector class.
BOXTYPE boundingBox(const UT_RTreeAssignmentT< BOXTYPE > &assignment) const
Definition: UT_RTree.C:1365
bool intersects(const UT_BoxT< T > &b) const
Definition: UT_RTree.C:187
GLsizeiptr size
Definition: glcorearb.h:663
void getIntersectingItemsBatch(RESULT_ACCEPTOR &batch_result_acceptor, const QUERY_SHAPE *query_box, const UT_RTreeAssignmentT< BOXTYPE > &assignment) const
Definition: UT_RTree.C:1211
void UTappendIntersectingItemsBatch(UT_Array< int > *results, const UT_RTreeGeneric< MAX_ORDER > &tree, const QUERY_SHAPE *query_box, const UT_RTreeAssignmentT< BOXTYPE > &assignment)
Definition: UT_RTree.C:1294
int getLargestAxis() const
Definition: UT_RTree.C:388
T getVel(const int c) const
void absorbPoint(const U p[3])
Definition: UT_RTree.C:112
void UTappendIntersectingItems(UT_Array< int > &results, const UT_RTreeGeneric< MAX_ORDER > &tree, const QUERY_SHAPE &query_box, const UT_RTreeAssignmentT< BOXTYPE > &assignment, exint baseindex)
Definition: UT_RTree.C:1306
bool contains(const T *const p) const
Definition: UT_RTree.C:178
UT_BoxT()
Definition: UT_RTree.C:21
UT_SphereT< fpreal32 > UT_SphereF
Definition: UT_RTree.h:426
int64 exint
Definition: SYS_Types.h:116
UT_RTreeBoxAssignmentT< fpreal64 > UT_RTreeBoxAssignmentD
Definition: UT_RTree.h:432
GLuint GLuint end
Definition: glcorearb.h:474
void createBoxAssignment(UT_RTreeBoxAssignmentT< T > &assignment, const UT_BoxT< T > item_boxes[]) const
Definition: UT_RTree.h:276
void traverse(PRE_FUNCTOR &pre_functor, ITEM_FUNCTOR &item_functor, POST_FUNCTOR &post_functor, LOCAL_DATA *data_for_parent=nullptr) const
Definition: UT_RTree.C:1393
UT_BoxT< fpreal64 > UT_BoxD
Definition: UT_RTree.h:422
UT_SphereT(const U p[3], const U r)
Definition: UT_RTree.h:193
SYS_FORCE_INLINE UT_StorageAtLeast32Bit< T, T >::Type length2() const noexcept
UT_RTreeBoxAssignmentT< fpreal64 > UT_RTreeBoxAssignment
Definition: UT_RTree.h:433
UT_RTreeGeneric< 16 > UT_RTree16
Definition: UT_RTree.h:437
int getNumItems() const
Definition: UT_RTree.C:879
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
exint getMemoryUsage() const
Definition: UT_RTree.h:224
bool intersects(const UT_VelBoxT< T > &b) const
Definition: UT_RTree.C:371
int getNumNodes() const
Definition: UT_RTree.h:318
T Scalar
Definition: UT_RTree.h:30
exint getMemoryUsage() const
Definition: UT_RTree.h:267
UT_RTreeGeneric< 2 > UT_RTree2
Definition: UT_RTree.h:436
void getIntersectingItems(RESULT_ACCEPTOR &result_acceptor, const QUERY_SHAPE &query_box, const UT_RTreeAssignmentT< BOXTYPE > &assignment) const
Definition: UT_RTree.C:1191
T getMin(const int c) const
Definition: UT_RTree.C:332
void absorbBox(const UT_BoxT< T > &b)
Definition: UT_RTree.C:125
int getLargestAxis() const
Definition: UT_RTree.C:232
T getMax(const int c) const
Definition: UT_RTree.C:342
bool isEmpty() const
Definition: UT_RTree.C:321
UT_RTreeGeneric< 2 > UT_RTree
Definition: UT_RTree.h:438
void UTgetIntersectingItems(UT_Array< int > &results, const UT_RTreeGeneric< MAX_ORDER > &tree, const QUERY_SHAPE &query_box, const UT_RTreeAssignmentT< BOXTYPE > &assignment)
Definition: UT_RTree.C:1281
void assignPoint(UT_Vector3T< U > p)
Definition: UT_RTree.h:88
bool intersects(const UT_BoxT< T > &b) const
Definition: UT_RTree.C:430
Definition: ImathBox.h:72
UT_VelBoxT()
Definition: UT_RTree.C:272
void absorbBox(const UT_VelBoxT< T > &b)
Definition: UT_RTree.C:352
GLboolean r
Definition: glcorearb.h:1221
UT_Vector3T< T > getSize() const
Definition: UT_RTree.h:66
UT_BoxT< fpreal32 > UT_BoxF
Definition: UT_RTree.h:421
UT_SphereT< fpreal64 > UT_Sphere
Definition: UT_RTree.h:428
void createAssignment(UT_RTreeAssignmentT< BOXTYPE > &assignment, const BOXTYPE item_boxes[]) const
Definition: UT_RTree.C:1155
UT_RTreeBoxAssignmentT< fpreal32 > UT_RTreeBoxAssignmentF
Definition: UT_RTree.h:431
UT_Vector3T< T > getMin() const
Definition: UT_RTree.h:55
UT_Vector3T< T > getMax() const
Definition: UT_RTree.h:57
UT_BoxT< fpreal64 > UT_Box
Definition: UT_RTree.h:423