HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_RTreeImpl.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.C (UT library, C++)
7  *
8  * COMMENTS:
9  */
10 
11 #ifndef __UT_RTREEIMPL_H_INCLUDED__
12 #define __UT_RTREEIMPL_H_INCLUDED__
13 
14 #include "UT_UniquePtr.h"
15 
16 #include <utility>
17 
18 template< typename BOX, typename ITEM_INDEX_REP >
20 {
21  //TODO: C++17: static_assert( SYS_IsIntegral_v< ITEM_INDEX_REP > );
22 
23  using Box = BOX;
24  using ItemIndexRep = ITEM_INDEX_REP;
25 
28 
30  myBox(),
31  myItem(-1)
32  {
33  }
34 
36  const Box& box,
37  const ItemIndexRep item
38  ) :
39  myBox( box ),
40  myItem( item )
41  {
42  }
43 };
44 
45 #if 0
46 
47 template< typename BOX, typename ITEM_INDEX_REP >
48 inline std::ostream& operator<<(std::ostream& os, const UT_BoxedItemT< BOX, ITEM_INDEX_REP >& bf)
49 {
50  os << "BoxedItem{ ";
51  os << "box = ";
52  os << bf.myBox << ", ";
53  os << "item = ";
54  os << bf.myItem;
55  os << " }";
56  return os;
57 }
58 
59 #endif
60 
61 // Compute the bounding box for a range of boxes [begin, end)
62 template< typename BOX >
63 inline void computeBoundingBox(
64  BOX& bounding_box,
65  const BOX*const begin,
66  const BOX*const end
67 )
68 {
69  bounding_box = BOX(); // empty
70 
71  for( const BOX* i = begin; i != end; ++i )
72  {
73  bounding_box.absorbBox(*i);
74  }
75 }
76 
77 // Compute the bounding box for all the boxes in
78 // a range of boxed items [begin, end)
79 template< typename BOX, typename ITEM_INDEX_REP >
81  BOX& bounding_box,
84 )
85 {
86  static_assert( SYS_IsIntegral_v< ITEM_INDEX_REP > );
87 
88  UT_ASSERT_P( end != begin );
89 
90  bounding_box = begin->myBox;
91 
92  for( const UT_BoxedItemT< BOX, ITEM_INDEX_REP >* i = begin + 1; i != end; ++i )
93  {
94  bounding_box.absorbBox(i->myBox);
95  }
96 }
97 
98 namespace UT
99 {
100 
101 template< typename ITEM_INDEX_REP, int MAX_ORDER >
102 class RNodeT
103 {
104 public:
105  //TODO: C++17: static_assert( SYS_IsIntegral_v< ITEM_INDEX_REP > );
106 
107  using Slot = std::make_unsigned_t< ITEM_INDEX_REP >;
108 
110  {
111  clear();
112  }
113 
115  {
116  }
117 
118  void clear()
119  {
120  setInternal(false);
121  for( int s = 0; s < MAX_ORDER; ++s )
122  {
124  }
125  }
126 
127  void setInternal(const bool isInternal)
128  {
129  mySlots[0] = ( (mySlots[0] & SLOT_MASK_INDEX) |
130  (isInternal ? SLOT_FLAG_INTERNAL : 0) );
131  }
132 
133  // Assuming this is an internal node, assign a node index to slot #s
134  void assignSubtree( const int s, const Slot index_root_subtree )
135  {
136  UT_ASSERT_P( isInternal() );
137  UT_ASSERT_P( (0 <= s) && (s < MAX_ORDER) );
138  UT_ASSERT_P( 0 <= index_root_subtree );
139  UT_ASSERT_P( ( index_root_subtree & SLOT_MASK_INDEX ) == index_root_subtree );
140 
141  mySlots[s] = index_root_subtree | SLOT_FLAG_INTERNAL;
142  }
143 
144  // Assign an item to slot #s
145  void assignItem( const int s, const ITEM_INDEX_REP item )
146  {
147  UT_ASSERT_P( !isInternal() );
148  UT_ASSERT_P( (0 <= s) && (s < MAX_ORDER) );
149  UT_ASSERT_P( 0 <= item );
150  UT_ASSERT_P( ( item & SLOT_MASK_INDEX) == item );
151 
152  mySlots[s] = item;
153  }
154 
155  bool isInternal() const
156  {
157  return ((mySlots[0] & SLOT_FLAG_INTERNAL) != 0);
158  }
159 
160  // Get node stored in slot.
161  // This assumes that the last configuration to this slot was an node!
162  // (not an item)
163  Slot getSubtree(const int s) const
164  {
165  UT_ASSERT( isInternal() );
166  UT_ASSERT( (0 <= s) && (s < MAX_ORDER) );
168 
169  return (mySlots[s] & SLOT_MASK_INDEX);
170  }
171 
172  // For internal nodes, count the number of children
173  // For leaf nodes, count the number of items
174  ITEM_INDEX_REP countNumItems() const
175  {
176  ITEM_INDEX_REP num_items(0);
177  for( int s = 0; s < MAX_ORDER; ++s )
178  {
180  break;
181 
182  ++num_items;
183  }
184 
185  return num_items;
186  }
187 
188  // Get item index stored in slot.
189  // This assumes that the last configuration to this slot was an item!
190  // (not an RTree node)
191  SYS_FORCE_INLINE ITEM_INDEX_REP getItemIndexRep( const int s ) const
192  {
193  UT_ASSERT( !isInternal() );
194  UT_ASSERT( (0 <= s) && (s < MAX_ORDER) );
196 
197  return (mySlots[s] & SLOT_MASK_INDEX);
198  }
199 
200  static const Slot SLOT_FLAG_INTERNAL = Slot( 1 ) << ( ( sizeof( Slot ) * 8 ) - 1 );
203 
204  //
205  // mySlots[0] has a bit that defines whether the node is an internal
206  // node. This is the SLOT_FLAG_INTERNAL bit.
207  // In an internal node, each non-empty slot has the index of a child
208  // node.
209  // In a leaf node, each non-empty slot has the index of an item.
210  //
211  // A node (internal or leaf) may not always be full
212  // (fewer than MAX_ORDER children for internal node case, or fewer than
213  // MAX_ORDER items for leaf case).
214  // When the node is not full, then the empty slots form
215  // a contiguous range after all the nonempty slots.
216  // The full range consists of the slots s in the half-open range
217  // [ 0, num_items )
218  //
219 
220  Slot mySlots[ MAX_ORDER ];
221 };
222 
223 // Determine the exact number of nodes needed to store an R-tree of MAX_ORDER
224 // based on "size" nonempty boxes.
225 // The O(log n) cost of this calculation is insignificant compared to
226 // the time it takes to construct the tree.
227 inline size_t
228 subtreeDetermineNumNodes( const int MAX_ORDER, const size_t size )
229 {
230  int num_nodes(0);
231 
232  if( size > MAX_ORDER )
233  {
234  // Internal node
235 
236  ++num_nodes;
237 
238  size_t m(MAX_ORDER);
239  while( m * MAX_ORDER < size )
240  {
241  m *= MAX_ORDER;
242  }
243 
244  UT_ASSERT_P( MAX_ORDER <= m );
245  UT_ASSERT_P( m < size );
246 
247  // Count number of nodes for the at most MAX_ORDER subtrees that
248  // have exactly m elements
249 
250  const size_t num_subtrees_size_m( size / m );
251 
252  UT_ASSERT_P( num_subtrees_size_m <= MAX_ORDER );
253 
254  const size_t num_nodes_for_m( subtreeDetermineNumNodes(MAX_ORDER, m) );
255 
256  num_nodes += num_subtrees_size_m * num_nodes_for_m;
257 
258  // Count number of nodes for the subtree with the less than m
259  // remaining elements (if this exists)
260 
261  const size_t num_remaining_items( size % m );
262  if( num_remaining_items > 0 )
263  {
264  num_nodes += subtreeDetermineNumNodes(MAX_ORDER, num_remaining_items);
265  }
266  }
267  else
268  {
269  // Leaf node
270 
271  ++num_nodes;
272  }
273 
274  return num_nodes;
275 }
276 
277 /// Partition the range of boxed items [begin, end) according to the given
278 /// comparison function such that all items in the range [0, m-1] are less than
279 /// or equal to all items in [m, 2m-1], which are less than or equal to all
280 /// items in [2m, 3m-1], etc, where m is the subtree size.
281 template< typename BOX, typename ITEM_INDEX_REP >
283 {
284  template< typename IS_LESS_THAN >
285  constexpr inline void operator()(
288  IS_LESS_THAN&& is_less_than,
289  const ITEM_INDEX_REP m,
290  const int num_subtrees
291  ) const noexcept
292  {
293  if( num_subtrees <= 1 )
294  {
295  return;
296  }
297 
298  // Choose a multiple of the subtree size that's close to the middle, and
299  // partition so that all items in [begin, begin + i) are less than or equal
300  // to all items in [begin + i, end).
301  const auto mid{ num_subtrees / 2 };
302  const auto i{ mid * m };
303  UTnth_element( begin, begin + i, end, is_less_than );
304 
305  // Recursively partition each side.
306  PartitionForSubtrees< BOX, ITEM_INDEX_REP >{}( begin, begin + i, std::forward< IS_LESS_THAN >( is_less_than ), m, mid);
307  PartitionForSubtrees< BOX, ITEM_INDEX_REP >{}( begin + i, end, std::forward< IS_LESS_THAN >( is_less_than ), m, num_subtrees - mid);
308  }
309 };
310 
311 // Create a subtree for the range of boxed items [begin, end).
312 // Return a pointer to the subtree root (this points into in shared_nodes)
313 // In addition, bounding_box will be a bounding box for the subtree.
314 // PRE: Each boxed item in [begin, end) has a nonempty box
315 // NOTE: No allocations are performed by this function, the returned pointer
316 // points into the array 'shared_nodes'
317 template< typename BOX, typename ITEM_INDEX_REP, int MAX_ORDER >
318 inline RNodeT< ITEM_INDEX_REP, MAX_ORDER >*
320  BOX& bounding_box,
321  BOX shared_boxes[],
326 )
327 {
328  static_assert( SYS_IsIntegral_v< ITEM_INDEX_REP > );
329 
331  using Box = BOX;
333 
334  SYS_STATIC_ASSERT( MAX_ORDER >= 2 );
335 
336 #if UT_ASSERT_LEVEL >= UT_ASSERT_LEVEL_PARANOID
337  for( const BoxedItem* i = begin; i != end; ++i )
338  {
339  UT_ASSERT_P( ! i->myBox.isEmpty() );
340  }
341 #endif
342 
343  // Claim storage for the root node
344  RNode* node( shared_nodes_end++ );
345 
346  node->clear();
347 
348  // node_boxes is the sub-array that contains the at most MAX_ORDER boxes
349  // for the node that we're building
350  Box*const node_boxes( shared_boxes + ((node - shared_nodes) * MAX_ORDER) );
351 
352  const size_t size(end - begin);
353 
354  UT_ASSERT_P( size > 0 );
355 
356  computeBoundingBoxItem(bounding_box, begin, end);
357 
358  if( size > MAX_ORDER )
359  {
360  // Create an internal node at most MAX_ORDER nonempty slots.
361  // slot #s will have the index of the root of a subtree,
362  // which is contained in node_boxes[s]
363 
364  node->setInternal(true);
365 
366  // Partition in a way that is balanced but that aims
367  // to keep the number of unused slots in leaves very small
368  // Pick "m" to be the ideal number of items per subtree.
369  ITEM_INDEX_REP m{ MAX_ORDER };
370  while( m * MAX_ORDER < size )
371  {
372  m *= MAX_ORDER;
373  }
374 
375  UT_ASSERT_P( MAX_ORDER <= m );
376  UT_ASSERT_P( m < size );
377 
378  // Create at most MAX_ORDER subtrees, each of which has exactly m elements
379  const int num_subtrees_size_m( size / m );
380 
381  UT_ASSERT_P( num_subtrees_size_m <= MAX_ORDER );
382 
383  //
384  {
385  // TODO: perhaps splitting along a single axis is not the best
386  // if MAX_ORDER > 2
387 
388  const int largest_axis = bounding_box.getLargestAxis();
389 
390  const auto is_less_than = [largest_axis]( const BoxedItem& a, const BoxedItem& b )
391  {
392  return ( signAxisCenterComparison( largest_axis, a.myBox, b.myBox ) == 1 );
393  };
394 
395  // Partition the elements for each subtree.
397  begin, end,
398  is_less_than,
399  m, num_subtrees_size_m
400  );
401  }
402 
403  // offset relative to 'begin':
404  // the at most 'm' elements for subtree #s start at begin + offset
405  size_t offset(0);
406 
407  for( int s = 0; s < num_subtrees_size_m; ++s )
408  {
409  if( size - offset < m )
410  {
411  break;
412  }
413 
414  const size_t next_offset( offset + m );
415 
416  node->assignSubtree(
417  s,
419  node_boxes[s],
420  shared_boxes,
421  begin + offset, begin + next_offset,
422  shared_nodes,
423  shared_nodes_end
424  ) - shared_nodes //FIXME: ugly pointer arithmetic
425  );
426 
427  offset = next_offset;
428  }
429 
430  // If needed, construct a subtree for any remaining elements (strictly less than m)
431  const size_t num_remaining_items( size % m );
432  if( num_remaining_items > 0 )
433  {
434  UT_ASSERT_P( num_subtrees_size_m < MAX_ORDER );
435  UT_ASSERT_P( num_remaining_items == size - offset );
436 
437  const size_t next_offset( offset + num_remaining_items );
438 
439  node->assignSubtree(
440  num_subtrees_size_m,
442  node_boxes[num_subtrees_size_m],
443  shared_boxes,
444  begin + offset, begin + next_offset,
445  shared_nodes,
446  shared_nodes_end
447  ) - shared_nodes //FIXME: ugly pointer arithmetic
448  );
449 
450  offset = next_offset;
451  }
452 
453  UT_ASSERT_P( offset == size );
454 
455  UT_ASSERT_P( node->countNumItems() > 0 );
456  }
457  else
458  {
459  // Create a leaf with size nonempty slots.
460  // Each slot has the index of a shared node box.
461  node->setInternal(false);
462 
463  int s(0);
464  for( const BoxedItem* i = begin; i != end; ++i )
465  {
466  node_boxes[s] = i->myBox;
467  node->assignItem(s, i->myItem);
468  ++s;
469  }
470  }
471 
472  return node;
473 }
474 
475 template< typename ITEM_INDEX_REP, int MAX_ORDER, typename ITEM_BOX, typename FT >
476 inline void
478  UT_BoxT< FT >& bounding_box,
480  const RNodeT< ITEM_INDEX_REP, MAX_ORDER > shared_nodes[],
481  const RNodeT< ITEM_INDEX_REP, MAX_ORDER >*const node,
482  ITEM_BOX&& item_box
483 )
484 {
485  static_assert( SYS_IsIntegral_v< ITEM_INDEX_REP > );
486 
488  using Box = UT_BoxT< FT >;
489 
490  UT_ASSERT_P( node != 0 );
491 
492  // s_box is the sub-array that contains the MAX_ORDER boxes
493  // for the node that we're visiting
494  Box*const s_box(
495  shared_boxes +
496  ((node - shared_nodes) * MAX_ORDER)
497  );
498 
499  if( node->isInternal() )
500  {
501  for( int s = 0; s < MAX_ORDER; ++s )
502  {
503  if( (node->mySlots[s] & RNode::SLOT_MASK_INDEX) == RNode::SLOT_VALUE_EMPTY )
504  {
505  break;
506  }
507 
509  s_box[s],
510  shared_boxes,
511  shared_nodes,
512  shared_nodes + node->getSubtree(s),
513  item_box
514  );
515  }
516  }
517  else
518  {
519  int s = 0;
520  for( ; s < MAX_ORDER; ++s )
521  {
522  if( ( node->mySlots[ s ] & RNode::SLOT_MASK_INDEX ) == RNode::SLOT_VALUE_EMPTY )
523  {
524  break;
525  }
526 
527  s_box[s] = item_box[ node->getItemIndexRep( s ) ];
528  }
529 
530  for( ; s < MAX_ORDER; ++s )
531  {
532  s_box[s] = UT_BoxT< FT >(); // Empty set
533  }
534  }
535 
536  computeBoundingBox(bounding_box, s_box, s_box + MAX_ORDER);
537 }
538 
539 template< typename ITEM_INDEX, int MAX_ORDER >
541 {
543 
544  template< typename FT, typename QUERY_SHAPE, typename ACCEPT_ITEM >
545  constexpr void operator()(
546  ACCEPT_ITEM&& accept_item,
547  const RNodeT< ItemIndexRep, MAX_ORDER > shared_nodes[],
548  const UT_BoxT< FT > shared_boxes[],
549  const RNodeT< ItemIndexRep, MAX_ORDER >*const node,
550  const QUERY_SHAPE& query_shape
551  ) const noexcept
552  {
553  static_assert( SYS_IsIntegral_v< ItemIndexRep > );
554 
555  using RNode = RNodeT< ItemIndexRep, MAX_ORDER >;
556  using Box = UT_BoxT< FT >;
557 
558  UT_ASSERT( node != nullptr );
559 
560  // node_boxes is the sub-array that contains the MAX_ORDER boxes
561  // for the node that we're visiting
562  const Box*const node_boxes(
563  shared_boxes +
564  ((node - shared_nodes) * MAX_ORDER)
565  );
566 
567  if( node->isInternal() )
568  {
569  for( int s = 0; s < MAX_ORDER; ++s )
570  {
571  if( (node->mySlots[s] & RNode::SLOT_MASK_INDEX) == RNode::SLOT_VALUE_EMPTY )
572  {
573  break;
574  }
575 
576  if( intersects( query_shape, node_boxes[ s ] ) )
577  {
579  std::forward< ACCEPT_ITEM >( accept_item ),
580  shared_nodes, shared_boxes,
581  shared_nodes + node->getSubtree( s ),
582  query_shape
583  );
584  }
585  }
586  }
587  else
588  {
589  for( int s = 0; s < MAX_ORDER; ++s )
590  {
591  if( (node->mySlots[s] & RNode::SLOT_MASK_INDEX) == RNode::SLOT_VALUE_EMPTY )
592  {
593  break;
594  }
595 
596  if( intersects( query_shape, node_boxes[ s ] ) )
597  {
598  accept_item( ITEM_INDEX{ node->getItemIndexRep( s ) } );
599  }
600  }
601  }
602  }
603 };
604 
605 template< typename ITEM_INDEX_REP, int MAX_ORDER >
607  const RNodeT< ITEM_INDEX_REP, MAX_ORDER > shared_nodes[],
608  const RNodeT< ITEM_INDEX_REP, MAX_ORDER >*const node
609 )
610 {
611  static_assert( SYS_IsIntegral_v< ITEM_INDEX_REP > );
612 
614 
615  UT_ASSERT_P( node != 0 );
616 
617  if( node->isInternal() )
618  {
619  int max_depth_children(0);
620 
621  for( int s = 0; s < MAX_ORDER; ++s )
622  {
623  if( (node->mySlots[s] & RNode::SLOT_MASK_INDEX) == RNode::SLOT_VALUE_EMPTY )
624  {
625  break;
626  }
627 
628  max_depth_children = std::max(
629  max_depth_children,
630  UTsubtreeComputeMaxDepth(shared_nodes, shared_nodes + node->getSubtree(s))
631  );
632  }
633 
634  return 1 + max_depth_children;
635  }
636  else
637  {
638  return 0;
639  }
640 }
641 
642 }
643 // namespace UT
644 
645 template< typename FT >
647  const exint node_slot_box_size,
648  std::unique_ptr< UT_BoxT< FT >[] >&& node_slot_box
649 ) :
650  myNodeSlotBoxSize( node_slot_box_size ),
651  myNodeSlotBox( std::move( node_slot_box ) )
652 {
653 }
654 
655 template< typename FT >
657  myNodeSlotBoxSize( a.myNodeSlotBoxSize ),
658  myNodeSlotBox( std::move( a.myNodeSlotBox ) )
659 {
660 }
661 
662 template< typename ITEM_INDEX, int MAX_ORDER >
663 template< typename FT >
665  const UT_BoxT< FT > item_box[],
666  const ItemIndex num_items
667 ) :
668  myNumNodes( 0 ),
669  myNodes( nullptr ),
670  myRoot( nullptr ),
671  myNumItems( ItemIndexUnderlyingInteger< ITEM_INDEX >{}( num_items ) )
672 {
673  using ItemIndexRep = ItemIndex_UnderlyingIntegerType_t< ITEM_INDEX >;
676 
677  SYS_STATIC_ASSERT( MAX_ORDER >= 2 );
678 
679 
680  UT_ASSERT( myNumItems >= 0 );
681  UT_ASSERT( myNumItems < ( ItemIndexRep(1) << ( ( 8 * sizeof(ItemIndexRep) ) - 2 ) ) );
682 
683  std::unique_ptr< BoxedItem[] > boxed_items( std::make_unique< BoxedItem[] >( myNumItems ) );
684  ItemIndexRep num_boxed_items = 0;
685  for( ItemIndexRep i = 0; i < myNumItems; ++i )
686  {
687  const Box& box( item_box[ i ] );
688  if( box.isEmpty() )
689  {
690  continue;
691  }
692 
693  boxed_items[ num_boxed_items ] = BoxedItem( box, i );
694  num_boxed_items++;
695  }
696 
697  if( num_boxed_items <= 0 )
698  {
699  // Verify nonempty tree with invalid root
700  UT_ASSERT( myNumNodes == 0 );
701  UT_ASSERT( myNodes == nullptr );
702  UT_ASSERT( myRoot == nullptr );
703 
704  return;
705  }
706 
707  myNumNodes = subtreeDetermineNumNodes( MAX_ORDER, num_boxed_items );
708  myNodes = std::make_unique< Node[] >( myNumNodes );
709 
710  // Create the R-tree nodes, based on boxed_items
712  std::unique_ptr< Box[] > shared_boxes( std::make_unique< Box[] >( MAX_ORDER * myNumNodes ) );
713 
715 
717  bounding_box_root,
718  shared_boxes.get(),
719  boxed_items.get(), boxed_items.get() + num_boxed_items,
720  myNodes.get(),
722  );
723 
724  UT_ASSERT( shared_nodes_end - myNodes.get() == myNumNodes );
725 
726  // Verify nonempty tree with valid root
727  UT_ASSERT( myNumNodes > 0 );
728  UT_ASSERT( myNodes != nullptr );
729  UT_ASSERT( ( myNodes.get() <= myRoot ) && ( myRoot < myNodes.get() + myNumNodes ) );
730 
731 #if 0
732  std::cout << "RTree stats: " << std::endl;
733  std::cout << "Number of items: " << num_items << std::endl;
734  std::cout << "Tree size (in node): " << myNumNodes << std::endl;
735  std::cout << "MAX_ORDER (max children/items per node) = " << MAX_ORDER << std::endl;
736  std::cout << "Number of items per node: " << fpreal64(num_items) / fpreal64(myNumNodes) << std::endl;
737  std::cout << "Max tree depth: " << UTsubtreeComputeMaxDepth(myNodes, myRoot) << std::endl;
738 #endif // 0
739 }
740 
741 template< typename ITEM_INDEX, int MAX_ORDER >
742 template< typename FT >
744  const UT_Array< UT_BoxT< FT > >& item_box
745 ) :
746  // Delegate to constructor that takes built-in array with size
747  RTreeT( item_box.array(), item_box.size() )
748 {
749 }
750 
751 template< typename ITEM_INDEX, int MAX_ORDER >
754  myNodes( std::move( a.myNodes ) ),
755  myRoot( a.myRoot ),
756  myNumItems( a.myNumItems )
757 {
758  // Mark tree as invalid
759  a.myNumItems = -1;
760  a.myRoot = nullptr;
761  a.myNumNodes = -1;
762 }
763 
764 template< typename ITEM_INDEX, int MAX_ORDER >
766 {
767  // Mark tree as invalid
768  myNumItems = -1;
769  myRoot = nullptr;
770  myNumNodes = -1;
771 }
772 
773 template< typename ITEM_INDEX, int MAX_ORDER, typename FT >
774 inline UT::RTreeT< ITEM_INDEX, MAX_ORDER > UT::constructRTree( const UT_BoxT< FT > item_box[], const ITEM_INDEX num_items )
775 {
776  return RTreeT< ITEM_INDEX, MAX_ORDER >( item_box, num_items );
777 }
778 
779 template< typename ITEM_INDEX, int MAX_ORDER, typename FT >
781 {
782  return constructRTree< ITEM_INDEX, MAX_ORDER >( item_box.array(), item_box.size() );
783 }
784 
785 template< typename ITEM_INDEX, int MAX_ORDER, typename FT >
787 {
788  using Box = UT_BoxT< FT >;
789 
790  exint node_slot_box_size = -1;
791  std::unique_ptr< Box[] > node_slot_box;
792 
793  UT_ASSERT( tree.myNumNodes != -1 );
794  UT_ASSERT( ItemIndexUnderlyingInteger< ITEM_INDEX >{}( num_items ) == tree.myNumItems );
795 
796  if( tree.myRoot == nullptr )
797  {
798  UT_ASSERT( tree.myNumNodes == 0 );
799 
800  node_slot_box_size = 0;
801  node_slot_box.reset();
802 
804  node_slot_box_size,
805  std::move( node_slot_box )
806  );
807  }
808 
809  UT_ASSERT( tree.myNumNodes > 0 );
810 
811  node_slot_box_size = MAX_ORDER * tree.myNumNodes;
812  node_slot_box = std::make_unique< Box[] >( node_slot_box_size );
813 
814  UT_ASSERT( node_slot_box != nullptr );
815 
816  Box bounding_box_root; // empty
818  bounding_box_root,
819  node_slot_box.get(),
820  tree.myNodes.get(),
821  tree.myRoot,
822  item_box
823  );
824 
826  node_slot_box_size,
827  std::move( node_slot_box )
828  );
829 }
830 
831 template< typename ITEM_INDEX, int MAX_ORDER, typename FT >
833 {
834  return constructRTreeConfiguration( tree, item_box.array(), ITEM_INDEX( item_box.size() ) );
835 }
836 
837 template< typename FT >
839 {
840  using Box = UT_BoxT< FT >;
841 
842  return configuration.myNodeSlotBoxSize * sizeof(Box);
843 }
844 
845 template< typename ITEM_INDEX, int MAX_ORDER, typename FT >
847  RTreeConfigurationT< FT >& configuration,
849  const UT_BoxT< FT > item_box[],
850  const ITEM_INDEX num_items
851 )
852 {
853  using Box = UT_BoxT< FT >;
854 
855  UT_ASSERT( tree.myNumNodes != -1 );
856  UT_ASSERT( num_items == tree.myNumItems );
857 
858  if( tree.myRoot == nullptr )
859  {
860  UT_ASSERT( tree.myNumNodes == 0 );
861  UT_ASSERT( configuration.myNodeSlotBoxSize == 0 );
862  UT_ASSERT( configuration.myNodeSlotBox == nullptr );
863 
864  return;
865  }
866 
867  UT_ASSERT( tree.myNumNodes > 0 );
868  UT_ASSERT( configuration.myNodeSlotBoxSize = MAX_ORDER * tree.myNumNodes );
869  UT_ASSERT( configuration.myNodeSlotBox != nullptr );
870 
871  Box bounding_box_root; // empty
873  bounding_box_root,
874  configuration.myNodeSlotBox.get(),
875  tree.myNodes.get(),
876  tree.myRoot,
877  item_box
878  );
879 }
880 
881 template< typename ITEM_INDEX, int MAX_ORDER, typename FT >
883  RTreeConfigurationT< FT >& configuration,
885  const UT_Array< UT_BoxT< FT > >& item_box
886 )
887 {
888  updateConfiguration( configuration, tree, item_box.data(), ITEM_INDEX( item_box.size() ) );
889 }
890 
891 template< typename QUERY_SHAPE, typename ITEM_INDEX, int MAX_ORDER, typename FT >
893  UT_Array< ITEM_INDEX >& results,
895  const RTreeConfigurationT< FT >& configuration,
896  const QUERY_SHAPE& query_shape
897 )
898 {
899  results.clear();
900 
902  [ &results ]( const ITEM_INDEX i ) { results.append( i ); },
903  tree, configuration,
904  query_shape
905  );
906 }
907 
908 /// For each item i for which item_box[i] intersects query_box,
909 /// call accept_item( i ).
910 /// There must exist a free-standing 'intersects' function that takes a
911 /// QUERY_SHAPE and a UT_BoxT< FT >.
912 template< typename ITEM_INDEX, int MAX_ORDER, typename FT, typename QUERY_SHAPE, typename ACCEPT_ITEM >
914  ACCEPT_ITEM&& accept_item,
916  const RTreeConfigurationT< FT >& configuration,
917  const QUERY_SHAPE& query_shape
918 )
919 {
920  UT_ASSERT( tree.myNumNodes != -1 );
921 
922  UT_ASSERT( configuration.myNodeSlotBoxSize == MAX_ORDER * tree.myNumNodes );
923 
924  if( tree.myRoot == nullptr )
925  {
926  return;
927  }
928 
930  std::forward< ACCEPT_ITEM >( accept_item ),
931  tree.myNodes.get(),
932  configuration.myNodeSlotBox.get(),
933  tree.myRoot, query_shape
934  );
935 }
936 
937 template< typename ITEM_INDEX, int MAX_ORDER >
939 {
940  using ItemIndexRep = ItemIndex_UnderlyingIntegerType_t< ITEM_INDEX >;
941  using RNode = RNodeT< ItemIndexRep, MAX_ORDER >;
942 
943  return tree.myNumNodes * sizeof(RNode);
944 }
945 
946 template< typename QUERY_SHAPE, typename ITEM_INDEX, int MAX_ORDER, typename FT >
947 inline ITEM_INDEX* UT::getIntersectingRaw(
949  const RTreeConfigurationT< FT >& configuration,
950  const QUERY_SHAPE& query_box,
951  ITEM_INDEX*const items_begin
952 )
953 {
954  ITEM_INDEX* it = items_begin;
955 
957  [ &it ]( const ITEM_INDEX i ) { *it++ = i; },
958  tree, configuration,
959  query_box
960  );
961 
962  return it;
963 }
964 
965 template< typename FT >
967 {
968  return UT::constructRTree< UT_RTree16Int::ItemIndex, UT_RTree16Int::max_order, FT >( item_box );
969 }
970 
971 template< typename FT >
973 {
974  return UT::constructRTree< UT_RTree2Int::ItemIndex, UT_RTree2Int::max_order, FT >( item_box );
975 }
976 
977 template< typename FT >
978 inline UT_RTreeInt UTconstructRTreeInt( const UT_BoxT< FT > item_box[], const UT_RTreeInt::ItemIndex num_items )
979 {
980  return UT::constructRTree< UT_RTreeInt::ItemIndex, UT_RTreeInt::max_order, FT >( item_box, num_items );
981 }
982 
983 template< typename FT >
985 {
986  return UT::constructRTree< UT_RTreeInt::ItemIndex, UT_RTreeInt::max_order, FT >( item_box );
987 }
988 
989 template< typename FT >
990 inline UT_RTree UTconstructRTree( const UT_BoxT< FT > item_box[], const UT_RTree::ItemIndex num_items )
991 {
992  return UT::constructRTree< UT_RTree::ItemIndex, UT_RTree::max_order, FT >( item_box, num_items );
993 }
994 
995 template< typename FT >
996 inline UT_RTree UTconstructRTree( const UT_Array< UT_BoxT< FT > >& item_box )
997 {
998  return UT::constructRTree< UT_RTree::ItemIndex, UT_RTree::max_order, FT >( item_box );
999 }
1000 
1001 template< typename FT >
1003 {
1004  return UT::constructRTreeConfiguration< UT_RTree2Int::ItemIndex, UT_RTree2Int::max_order, FT >( tree, item_box );
1005 }
1006 
1007 template< typename FT >
1009 {
1010  return UT::constructRTreeConfiguration< UT_RTree16Int::ItemIndex, UT_RTree16Int::max_order, FT >( tree, item_box );
1011 }
1012 
1013 template< typename FT >
1015 {
1016  return UT::constructRTreeConfiguration< UT_RTreeInt::ItemIndex, UT_RTreeInt::max_order, FT >( tree, item_box );
1017 }
1018 
1019 template< typename FT >
1021 {
1022  return UT::constructRTreeConfiguration< UT_RTreeInt::ItemIndex, UT_RTreeInt::max_order, FT >( tree, item_box, num_items );
1023 }
1024 
1025 template< typename FT >
1027 {
1028  return UT::constructRTreeConfiguration< UT_RTree::ItemIndex, UT_RTree::max_order, FT >( tree, item_box );
1029 }
1030 
1031 template< typename FT >
1032 inline auto UTmakeUniqueRTree2Int( const UT_Array< UT_BoxT< FT > >& item_box )
1033 {
1034  return UTmakeUnique< const UT_RTree2Int >( UTconstructRTree2Int( item_box ) );
1035 }
1036 
1037 template< typename FT >
1038 inline auto UTmakeUniqueRTree16Int( const UT_Array< UT_BoxT< FT > >& item_box )
1039 {
1040  return UTmakeUnique< const UT_RTree16Int >( UTconstructRTree16Int( item_box ) );
1041 }
1042 
1043 template< typename FT >
1044 inline auto UTmakeUniqueRTreeInt( const UT_Array< UT_BoxT< FT > >& item_box )
1045 {
1046  return UTmakeUnique< const UT_RTreeInt >( UTconstructRTreeInt( item_box ) );
1047 }
1048 
1049 template< typename FT >
1050 inline auto UTmakeUniqueRTreeInt( const UT_BoxT< FT > item_box[], const UT_RTree::ItemIndex num_items )
1051 {
1052  return UTmakeUnique< const UT_RTreeInt >( UTconstructRTreeInt( item_box, num_items ) );
1053 }
1054 
1055 template< typename FT >
1056 inline auto UTmakeUniqueRTree2IntConfiguration( const UT_RTree2Int& tree, const UT_Array< UT_BoxT< FT > >& item_box )
1057 {
1058  return UTmakeUnique< const UT::RTreeConfigurationT< FT > >( UTconstructRTree2IntConfiguration( tree, item_box ) );
1059 }
1060 
1061 template< typename FT >
1062 inline auto UTmakeUniqueRTree16IntConfiguration( const UT_RTree16Int& tree, const UT_Array< UT_BoxT< FT > >& item_box )
1063 {
1064  return UTmakeUnique< const UT::RTreeConfigurationT< FT > >( UTconstructRTree16IntConfiguration( tree, item_box ) );
1065 }
1066 
1067 template< typename FT >
1068 inline auto UTmakeUniqueRTreeIntConfiguration( const UT_RTreeInt& tree, const UT_Array< UT_BoxT< FT > >& item_box )
1069 {
1070  return UTmakeUnique< const UT::RTreeConfigurationT< FT > >( UTconstructRTreeIntConfiguration( tree, item_box ) );
1071 }
1072 
1073 template< typename FT >
1074 auto UTmakeUniqueRTreeIntConfiguration( const UT_RTreeInt& tree, const UT_BoxT< FT > item_box[], const UT_RTree::ItemIndex num_items )
1075 {
1076  return UTmakeUnique< const UT::RTreeConfigurationT< FT > >( UTconstructRTreeIntConfiguration( tree, item_box, num_items ) );
1077 }
1078 
1079 #endif // __UT_RTREEIMPL_H_INCLUDED__
1080 
static const Slot SLOT_MASK_INDEX
Definition: UT_RTreeImpl.h:201
UT_RTree16IntConfigurationT< FT > UTconstructRTree16IntConfiguration(const UT_RTree16Int &tree, const UT_Array< UT_BoxT< FT > > &item_box)
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1222
std::make_unsigned_t< ITEM_INDEX_REP > Slot
Definition: UT_RTreeImpl.h:107
myNodes
Definition: UT_RTreeImpl.h:708
auto UTmakeUniqueRTree2Int(const UT_Array< UT_BoxT< FT > > &item_box)
void UTnth_element(IT start, IT nth, IT end, COMPARE isAbeforeB)
Definition: UT_Permute.h:75
void subtreeAssignItemBoxArray(UT_BoxT< FT > &bounding_box, UT_BoxT< FT > shared_boxes[], const RNodeT< ITEM_INDEX_REP, MAX_ORDER > shared_nodes[], const RNodeT< ITEM_INDEX_REP, MAX_ORDER > *const node, ITEM_BOX &&item_box)
Definition: UT_RTreeImpl.h:477
Definition: UT_BVH.h:37
void computeBoundingBoxItem(BOX &bounding_box, const UT_BoxedItemT< BOX, ITEM_INDEX_REP > *const begin, const UT_BoxedItemT< BOX, ITEM_INDEX_REP > *const end)
Definition: UT_RTreeImpl.h:80
Definition: Node.h:52
auto UTmakeUniqueRTree16Int(const UT_Array< UT_BoxT< FT > > &item_box)
IMATH_HOSTDEVICE IMATH_CONSTEXPR14 bool isEmpty() const IMATH_NOEXCEPT
Definition: ImathBox.h:292
auto UTmakeUniqueRTreeIntConfiguration(const UT_RTreeInt &tree, const UT_Array< UT_BoxT< FT > > &item_box)
int64 exint
Definition: SYS_Types.h:125
RNodeT< ITEM_INDEX_REP, MAX_ORDER > * subtreeCreate(BOX &bounding_box, BOX shared_boxes[], UT_BoxedItemT< BOX, ITEM_INDEX_REP > *const begin, UT_BoxedItemT< BOX, ITEM_INDEX_REP > *const end, RNodeT< ITEM_INDEX_REP, MAX_ORDER > shared_nodes[], RNodeT< ITEM_INDEX_REP, MAX_ORDER > *&shared_nodes_end)
Definition: UT_RTreeImpl.h:319
Node * shared_nodes_end
Definition: UT_RTreeImpl.h:714
UT_BoxedItemT(const Box &box, const ItemIndexRep item)
Definition: UT_RTreeImpl.h:35
std::unique_ptr< BoxedItem[] > boxed_items(std::make_unique< BoxedItem[] >(myNumItems))
exint heapMemoryUsage(const RTreeConfigurationT< FT > &configuration)
Definition: UT_RTreeImpl.h:838
Slot getSubtree(const int s) const
Definition: UT_RTreeImpl.h:163
constexpr void operator()(UT_BoxedItemT< BOX, ITEM_INDEX_REP > *const begin, UT_BoxedItemT< BOX, ITEM_INDEX_REP > *const end, IS_LESS_THAN &&is_less_than, const ITEM_INDEX_REP m, const int num_subtrees) const noexcept
Definition: UT_RTreeImpl.h:285
ITEM_INDEX_REP ItemIndexRep
Definition: UT_RTreeImpl.h:24
constexpr void operator()(ACCEPT_ITEM &&accept_item, const RNodeT< ItemIndexRep, MAX_ORDER > shared_nodes[], const UT_BoxT< FT > shared_boxes[], const RNodeT< ItemIndexRep, MAX_ORDER > *const node, const QUERY_SHAPE &query_shape) const noexcept
Definition: UT_RTreeImpl.h:545
GLsizeiptr size
Definition: glcorearb.h:664
double fpreal64
Definition: SYS_Types.h:201
ItemIndexRep myItem
Definition: UT_RTreeImpl.h:27
GLenum array
Definition: glew.h:9108
void assignSubtree(const int s, const Slot index_root_subtree)
Definition: UT_RTreeImpl.h:134
auto UTmakeUniqueRTreeInt(const UT_Array< UT_BoxT< FT > > &item_box)
UT_RTree2IntConfigurationT< FT > UTconstructRTree2IntConfiguration(const UT_RTree2Int &tree, const UT_Array< UT_BoxT< FT > > &item_box)
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:152
Slot mySlots[MAX_ORDER]
Definition: UT_RTreeImpl.h:220
UT_BoxedItemT< Box, ItemIndexRep > BoxedItem
Definition: UT_RTreeImpl.h:675
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
GLuint GLuint end
Definition: glcorearb.h:475
void assignItem(const int s, const ITEM_INDEX_REP item)
Definition: UT_RTreeImpl.h:145
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
RTreeConfigurationT< FT > constructRTreeConfiguration(const UT::RTreeT< ITEM_INDEX, MAX_ORDER > &tree, const UT_BoxT< FT > item_box[], const ITEM_INDEX num_items)
Box bounding_box_root
Definition: UT_RTreeImpl.h:711
SYS_FORCE_INLINE ITEM_INDEX_REP getItemIndexRep(const int s) const
Definition: UT_RTreeImpl.h:191
UT_RTreeIntConfigurationT< FT > UTconstructRTreeIntConfiguration(const UT_RTreeInt &tree, const UT_Array< UT_BoxT< FT > > &item_box)
auto UTmakeUniqueRTree2IntConfiguration(const UT_RTree2Int &tree, const UT_Array< UT_BoxT< FT > > &item_box)
UT_RTreeConfigurationT< FT > UTconstructRTreeConfiguration(const UT_RTree &tree, const UT_Array< UT_BoxT< FT > > &item_box)
void computeBoundingBox(BOX &bounding_box, const BOX *const begin, const BOX *const end)
Definition: UT_RTreeImpl.h:63
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
num_items
Definition: UT_RTreeImpl.h:672
UT_RTree UTconstructRTree(const UT_BoxT< FT > item_box[], const UT_RTree::ItemIndex num_items)
Definition: UT_RTreeImpl.h:990
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
exint append()
Definition: UT_Array.h:137
myNumNodes
Definition: UT_RTreeImpl.h:707
typename ItemIndex_UnderlyingIntegerType< ITEM_INDEX >::type ItemIndex_UnderlyingIntegerType_t
Definition: UT_RTree.h:118
static const Slot SLOT_FLAG_INTERNAL
Definition: UT_RTreeImpl.h:200
ItemIndex_UnderlyingIntegerType_t< ITEM_INDEX > ItemIndexRep
Definition: UT_RTreeImpl.h:542
void clear()
Definition: UT_RTreeImpl.h:118
SYS_STATIC_ASSERT(MAX_ORDER >=2)
UT_RTreeInt UTconstructRTreeInt(const UT_BoxT< FT > item_box[], const UT_RTreeInt::ItemIndex num_items)
Definition: UT_RTreeImpl.h:978
UT_RTree2Int UTconstructRTree2Int(const UT_Array< UT_BoxT< FT > > &item_box)
Definition: UT_RTreeImpl.h:972
GLsizei const GLint box[]
Definition: glew.h:11654
UT_BoxT< FT > Box
Definition: UT_RTreeImpl.h:674
exint subtreeComputeMaxDepth(const RNodeT< ITEM_INDEX_REP, MAX_ORDER > shared_nodes[], const RNodeT< ITEM_INDEX_REP, MAX_ORDER > *const node)
Definition: UT_RTreeImpl.h:606
ImageBuf OIIO_API max(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
const GLdouble * m
Definition: glew.h:9166
size_t subtreeDetermineNumNodes(const int MAX_ORDER, const size_t size)
Definition: UT_RTreeImpl.h:228
RTreeT()=delete
IMATH_HOSTDEVICE IMATH_CONSTEXPR14 bool intersects(const Box< Vec3< T >> &b, const Line3< T > &r, Vec3< T > &ip) IMATH_NOEXCEPT
Definition: ImathBoxAlgo.h:642
static const Slot SLOT_VALUE_EMPTY
Definition: UT_RTreeImpl.h:202
Definition: ImathBox.h:37
GLintptr offset
Definition: glcorearb.h:665
UT_ASSERT(myNumItems >=0)
void setInternal(const bool isInternal)
Definition: UT_RTreeImpl.h:127
void clear()
Resets list to an empty list.
Definition: UT_Array.h:679
ItemIndexRep num_boxed_items
Definition: UT_RTreeImpl.h:684
std::unique_ptr< Box[] > shared_boxes(std::make_unique< Box[] >(MAX_ORDER *myNumNodes))
bool isInternal() const
Definition: UT_RTreeImpl.h:155
auto UTmakeUniqueRTree16IntConfiguration(const UT_RTree16Int &tree, const UT_Array< UT_BoxT< FT > > &item_box)
GLdouble s
Definition: glew.h:1395
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
myRoot
Definition: UT_RTreeImpl.h:716
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
UT_RTree16Int UTconstructRTree16Int(const UT_Array< UT_BoxT< FT > > &item_box)
Definition: UT_RTreeImpl.h:966
ITEM_INDEX_REP countNumItems() const
Definition: UT_RTreeImpl.h:174
PcpNodeRef_ChildrenIterator begin(const PcpNodeRef::child_const_range &r)
Support for range-based for loops for PcpNodeRef children ranges.
Definition: node.h:450