HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros 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_IntArray.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  {
57  return UT_Vector3T<T>((myMin[0]+myMax[0])/2,
58  (myMin[1]+myMax[1])/2,
59  (myMin[2]+myMax[2])/2);
60  }
62  {
63  return UT_Vector3T<T>((myMax[0]-myMin[0]),
64  (myMax[1]-myMin[1]),
65  (myMax[2]-myMin[2]));
66  }
67  T getRadius2() const
68  {
70 
71  size *= 0.5;
72  return size.length2();
73  }
74  T getRadius() const
75  {
76  return SYSsqrt(getRadius2());
77  }
78 
79  // Make a box that's a single point
80  template< typename U >
81  void assignPoint(const U p[3]);
82  template< typename U >
84 
85  // Expand the box just enough so that it contains a point p
86  template< typename U >
87  void absorbPoint(const U p[3]);
88  template< typename U >
90 
91  // Expand the box just enough so that it contains a box b
92  void absorbBox(const UT_BoxT<T>& b);
93  void absorbBox(const UT_BoundingBox &b);
94 
95  // Expand in the directions of the axes:
96  // In case this is the empty set, the result is still the empty set
97  // This is equivalent to making *this the union of all cubes with
98  // radius l placed at points of the original set.
99  void expandDistance(const T l);
100 
101  // As above but expand distance in a specific axis
102  void expandDistance(const T l, int axis);
103 
104  // Return whether a point is contained in the closed set
105  bool contains(const T*const p) const;
106 
107  // Return whether the closed set *this intersects the closed set b
108  bool intersects(const UT_BoxT<T>& b) const;
109 
110  // Return the axis in which the box is the widest.
111  // For the empty set, this always returns axis 0
112  int getLargestAxis() const;
113 
114 private:
115  // This represents set of all points x
116  // with myMin[c] <= x[c] <= myMax[c] for each c = 0, 1, 2
117  T myMin[3];
118  T myMax[3];
119 };
120 
121 
122 // UT_Sphere represents a simple sphere or the empty set.
123 template< typename T >
125 {
126 public:
127  typedef T Scalar;
128 
129  // The constructor must take a centre point and a radius
130 
131  template< typename U >
132  explicit UT_SphereT(const U p[3], const U r)
133  : myRadius(r)
134  {
135  myCentre[0] = p[0];
136  myCentre[1] = p[1];
137  myCentre[2] = p[2];
138  };
139 
140  // Return whether the closed set *this intersects the closed set b
141  bool intersects(const UT_BoxT<T>& b) const;
142 
143 private:
144  T myCentre[3];
145  T myRadius;
146 };
147 
148 template< int MAX_ORDER >
150 
151 // This is an assigment of a box to each item stored in the R-tree.
152 // It is passed an argument to queries on the R-tree.
153 // This way, an R-tree can be re-used efficiently if the item boxes change.
154 // This will only remain efficient as long as the configuration of boxes
155 // doesn't change dramatically.
156 template< typename T >
158 {
159 public:
162 
164  {
165  // Do not include ourselves.
166  return myBoxesForSharedNodes.capacity() * sizeof(UT_BoxT<T>);
167  }
168 
169 private:
170  typedef UT_BoxT<T> Box;
171  std::vector<Box> myBoxesForSharedNodes;
172 
173  template< int MAX_ORDER >
174  friend class UT_RTreeGeneric;
175 };
176 
177 template< int MAX_ORDER >
178 class UT_RNode;
179 
180 // The order of the R-Tree is the number of children that each
181 // internal node in the tree has. Picking a higher value of
182 // MAX_ORDER will reduce the height of the R-tree.
183 // R-tree stores a containment structure for the boxes that are
184 // passed to its contructor, but doesn't store any actual boxes.
185 // That's why UT_RTreeGeneric doesn't take the number type T as a template parameter.
186 template< int MAX_ORDER >
187 class UT_RTreeGeneric
188 {
189 public:
190  // Construct R-tree that contains the range of items [0, size),
191  // During the construction, item_boxes[i] is used as the bounding box
192  // for item #i. These boxes determine the initial structure of the R-tree.
193  // However, the box positions and dimensions are not stored in the R-tree.
194  template< typename T >
195  UT_RTreeGeneric(const UT_BoxT<T> item_boxes[], const int size);
196 
198 
199  // The number of items stored in the tree
200  int getNumItems() const;
201 
203  {
204  return sizeof(*this) + sizeof(Node) * mySharedNodesSize;
205  }
206 
207  // Create an assignment of a box to each item in the tree.
208  // That is, item i is assigned box item_boxes[i].
209  // This box assignment can be used in intersection queries.
210  template< typename T >
211  void createBoxAssignment(
212  UT_RTreeBoxAssignmentT<T>& assignment,
213  const UT_BoxT<T> item_boxes[]
214  ) const;
215 
216  /// For each item i for which item_boxes[i] intersects query_box,
217  /// call result_acceptor(i).
218  /// This assumes that RESULT_ACCEPTOR is a function or a functor.
219  /// A further generlaization of getIntersectingItems that takes
220  /// a queryshape. It is assumed to have an .intersects() method
221  /// which takes a UT_Box<T>
222  /// It is very important that the intersects() method will
223  /// return false for empty nodes.
224  template< typename QUERY_SHAPE, typename RESULT_ACCEPTOR, typename T >
226  RESULT_ACCEPTOR& result_acceptor,
227  const QUERY_SHAPE& query_box,
228  const UT_RTreeBoxAssignmentT<T>& assignment
229  ) const;
230 
231  template< typename T >
232  UT_BoxT<T> boundingBox(const UT_RTreeBoxAssignmentT<T>& assignment) const;
233 
234 private:
235  typedef UT_RNode<MAX_ORDER> Node;
236 
237  int mySharedNodesSize;
238  Node* mySharedNodes;
239  Node* myRoot;
240  int myNumItems;
241 
242  // Disallow
243  UT_RTreeGeneric();
245  UT_RTreeGeneric& operator=(const UT_RTreeGeneric&);
246 };
247 
248 //
249 // Helpers for storing query results in containers
250 //
251 
252 // On return, "results" consists of all items i for which item_boxes[i]
253 // intersects query_box.
254 // The contents of "results" from before the call are cleared, so it
255 // is not neccessary to call results.clear() before calling this function.
256 template< typename QUERY_SHAPE, int MAX_ORDER, typename T >
257 inline void UTgetIntersectingItems(
258  UT_IntArray& results,
259  const UT_RTreeGeneric<MAX_ORDER>& tree,
260  const QUERY_SHAPE& query_box,
261  const UT_RTreeBoxAssignmentT<T>& assignment
262 );
263 
264 // Similar to UTgetIntersectingItems, but does not invoke clear()
265 // allowing you to join multiple searches together.
266 // The new items will all have baseindex added to them.
267 template< typename QUERY_SHAPE, int MAX_ORDER, typename T >
268 inline void UTappendIntersectingItems(
269  UT_IntArray& results,
270  const UT_RTreeGeneric<MAX_ORDER>& tree,
271  const QUERY_SHAPE& query_box,
272  const UT_RTreeBoxAssignmentT<T>& assignment,
273  exint baseindex
274 );
275 
276 // Return all items i for which item_boxes[i] intersects query_box.
277 // The resulting items will be stored in the range [items_begin, items_end),
278 // where items_end is the return value.
279 // It is assumed that the array starting at items_begin is large enough
280 // to contain the results (at most the total number of items).
281 template< typename QUERY_SHAPE, int MAX_ORDER, typename T >
282 inline int* UTgetIntersectingItems(
283  const UT_RTreeGeneric<MAX_ORDER>& tree,
284  const QUERY_SHAPE& query_box,
285  const UT_RTreeBoxAssignmentT<T>& assignment,
286  int*const items_begin
287 );
288 
289 #if defined( WIN32 ) || defined( LINUX ) || defined( MBSD ) || defined(GAMEOS)
290  #include "UT_RTree.C"
291 #endif
292 
293 // R-tree boxes for various float types
297 
298 // R-tree spheres for float types
302 
303 // R-tree box assignments for various float types
307 
308 // Tree of various orders
312 
313 #endif
314 
T getRadius() const
Definition: UT_RTree.h:74
T getMin(const int c) const
Definition: UT_RTree.C:76
UT_SphereT< fpreal64 > UT_SphereD
Definition: UT_RTree.h:300
void expandDistance(const T l)
Definition: UT_RTree.C:150
void absorbPoint(UT_Vector3T< U > p)
Definition: UT_RTree.h:89
UT_Vector3T< T > getCenter() const
Definition: UT_RTree.h:55
UT_BoxT< T > boundingBox(const UT_RTreeBoxAssignmentT< T > &assignment) const
Definition: UT_RTree.C:1053
void assignPoint(const U p[3])
Definition: UT_RTree.C:97
bool isEmpty() const
Definition: UT_RTree.C:65
void UTappendIntersectingItems(UT_IntArray &results, const UT_RTreeGeneric< MAX_ORDER > &tree, const QUERY_SHAPE &query_box, const UT_RTreeBoxAssignmentT< T > &assignment, exint baseindex)
Definition: UT_RTree.C:994
T getRadius2() const
Definition: UT_RTree.h:67
3D Vector class.
bool intersects(const UT_BoxT< T > &b) const
Definition: UT_RTree.C:186
void UTgetIntersectingItems(UT_IntArray &results, const UT_RTreeGeneric< MAX_ORDER > &tree, const QUERY_SHAPE &query_box, const UT_RTreeBoxAssignmentT< T > &assignment)
Definition: UT_RTree.C:981
GLsizeiptr size
Definition: glcorearb.h:663
void getIntersectingItems(RESULT_ACCEPTOR &result_acceptor, const QUERY_SHAPE &query_box, const UT_RTreeBoxAssignmentT< T > &assignment) const
Definition: UT_RTree.C:937
void absorbPoint(const U p[3])
Definition: UT_RTree.C:111
bool contains(const T *const p) const
Definition: UT_RTree.C:177
UT_BoxT()
Definition: UT_RTree.C:20
UT_SphereT< fpreal32 > UT_SphereF
Definition: UT_RTree.h:299
int64 exint
Definition: SYS_Types.h:109
UT_RTreeBoxAssignmentT< fpreal64 > UT_RTreeBoxAssignmentD
Definition: UT_RTree.h:305
void createBoxAssignment(UT_RTreeBoxAssignmentT< T > &assignment, const UT_BoxT< T > item_boxes[]) const
Definition: UT_RTree.C:901
UT_BoxT< fpreal64 > UT_BoxD
Definition: UT_RTree.h:295
UT_SphereT(const U p[3], const U r)
Definition: UT_RTree.h:132
UT_RTreeBoxAssignmentT< fpreal64 > UT_RTreeBoxAssignment
Definition: UT_RTree.h:306
UT_RTreeGeneric< 16 > UT_RTree16
Definition: UT_RTree.h:310
int getNumItems() const
Definition: UT_RTree.C:686
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
T Scalar
Definition: UT_RTree.h:30
exint getMemoryUsage() const
Definition: UT_RTree.h:202
UT_RTreeGeneric< 2 > UT_RTree2
Definition: UT_RTree.h:309
void absorbBox(const UT_BoxT< T > &b)
Definition: UT_RTree.C:124
int getLargestAxis() const
Definition: UT_RTree.C:197
UT_RTreeGeneric< 2 > UT_RTree
Definition: UT_RTree.h:311
void assignPoint(UT_Vector3T< U > p)
Definition: UT_RTree.h:83
bool intersects(const UT_BoxT< T > &b) const
Definition: UT_RTree.C:237
Definition: ImathBox.h:72
T getMax(const int c) const
Definition: UT_RTree.C:86
SYS_FORCE_INLINE Storage::AtLeast32Bit length2() const noexcept
GLboolean r
Definition: glcorearb.h:1221
UT_Vector3T< T > getSize() const
Definition: UT_RTree.h:61
UT_BoxT< fpreal32 > UT_BoxF
Definition: UT_RTree.h:294
UT_SphereT< fpreal64 > UT_Sphere
Definition: UT_RTree.h:301
exint getMemoryUsage() const
Definition: UT_RTree.h:163
UT_RTreeBoxAssignmentT< fpreal32 > UT_RTreeBoxAssignmentF
Definition: UT_RTree.h:304
UT_BoxT< fpreal64 > UT_Box
Definition: UT_RTree.h:296