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: RTree.h (UT Library, C++)
7  *
8  * COMMENTS:
9  */
10 
11 #ifndef __RTree_H__
12 #define __RTree_H__
13 
14 #include "UT_API.h"
15 
16 #include "UT_RTreeBox.h"
17 
18 #include "UT_Array.h"
19 
20 #include <memory>
21 
22 namespace UT
23 {
24 
25 template< typename ITEM_INDEX, int MAX_ORDER > class RTreeT;
26 template< typename FT > class RTreeConfigurationT;
27 
28 //
29 // Construct an R-tree that contains items with indices in [ 0, num_items ).
30 // During the construction, item_box[ i ] is used as the bounding box
31 // for item #i.
32 // These boxes determine only the initial structure of the R-tree;
33 // the passed-in box positions and dimensions are not stored in the R-tree.
34 //
35 // Empty boxes are allowed: each item that has an empty box is guaranteed
36 // to never be returned by any of the getIntersectingItems queries.
37 // This is useful because it helps avoid the need for re-indexing
38 // in the client code, in case certain items need to be omitted from the tree.
39 //
40 // 'num_items' must be less than 2^{ 8 * sizeof(ItemIndex) - 2 }
41 // In case ItemIndex is 32 bit int, this is 2^30 == 1073741824
42 //
43 template< typename ITEM_INDEX, int MAX_ORDER, typename FT >
44 RTreeT< ITEM_INDEX, MAX_ORDER > constructRTree( const UT_BoxT< FT > item_box[], const ITEM_INDEX num_items );
45 
46 // Convenience version of constructRTree that takes a UT_Array of boxes
47 template< typename ITEM_INDEX, int MAX_ORDER, typename FT >
49 
50 template< typename ITEM_INDEX, int MAX_ORDER, typename FT >
52 
53 // Convenience version of constructRTreeConfiguration that takes a UT_Array of boxes
54 template< typename ITEM_INDEX, int MAX_ORDER, typename FT >
56 
57 
58 //
59 // For each item i, if item_box[i] intersects query_box, call accept_item( i ).
60 // This assumes there exists a free-standing 'intersects' function that takes a
61 // QUERY_SHAPE and a UT_BoxT< FT >.
62 //
63 template< typename ITEM_INDEX, int MAX_ORDER, typename FT, typename QUERY_SHAPE, typename ACCEPT_ITEM >
65  ACCEPT_ITEM&& accept_item,
67  const RTreeConfigurationT< FT >& configuration,
68  const QUERY_SHAPE& query_shape
69 );
70 
71 //
72 // Assign a new box to each item: To item index i, assign item_box[ i ].
73 // Updated configurations can be used with the original tree,
74 // for example, when alternating collision detection and collision response passes.
75 // however, when the boxes change too much from the boxes used to construct
76 // the R-tree, queries become less efficient, in which case
77 // a new R-tree should be built.
78 //
79 // ITEM_BOX must be an array-like type (it supports operator[]),
80 // for example, const ITEM_BOX*, UT_Array< ITEM_BOX> or std::vector< ITEM_BOX >
81 // Each element item_box[ i ] must convert into a UT_BoxT< FT >.
82 //
83 // 'num_items' must match the number of items in the tree
84 //
85 template< typename ITEM_INDEX, int MAX_ORDER, typename FT >
87  RTreeConfigurationT< FT >& configuration,
89  const UT_BoxT< FT > item_box[],
90  const ITEM_INDEX num_items
91 );
92 
93 template< typename ITEM_INDEX_REP, int MAX_ORDER >
94 class RNodeT;
95 
96 //
97 // ItemIndexUnderlyingInteger:
98 // Map ITEM_INDEX value to its underlying integer representation.
99 // This can be specialized for any strong index type that needs to be used with RTreeT.
100 // (e.g., GA_Offset, GA_Index, SC::StrongIndex ).
101 //
102 // Primary
103 // This catches all cases where ITEM_INDEX is a built-in integer type
104 //
105 template< typename ITEM_INDEX >
107 {
108  constexpr auto operator()( const ITEM_INDEX i ) const noexcept
109  {
110  return i;
111  }
112 };
113 
114 template< typename ITEM_INDEX >
115 struct ItemIndex_UnderlyingIntegerType : SYS_TypeIdentity< SYS_RemoveCVRef_t< decltype( ItemIndexUnderlyingInteger< ITEM_INDEX >{}( std::declval< ITEM_INDEX >() ) ) > > {};
116 
117 template< typename ITEM_INDEX >
119 
120 //
121 // The order of the R-Tree is the number of children that each
122 // internal node in the tree has. Picking a higher value of
123 // MAX_ORDER will reduce the height of the R-tree.
124 // R-tree stores a containment structure for the boxes that are
125 // passed to its contructor, but doesn't store any actual boxes.
126 // That's why RTree doesn't take the number type T as a template parameter.
127 //
128 template< typename ITEM_INDEX, int MAX_ORDER >
129 class RTreeT
130 {
131 public:
132  // Each item held by the R-tree is represented by an index
133  // These indices are relative to arrays held by the client code
134  using ItemIndex = ITEM_INDEX;
135  static constexpr int max_order = MAX_ORDER;
136 
137  RTreeT( RTreeT&& );
138  ~RTreeT();
139 
140  RTreeT() = delete;
141  RTreeT( const RTreeT& ) = delete;
142  RTreeT& operator=( const RTreeT& ) = delete;
143 
144 private:
147 
148  // Single contiguous array containing all the R-tree nodes
149  exint myNumNodes;
150  std::unique_ptr< Node[] > myNodes;
151 
152  // myRoot is non owned; it points to an element of the array myNodes
153  Node* myRoot;
154 
155  // Number of items passed into constructor
156  ItemIndexRep myNumItems;
157 
158  template< typename FT >
159  RTreeT( const UT_BoxT< FT > item_box[], const ITEM_INDEX num_items );
160 
161  // Convenience version that takes a UT_Array of boxes instead
162  template< typename FT >
163  RTreeT( const UT_Array< UT_BoxT< FT > >& item_box );
164 
165  template< typename ALT_ITEM_INDEX, int ALT_MAX_ORDER, typename FT >
166  friend RTreeT< ALT_ITEM_INDEX, ALT_MAX_ORDER > constructRTree( const UT_BoxT< FT > item_box[], const ALT_ITEM_INDEX num_items );
167 
168  template< typename ALT_ITEM_INDEX, int ALT_MAX_ORDER, typename FT >
170 
171  template< typename ALT_ITEM_INDEX, int ALT_MAX_ORDER, typename FT, typename QUERY_SHAPE, typename ACCEPT_ITEM >
172  friend void forEachIntersecting(
173  ACCEPT_ITEM&& accept_item,
175  const RTreeConfigurationT< FT >& configuration,
176  const QUERY_SHAPE& query_shape
177  );
178 
179  template< typename ALT_ITEM_INDEX, int ALT_MAX_ORDER, typename FT >
180  friend void updateConfiguration(
181  RTreeConfigurationT< FT >& configuration,
183  const UT_BoxT< FT > item_box[],
184  const ALT_ITEM_INDEX num_items
185  );
186 
187  template< typename ALT_ITEM_INDEX, int ALT_MAX_ORDER >
189 };
190 
191 template< typename FT >
192 exint heapMemoryUsage( const RTreeConfigurationT< FT >& configuration );
193 
194 // This is an assigment of a box to each item stored in the R-tree.
195 // It is passed an argument to queries on the R-tree.
196 // This way, an R-tree can be re-used efficiently if the item boxes change.
197 // This will only remain efficient as long as the configuration of boxes
198 // doesn't change dramatically.
199 template< typename FT >
201 {
202 public:
204 
205 private:
206  using Box = UT_BoxT< FT >;
207 
208  // Box #s of node n is stored at index ( MAX_ORDER * tree.myNumNodes ) + s
209  // of myNodeSlotBox
210  exint myNodeSlotBoxSize;
211  std::unique_ptr< Box[] > myNodeSlotBox;
212 
213 
215  const exint node_slot_box_size,
216  std::unique_ptr< Box[] >&& node_slot_box
217  );
218 
219  // Disallow
220  RTreeConfigurationT() = delete;
221  RTreeConfigurationT( const RTreeConfigurationT& ) = delete;
222  RTreeConfigurationT& operator=( const RTreeConfigurationT& ) = delete;
223 
224  template< typename ITEM_INDEX, int MAX_ORDER > friend class RTreeT;
225 
226 
227  template< typename ITEM_INDEX, int MAX_ORDER, typename ALT_FT >
229 
230  template< typename ITEM_INDEX, int MAX_ORDER, typename ALT_FT, typename QUERY_SHAPE, typename ACCEPT_ITEM >
231  friend void forEachIntersecting(
232  ACCEPT_ITEM&& accept_item,
234  const RTreeConfigurationT< ALT_FT >& configuration,
235  const QUERY_SHAPE& query_shape
236  );
237 
238  template< typename ITEM_INDEX, int MAX_ORDER, typename ALT_FT >
239  friend void updateConfiguration(
240  RTreeConfigurationT< ALT_FT >& configuration,
242  const UT_BoxT< ALT_FT > item_box[],
243  const ITEM_INDEX num_items
244  );
245  friend exint heapMemoryUsage <>( const RTreeConfigurationT< FT >& configuration );
246 };
247 
248 //
249 // Convenience for assigning boxes stored in containers other than built-in arrays
250 //
251 
252 template< typename ITEM_INDEX, int MAX_ORDER, typename FT >
254  RTreeConfigurationT< FT >& configuration,
256  const UT_Array< UT_BoxT< FT > >& item_box
257 );
258 
259 //
260 // Helpers for storing query results in containers
261 //
262 
263 // On return, 'results' consists of all items i for which item_box[i]
264 // intersects 'query_shape'.
265 // The contents of "results" from before the call are cleared, so it
266 // is not neccessary to call results.clear() before calling this function.
267 template< typename QUERY_SHAPE, typename ITEM_INDEX, int MAX_ORDER, typename FT >
268 void getIntersecting(
269  UT_Array< ITEM_INDEX >& results,
271  const RTreeConfigurationT< FT >& configuration,
272  const QUERY_SHAPE& query_shape
273 );
274 
275 // Return all items i for which item_box[ i ] intersects query_box.
276 // The resulting items will be stored in the range [ items_begin, items_end ),
277 // where items_end is the return value.
278 // It is assumed that the array starting at items_begin is large enough
279 // to contain the results (at most the total number of items).
280 template< typename QUERY_SHAPE, typename ITEM_INDEX, int MAX_ORDER, typename FT >
281 ITEM_INDEX* getIntersectingRaw(
283  const RTreeConfigurationT< FT >& configuration,
284  const QUERY_SHAPE& query_shape,
285  ITEM_INDEX*const items_begin
286 );
287 
288 // Various R-tree types
289 
290 // RTree with index type 'int': max number of items is 2^30
291 // (two most significant bits are used as flags)
295 
296 // RTree with index type 'exint': up to 2^62 items in theory
297 // (two most significant bits are used as flags)
299 
300 // R-tree box configurations for various float types
304 
305 // R-tree boxes for various float types
309 
310 }
311 // namespace UT
312 
313 //
314 // The below typedefs and functions are used by existing code
315 // that used R-tree before its interface got updated.
316 //
317 
321 
323 
328 
332 
336 
340 
341 template< typename FT >
343 
344 template< typename FT >
346 
347 template< typename FT >
349 
350 template< typename FT >
352 
353 template< typename FT >
355 
356 template< typename FT >
357 UT_RTree UTconstructRTree( const UT_Array< UT_BoxT< FT > >& item_box );
358 
359 template< typename FT >
361 
362 template< typename FT >
364 
365 template< typename FT >
367 
368 template< typename FT >
370 
371 template< typename FT >
373 
374 template< typename FT >
375 auto UTmakeUniqueRTree2Int( const UT_Array< UT_BoxT< FT > >& item_box );
376 
377 template< typename FT >
378 auto UTmakeUniqueRTree16Int( const UT_Array< UT_BoxT< FT > >& item_box );
379 
380 template< typename FT >
381 auto UTmakeUniqueRTreeInt( const UT_Array< UT_BoxT< FT > >& item_box );
382 
383 template< typename FT >
384 auto UTmakeUniqueRTreeInt( const UT_BoxT< FT > item_box[], const UT_RTree::ItemIndex num_items );
385 
386 template< typename FT >
387 auto UTmakeUniqueRTree2IntConfiguration( const UT_RTree2Int& tree, const UT_Array< UT_BoxT< FT > >& item_box );
388 
389 template< typename FT >
390 auto UTmakeUniqueRTree16IntConfiguration( const UT_RTree16Int& tree, const UT_Array< UT_BoxT< FT > >& item_box );
391 
392 template< typename FT >
393 auto UTmakeUniqueRTreeIntConfiguration( const UT_RTreeInt& tree, const UT_Array< UT_BoxT< FT > >& item_box );
394 
395 template< typename FT >
397 
398 #include "UT_RTreeImpl.h"
399 
400 #endif // __RTree_H__
401 
auto UTmakeUniqueRTree16IntConfiguration(const UT_RTree16Int &tree, const UT_Array< UT_BoxT< FT > > &item_box)
UT_BoxT< fpreal64 > RTreeBoxD
Definition: UT_RTree.h:307
RTreeT< int, 2 > RTreeInt
Definition: UT_RTree.h:294
Definition: UT_BVH.h:37
UT_BoxT< fpreal32 > RTreeBoxF
Definition: UT_RTree.h:306
static constexpr int max_order
Definition: UT_RTree.h:135
auto UTmakeUniqueRTreeInt(const UT_Array< UT_BoxT< FT > > &item_box)
int64 exint
Definition: SYS_Types.h:125
auto UTmakeUniqueRTreeIntConfiguration(const UT_RTreeInt &tree, const UT_Array< UT_BoxT< FT > > &item_box)
friend RTreeConfigurationT< ALT_FT > constructRTreeConfiguration(const RTreeT< ITEM_INDEX, MAX_ORDER > &tree, const UT_BoxT< ALT_FT > item_box[], const ITEM_INDEX num_items)
exint heapMemoryUsage(const RTreeConfigurationT< FT > &configuration)
Definition: UT_RTreeImpl.h:838
RTreeConfigurationT< fpreal64 > RTreeConfigurationD
Definition: UT_RTree.h:302
friend RTreeT< ALT_ITEM_INDEX, ALT_MAX_ORDER > constructRTree(const UT_BoxT< FT > item_box[], const ALT_ITEM_INDEX num_items)
friend RTreeConfigurationT< FT > constructRTreeConfiguration(const RTreeT< ALT_ITEM_INDEX, ALT_MAX_ORDER > &tree, const UT_BoxT< FT > item_box[], const ALT_ITEM_INDEX num_items)
UT_RTree2IntConfigurationT< FT > UTconstructRTree2IntConfiguration(const UT_RTree2Int &tree, const UT_Array< UT_BoxT< FT > > &item_box)
friend void forEachIntersecting(ACCEPT_ITEM &&accept_item, const RTreeT< ITEM_INDEX, MAX_ORDER > &tree, const RTreeConfigurationT< ALT_FT > &configuration, const QUERY_SHAPE &query_shape)
auto UTmakeUniqueRTree16Int(const UT_Array< UT_BoxT< FT > > &item_box)
RTreeT< exint, 2 > RTree
Definition: UT_RTree.h:298
RTreeT< ITEM_INDEX, MAX_ORDER > constructRTree(const UT_BoxT< FT > item_box[], const ITEM_INDEX num_items)
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1222
RTreeConfigurationT< FT > constructRTreeConfiguration(const UT::RTreeT< ITEM_INDEX, MAX_ORDER > &tree, const UT_BoxT< FT > item_box[], const ITEM_INDEX num_items)
auto UTmakeUniqueRTree2Int(const UT_Array< UT_BoxT< FT > > &item_box)
SYS_RemoveCVRef_t< decltype(ItemIndexUnderlyingInteger< ITEM_INDEX >{}(std::declval< ITEM_INDEX >())) > type
friend void updateConfiguration(RTreeConfigurationT< FT > &configuration, const RTreeT< ALT_ITEM_INDEX, ALT_MAX_ORDER > &tree, const UT_BoxT< FT > item_box[], const ALT_ITEM_INDEX num_items)
UT_BoxT< fpreal64 > RTreeBox
Definition: UT_RTree.h:308
UT_RTree16Int UTconstructRTree16Int(const UT_Array< UT_BoxT< FT > > &item_box)
Definition: UT_RTreeImpl.h:966
ITEM_INDEX ItemIndex
Definition: UT_RTree.h:134
void forEachIntersecting(ACCEPT_ITEM &&accept_item, const RTreeT< ITEM_INDEX, MAX_ORDER > &tree, const RTreeConfigurationT< FT > &configuration, const QUERY_SHAPE &query_shape)
Definition: UT_RTreeImpl.h:913
auto UTmakeUniqueRTree2IntConfiguration(const UT_RTree2Int &tree, const UT_Array< UT_BoxT< FT > > &item_box)
UT_RTree16IntConfigurationT< FT > UTconstructRTree16IntConfiguration(const UT_RTree16Int &tree, const UT_Array< UT_BoxT< FT > > &item_box)
num_items
Definition: UT_RTreeImpl.h:672
void updateConfiguration(RTreeConfigurationT< FT > &configuration, const RTreeT< ITEM_INDEX, MAX_ORDER > &tree, const UT_BoxT< FT > item_box[], const ITEM_INDEX num_items)
Definition: UT_RTreeImpl.h:846
RTreeT & operator=(const RTreeT &)=delete
typename ItemIndex_UnderlyingIntegerType< ITEM_INDEX >::type ItemIndex_UnderlyingIntegerType_t
Definition: UT_RTree.h:118
friend void updateConfiguration(RTreeConfigurationT< ALT_FT > &configuration, const RTreeT< ITEM_INDEX, MAX_ORDER > &tree, const UT_BoxT< ALT_FT > item_box[], const ITEM_INDEX num_items)
RTreeT< int, 2 > RTree2Int
Definition: UT_RTree.h:293
UT_RTreeInt UTconstructRTreeInt(const UT_BoxT< FT > item_box[], const UT_RTreeInt::ItemIndex num_items)
Definition: UT_RTreeImpl.h:978
RTreeConfigurationT< fpreal32 > RTreeConfigurationF
Definition: UT_RTree.h:301
UT_RTree2Int UTconstructRTree2Int(const UT_Array< UT_BoxT< FT > > &item_box)
Definition: UT_RTreeImpl.h:972
friend void forEachIntersecting(ACCEPT_ITEM &&accept_item, const RTreeT< ALT_ITEM_INDEX, ALT_MAX_ORDER > &tree, const RTreeConfigurationT< FT > &configuration, const QUERY_SHAPE &query_shape)
RTreeConfigurationT< fpreal64 > RTreeConfiguration
Definition: UT_RTree.h:303
RTreeT()=delete
UT_RTreeConfigurationT< FT > UTconstructRTreeConfiguration(const UT_RTree &tree, const UT_Array< UT_BoxT< FT > > &item_box)
constexpr auto operator()(const ITEM_INDEX i) const noexcept
Definition: UT_RTree.h:108
UT_RTreeIntConfigurationT< FT > UTconstructRTreeIntConfiguration(const UT_RTreeInt &tree, const UT_Array< UT_BoxT< FT > > &item_box)
RTreeT< int, 16 > RTree16Int
Definition: UT_RTree.h:292
void getIntersecting(UT_Array< ITEM_INDEX > &results, const RTreeT< ITEM_INDEX, MAX_ORDER > &tree, const RTreeConfigurationT< FT > &configuration, const QUERY_SHAPE &query_shape)
Definition: UT_RTreeImpl.h:892
UT_RTree UTconstructRTree(const UT_BoxT< FT > item_box[], const UT_RTree::ItemIndex num_items)
Definition: UT_RTreeImpl.h:990
ITEM_INDEX * getIntersectingRaw(const RTreeT< ITEM_INDEX, MAX_ORDER > &tree, const RTreeConfigurationT< FT > &configuration, const QUERY_SHAPE &query_shape, ITEM_INDEX *const items_begin)
Definition: UT_RTreeImpl.h:947
friend exint heapMemoryUsage(const RTreeT< ALT_ITEM_INDEX, ALT_MAX_ORDER > &tree)