HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
UT_RTree.C
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.C (UT library, C++)
7  *
8  * COMMENTS:
9  */
10 
11 #include "UT_RTree.h"
12 #include "UT_Assert.h"
13 #include <SYS/SYS_Math.h>
14 #include <SYS/SYS_StaticAssert.h>
15 #include <iostream>
16 #include <algorithm>
17 
18 template< typename T >
19 inline
21 {
22  myMin[0] = std::numeric_limits<T>::max();
23  myMin[1] = std::numeric_limits<T>::max();
24  myMin[2] = std::numeric_limits<T>::max();
25 
26  myMax[0] = -std::numeric_limits<T>::max();
27  myMax[1] = -std::numeric_limits<T>::max();
28  myMax[2] = -std::numeric_limits<T>::max();
29 }
30 
31 template< typename T >
32 template< typename U >
33 inline
34 UT_BoxT<T>::UT_BoxT(const U p[3])
35 {
36  myMin[0] = myMax[0] = p[0];
37  myMin[1] = myMax[1] = p[1];
38  myMin[2] = myMax[2] = p[2];
39 }
40 
41 template< typename T >
42 template< typename U >
43 inline
45 {
46  myMin[0] = myMax[0] = p.x();
47  myMin[1] = myMax[1] = p.y();
48  myMin[2] = myMax[2] = p.z();
49 }
50 
51 template< typename T >
52 inline
54 {
55  myMin[0] = bbox.xmin();
56  myMax[0] = bbox.xmax();
57  myMin[1] = bbox.ymin();
58  myMax[1] = bbox.ymax();
59  myMin[2] = bbox.zmin();
60  myMax[2] = bbox.zmax();
61 }
62 
63 template< typename T >
64 inline bool
66 {
67  return(
68  (myMin[0] > myMax[0]) ||
69  (myMin[1] > myMax[1]) ||
70  (myMin[2] > myMax[2])
71  );
72 }
73 
74 template< typename T >
75 inline T
76 UT_BoxT<T>::getMin(const int c) const
77 {
78  UT_ASSERT_P( (0 <= c) && (c < 3) );
79  UT_ASSERT_P( !isEmpty() );
80 
81  return myMin[c];
82 }
83 
84 template< typename T >
85 inline T
86 UT_BoxT<T>::getMax(const int c) const
87 {
88  UT_ASSERT_P( (0 <= c) && (c < 3) );
89  UT_ASSERT_P( !isEmpty() );
90 
91  return myMax[c];
92 }
93 
94 template< typename T >
95 template< typename U >
96 inline void
98 {
99  myMin[0] = p[0];
100  myMin[1] = p[1];
101  myMin[2] = p[2];
102 
103  myMax[0] = p[0];
104  myMax[1] = p[1];
105  myMax[2] = p[2];
106 }
107 
108 template< typename T >
109 template< typename U >
110 inline void
112 {
113  myMin[0] = (myMin[0] > p[0]) ? p[0] : myMin[0];
114  myMin[1] = (myMin[1] > p[1]) ? p[1] : myMin[1];
115  myMin[2] = (myMin[2] > p[2]) ? p[2] : myMin[2];
116 
117  myMax[0] = (myMax[0] < p[0]) ? p[0] : myMax[0];
118  myMax[1] = (myMax[1] < p[1]) ? p[1] : myMax[1];
119  myMax[2] = (myMax[2] < p[2]) ? p[2] : myMax[2];
120 }
121 
122 template< typename T >
123 inline void
125 {
126  myMin[0] = (myMin[0] > b.myMin[0]) ? b.myMin[0] : myMin[0];
127  myMin[1] = (myMin[1] > b.myMin[1]) ? b.myMin[1] : myMin[1];
128  myMin[2] = (myMin[2] > b.myMin[2]) ? b.myMin[2] : myMin[2];
129 
130  myMax[0] = (myMax[0] < b.myMax[0]) ? b.myMax[0] : myMax[0];
131  myMax[1] = (myMax[1] < b.myMax[1]) ? b.myMax[1] : myMax[1];
132  myMax[2] = (myMax[2] < b.myMax[2]) ? b.myMax[2] : myMax[2];
133 }
134 
135 template< typename T >
136 inline void
138 {
139  myMin[0] = (myMin[0] > b.xmin()) ? b.xmin() : myMin[0];
140  myMin[1] = (myMin[1] > b.ymin()) ? b.ymin() : myMin[1];
141  myMin[2] = (myMin[2] > b.zmin()) ? b.zmin() : myMin[2];
142 
143  myMax[0] = (myMax[0] < b.xmax()) ? b.xmax() : myMax[0];
144  myMax[1] = (myMax[1] < b.ymax()) ? b.ymax() : myMax[1];
145  myMax[2] = (myMax[2] < b.zmax()) ? b.zmax() : myMax[2];
146 }
147 
148 template< typename T >
149 inline void
151 {
152  if( isEmpty() )
153  return;
154 
155  myMin[0] -= l;
156  myMin[1] -= l;
157  myMin[2] -= l;
158 
159  myMax[0] += l;
160  myMax[1] += l;
161  myMax[2] += l;
162 }
163 
164 template< typename T >
165 inline void
166 UT_BoxT<T>::expandDistance(const T l, int axis)
167 {
168  if( isEmpty() )
169  return;
170 
171  myMin[axis] -= l;
172  myMax[axis] += l;
173 }
174 
175 template< typename T >
176 inline bool
177 UT_BoxT<T>::contains(const T*const p) const
178 {
179  return ( (myMin[0] <= p[0]) && (p[0] <= myMax[0]) &&
180  (myMin[1] <= p[1]) && (p[1] <= myMax[1]) &&
181  (myMin[2] <= p[2]) && (p[2] <= myMax[2]) );
182 }
183 
184 template< typename T >
185 inline bool
187 {
188  return (
189  (SYSmax(myMin[0], b.myMin[0]) <= SYSmin(myMax[0], b.myMax[0])) &&
190  (SYSmax(myMin[1], b.myMin[1]) <= SYSmin(myMax[1], b.myMax[1])) &&
191  (SYSmax(myMin[2], b.myMin[2]) <= SYSmin(myMax[2], b.myMax[2]))
192  );
193 }
194 
195 template< typename T >
196 inline int
198 {
199  if( isEmpty() )
200  return 0;
201 
202  int max_axis(0);
203  T max_length(myMax[0] - myMin[0]);
204 
205  T length(0);
206 
207  length = myMax[1] - myMin[1];
208  if( length > max_length )
209  {
210  max_length = length;
211  max_axis = 1;
212  }
213 
214  length = myMax[2] - myMin[2];
215  if( length > max_length )
216  {
217  max_length = length;
218  max_axis = 2;
219  }
220 
221  return max_axis;
222 }
223 
224 template< typename T >
225 inline std::ostream& operator<<(std::ostream& os, const UT_BoxT<T>& b)
226 {
227  os << "Box{ min = ";
228  os << b.getMin(0) << ", " << b.getMin(1) << ", " << b.getMin(2);
229  os << ", max = ";
230  os << b.getMax(0) << ", " << b.getMax(1) << ", " << b.getMax(2);
231  os << " }";
232  return os;
233 }
234 
235 template< typename T >
236 inline bool
238 {
239  // We calculate whether the box intersects the sphere by
240  // calculating the distance from the sphere center to the
241  // minimum / maximum axis coordinate (for each axis), squaring,
242  // and adding together to compare to the sphere radius
243  T min_distance = 0;
244  for( int axis = 0; axis < 3; axis++ )
245  {
246  if( myCentre[axis] < b.getMin(axis) )
247  {
248  T difference = myCentre[axis] - b.getMin(axis);
249  min_distance += difference * difference;
250  }
251  else if( myCentre[axis] > b.getMax(axis) )
252  {
253  T difference = myCentre[axis] - b.getMax(axis);
254  min_distance += difference * difference;
255  }
256  }
257  return min_distance <= myRadius*myRadius;
258 }
259 
260 template< typename T>
262 {
263  typedef UT_BoxT<T> Box;
264 
266  int myItem;
267 
269  myBox(),
270  myItem(-1)
271  {
272  }
273 };
274 
275 template< typename T >
276 inline std::ostream& operator<<(std::ostream& os, const UT_BoxedItemT<T>& bf)
277 {
278  os << "BoxedItem{ ";
279  os << "box = ";
280  os << bf.myBox << ", ";
281  os << "item = ";
282  os << bf.myItem;
283  os << " }";
284  return os;
285 }
286 
287 // Compute the bounding box for a range of boxes [begin, end)
288 template< typename T>
289 inline void
291  UT_BoxT<T>& bounding_box,
292  const UT_BoxT<T>*const begin, const UT_BoxT<T>*const end
293 )
294 {
295  UT_ASSERT( end != begin );
296 
297  bounding_box = *begin;
298 
299  for( const UT_BoxT<T>* i = begin + 1; i != end; ++i )
300  {
301  bounding_box.absorbBox(*i);
302  }
303 }
304 
305 // Compute the bounding box for all the boxes in
306 // a range of boxed items [begin, end)
307 template< typename T >
308 inline void
310  UT_BoxT<T>& bounding_box,
311  const UT_BoxedItemT<T>*const begin, const UT_BoxedItemT<T>*const end
312 )
313 {
314  UT_ASSERT( end != begin );
315 
316  bounding_box = begin->myBox;
317 
318  for( const UT_BoxedItemT<T>* i = begin + 1; i != end; ++i )
319  {
320  bounding_box.absorbBox(i->myBox);
321  }
322 }
323 
324 // Sort boxed items in the direction of an axis, by their centers
325 template< typename T >
327 {
328  int myAxis;
329 
330  explicit UT_BoxedItemAxisOrderT(const int axis) :
331  myAxis(axis)
332  {
333  }
334 
336  {
337  }
338 
340  {
341  T amid = a.myBox.getMin(myAxis) + a.myBox.getMax(myAxis);
342  T bmid = b.myBox.getMin(myAxis) + b.myBox.getMax(myAxis);
343 
344  return amid < bmid;
345  }
346 };
347 
348 template< int MAX_ORDER >
349 class UT_RNode
350 {
351 public:
352  typedef uint32 Index;
353 
355  {
356  clear();
357  }
358 
360  {
361  }
362 
363  void clear()
364  {
365  setInternal(false);
366  for( int s = 0; s < MAX_ORDER; ++s )
367  {
369  }
370  }
371 
372  void setInternal(const bool isInternal)
373  {
374  mySlots[0] = ( (mySlots[0] & SLOT_MASK_INDEX) |
375  (isInternal ? SLOT_FLAG_INTERNAL : 0) );
376  }
377 
378  // Assuming this is an internal node, assign a node index to slot s
379  void assignSubtree(const int s, const int index_root_subtree)
380  {
381  UT_ASSERT( isInternal() );
382  UT_ASSERT( (0 <= s) && (s < MAX_ORDER) );
383  UT_ASSERT( 0 <= index_root_subtree );
384  UT_ASSERT(
385  (static_cast<uint32>(index_root_subtree) & SLOT_MASK_INDEX) ==
386  static_cast<uint32>(index_root_subtree)
387  );
388 
389  mySlots[s] = index_root_subtree | SLOT_FLAG_INTERNAL;
390  }
391 
392  // Assign an item to slot s
393  void assignItem(const int s, const int item)
394  {
395  UT_ASSERT( !isInternal() );
396  UT_ASSERT( (0 <= s) && (s < MAX_ORDER) );
397  UT_ASSERT( 0 <= item );
398  UT_ASSERT(
399  (static_cast<uint32>(item) & SLOT_MASK_INDEX) ==
400  static_cast<uint32>(item)
401  );
402 
403  mySlots[s] = item;
404  }
405 
406  bool isInternal() const
407  {
408  return ((mySlots[0] & SLOT_FLAG_INTERNAL) != 0);
409  }
410 
411  // Get node stored in slot.
412  // This assumes that the last assignment to this slot was an node!
413  // (not an item)
414  int getSubtree(const int s) const
415  {
416  UT_ASSERT_P( isInternal() );
417  UT_ASSERT_P( (0 <= s) && (s < MAX_ORDER) );
419 
420  return (mySlots[s] & SLOT_MASK_INDEX);
421  }
422 
423  // For internal nodes, count the number of children
424  // For leaf nodes, count the number of items
425  int countNumItems() const
426  {
427  int num_items(0);
428  for( int s = 0; s < MAX_ORDER; ++s )
429  {
431  break;
432 
433  ++num_items;
434  }
435 
436  return num_items;
437  }
438 
439  // Get item stored in slot.
440  // This assumes that the last assignment to this slot was an item!
441  // (not a node)
442  int getItem(const int s) const
443  {
444  UT_ASSERT_P( !isInternal() );
445  UT_ASSERT_P( (0 <= s) && (s < MAX_ORDER) );
447 
448  return (mySlots[s] & SLOT_MASK_INDEX);
449  }
450 
451  typedef Index Slot;
452  static const Slot SLOT_FLAG_INTERNAL = 0x80000000;
453  static const Slot SLOT_MASK_INDEX = 0x7fffffff;
455 
456  //
457  // mySlots[0] has a bit that defines whether the node is an internal
458  // node. This is the SLOT_FLAG_INTERNAL bit.
459  // In an internal node, each non-empty slot has the index of a child
460  // node.
461  // In a leaf node, each non-empty slot has the index of an item.
462  //
463  // A node (internal or leaf) may not always be full
464  // (fewer than MAX_ORDER children for internal node case, or fewer than
465  // MAX_ORDER items for leaf case).
466  // When the node is not full, then the empty slots form
467  // a contiguous range after all the nonempty slots.
468  // The full range consists of the slots s in the half-open range
469  // [ 0, getNumItems() )
470  //
471 
472  Slot mySlots[MAX_ORDER];
473 };
474 
475 // Determine the exact number of nodes needed to store an R-tree of MAX_ORDER
476 // with "size" elements. The O(log n) cost of this calculation is insignificant compared to
477 // the time it takes to construct the tree.
478 inline size_t
480  const int MAX_ORDER,
481  const size_t size
482 )
483 {
484  int num_nodes(0);
485 
486  if( size > MAX_ORDER )
487  {
488  // Internal node
489 
490  ++num_nodes;
491 
492  size_t m(MAX_ORDER);
493  while( m * MAX_ORDER < size )
494  m *= MAX_ORDER;
495 
496  UT_ASSERT( MAX_ORDER <= m );
497  UT_ASSERT( m < size );
498 
499  // Count number of nodes for the at most MAX_ORDER subtrees that
500  // have exactly m elements
501 
502  const int num_subtrees_size_m( size / m );
503 
504  UT_ASSERT( num_subtrees_size_m <= MAX_ORDER );
505 
506  const size_t num_nodes_for_m( subtreeDetermineNumNodes(MAX_ORDER, m) );
507 
508  num_nodes += num_subtrees_size_m * num_nodes_for_m;
509 
510  // Count number of nodes for the subtree with the less than m
511  // remaining elements (if this exists)
512 
513  const size_t num_remaining_items( size % m );
514  if( num_remaining_items > 0 )
515  {
516  num_nodes += subtreeDetermineNumNodes(MAX_ORDER, num_remaining_items);
517  }
518  }
519  else
520  {
521  // Leaf node
522 
523  ++num_nodes;
524  }
525 
526  return num_nodes;
527 }
528 
529 /// Partition the range of boxed items [begin, end) according to the given
530 /// comparison function such that all items in the range [0, m-1] are less than
531 /// or equal to all items in [m, 2m-1], which are less than or equal to all
532 /// items in [2m, 3m-1], etc, where m is the subtree size.
533 template< typename T >
534 inline void
536  UT_BoxedItemT<T>*const begin, UT_BoxedItemT<T>*const end,
537  const UT_BoxedItemAxisOrderT<T> &order,
538  int subtree_size, int num_subtrees
539 )
540 {
541  if (num_subtrees <= 1)
542  return;
543 
544  // Choose a multiple of the subtree size that's close to the middle, and
545  // partition so that all items in [begin, begin + i) are less than or equal
546  // to all items in [begin + i, end).
547  const int mid = num_subtrees / 2;
548  const int i = mid * subtree_size;
549  UTnth_element(begin, begin + i, end, order);
550 
551  // Recursively partition each side.
552  partitionForSubtrees(begin, begin + i, order, subtree_size, mid);
553  partitionForSubtrees(begin + i, end, order, subtree_size,
554  num_subtrees - mid);
555 }
556 
557 // Create a subtree for the range of boxed items [begin, end).
558 // Return a pointer to the subtree root (this points into in shared_nodes)
559 // In addition, bounding_box will be a bounding box for the subtree.
560 template< int MAX_ORDER, typename T >
561 inline UT_RNode<MAX_ORDER>*
563  UT_BoxT<T>& bounding_box,
564  UT_BoxT<T> shared_boxes[],
565  UT_BoxedItemT<T>*const begin, UT_BoxedItemT<T>*const end,
566  UT_RNode<MAX_ORDER>*const shared_nodes,
567  UT_RNode<MAX_ORDER>*& shared_nodes_end
568 )
569 {
570  SYS_STATIC_ASSERT( MAX_ORDER >= 2 );
571 
572  UT_RNode<MAX_ORDER>* node(shared_nodes_end++);
573  node->clear();
574 
575  // node_boxes is the sub-array that contains the at most MAX_ORDER boxes
576  // for the node that we're building
577  UT_BoxT<T>*const node_boxes(
578  shared_boxes +
579  ((node - shared_nodes) * MAX_ORDER)
580  );
581 
582  const size_t size(end - begin);
583 
584  UT_ASSERT( size > 0 );
585 
586  computeBoundingBox(bounding_box, begin, end);
587 
588  if( size > MAX_ORDER )
589  {
590  // Create an internal node at most MAX_ORDER nonempty slots.
591  // slot s will have the index of the root of a subtree,
592  // which is contained in node_boxes[s]
593 
594  node->setInternal(true);
595 
596  // Partition in a way that is balanced but that aims
597  // to keep the number of unused slots in leaves very small
598  // Pick "m" to be the ideal number of items per subtree.
599  size_t m(MAX_ORDER);
600  while( m * MAX_ORDER < size )
601  m *= MAX_ORDER;
602 
603  UT_ASSERT( MAX_ORDER <= m );
604  UT_ASSERT( m < size );
605 
606  size_t offset(0);
607 
608  // Create at most MAX_ORDER subtrees, each of which has exactly m elements
609  const int num_subtrees_size_m( size / m );
610 
611  UT_ASSERT( num_subtrees_size_m <= MAX_ORDER );
612 
613  // TODO: perhaps splitting along a single axis is not the best
614  UT_BoxedItemAxisOrderT<T> order(bounding_box.getLargestAxis());
615  // Partition the elements for each subtree.
616  partitionForSubtrees(begin, end, order, m, num_subtrees_size_m);
617 
618  for( int s = 0; s < num_subtrees_size_m; ++s )
619  {
620  if( size - offset < m )
621  break;
622 
623  const size_t next_offset( offset + m );
624 
625  node->assignSubtree(
626  s,
628  node_boxes[s],
629  shared_boxes,
630  begin + offset, begin + next_offset,
631  shared_nodes,
632  shared_nodes_end
633  ) - shared_nodes //FIXME: ugly pointer arithmetic
634  );
635 
636  offset = next_offset;
637  }
638 
639  // If needed, create a subtree for any remaining elements (strictly less than m)
640  const size_t num_remaining_items( size % m );
641  if( num_remaining_items > 0 )
642  {
643  UT_ASSERT( num_subtrees_size_m < MAX_ORDER );
644  UT_ASSERT( num_remaining_items == size - offset );
645 
646  const size_t next_offset( offset + num_remaining_items );
647 
648  node->assignSubtree(
649  num_subtrees_size_m,
651  node_boxes[num_subtrees_size_m],
652  shared_boxes,
653  begin + offset, begin + next_offset,
654  shared_nodes,
655  shared_nodes_end
656  ) - shared_nodes //FIXME: ugly pointer arithmetic
657  );
658 
659  offset = next_offset;
660  }
661 
662  UT_ASSERT( offset == size );
663 
664  UT_ASSERT( node->countNumItems() > 0 );
665  }
666  else
667  {
668  // Create a leaf with size nonempty slots.
669  // Each slot has the index of a shared node box.
670  node->setInternal(false);
671 
672  int s(0);
673  for( const UT_BoxedItemT<T>* i = begin; i != end; ++i )
674  {
675  node_boxes[s] = i->myBox;
676  node->assignItem(s, i->myItem);
677  ++s;
678  }
679  }
680 
681  return node;
682 }
683 
684 template< int MAX_ORDER >
685 inline int
687 {
688  return myNumItems;
689 }
690 
691 template< int MAX_ORDER, typename T >
692 inline void
694  UT_BoxT<T>& bounding_box,
695  UT_BoxT<T>*const shared_boxes,
696  const UT_RNode<MAX_ORDER>*const shared_nodes,
697  const UT_RNode<MAX_ORDER>*const node,
698  const UT_BoxT<T> item_boxes[]
699 )
700 {
701  using RNode = UT_RNode<MAX_ORDER>;
702 
703  UT_ASSERT( node != 0 );
704 
705  // node_boxes is the sub-array that contains the MAX_ORDER boxes
706  // for the node that we're visiting
707  UT_BoxT<T>*const node_boxes(
708  shared_boxes +
709  ((node - shared_nodes) * MAX_ORDER)
710  );
711 
712  if( node->isInternal() )
713  {
714  for( int s = 0; s < MAX_ORDER; ++s )
715  {
716  if( (node->mySlots[s] & RNode::SLOT_MASK_INDEX) == RNode::SLOT_VALUE_EMPTY )
717  break;
718 
720  node_boxes[s],
721  shared_boxes,
722  shared_nodes,
723  shared_nodes + node->getSubtree(s),
724  item_boxes
725  );
726  }
727  }
728  else
729  {
730  int s = 0;
731  for( ; s < MAX_ORDER; ++s )
732  {
733  if( (node->mySlots[s] & RNode::SLOT_MASK_INDEX) == RNode::SLOT_VALUE_EMPTY )
734  break;
735 
736  node_boxes[s] = item_boxes[node->getItem(s)];
737  }
738  for( ; s < MAX_ORDER; ++s )
739  {
740  node_boxes[s] = UT_BoxT<T>(); // Empty set
741  }
742  }
743 
744  computeBoundingBox(bounding_box, node_boxes, node_boxes + MAX_ORDER);
745 }
746 
747 template< typename QUERY_SHAPE, typename RESULT_ACCEPTOR, int MAX_ORDER, typename T >
748 inline void
750  RESULT_ACCEPTOR& acceptor,
751  const UT_RNode<MAX_ORDER>*const shared_nodes,
752  const UT_BoxT<T>*const shared_boxes,
753  const UT_RNode<MAX_ORDER>*const node,
754  const QUERY_SHAPE& query_box
755 )
756 {
757  using RNode = UT_RNode<MAX_ORDER>;
758 
759  UT_ASSERT( node != 0 );
760 
761  // node_boxes is the sub-array that contains the MAX_ORDER boxes
762  // for the node that we're visiting
763  const UT_BoxT<T>*const node_boxes(
764  shared_boxes +
765  ((node - shared_nodes) * MAX_ORDER)
766  );
767 
768  if( node->isInternal() )
769  {
770  for( int s = 0; s < MAX_ORDER; ++s )
771  {
772  if( (node->mySlots[s] & RNode::SLOT_MASK_INDEX) == RNode::SLOT_VALUE_EMPTY )
773  break;
774 
775  if( query_box.intersects(node_boxes[s]) )
776  {
778  acceptor,
779  shared_nodes, shared_boxes,
780  shared_nodes + node->getSubtree(s),
781  query_box
782  );
783  }
784  }
785  }
786  else
787  {
788  for( int s = 0; s < MAX_ORDER; ++s )
789  {
790  if( (node->mySlots[s] & RNode::SLOT_MASK_INDEX) == RNode::SLOT_VALUE_EMPTY )
791  break;
792 
793  if( query_box.intersects(node_boxes[s]) )
794  {
795  acceptor(node->getItem(s));
796  }
797  }
798  }
799 }
800 
801 template< int MAX_ORDER >
802 inline int
804  const UT_RNode<MAX_ORDER> shared_nodes[],
805  const UT_RNode<MAX_ORDER>*const node
806 )
807 {
808  using RNode = UT_RNode<MAX_ORDER>;
809 
810  UT_ASSERT( node != 0 );
811 
812  if( node->isInternal() )
813  {
814  int max_depth_children(0);
815 
816 
817  for( int s = 0; s < MAX_ORDER; ++s )
818  {
819  if( (node->mySlots[s] & RNode::SLOT_MASK_INDEX) == RNode::SLOT_VALUE_EMPTY )
820  break;
821 
822  max_depth_children = std::max(
823  max_depth_children,
824  UTsubtreeComputeMaxDepth(shared_nodes, shared_nodes + node->getSubtree(s))
825  );
826  }
827 
828  return 1 + max_depth_children;
829  }
830  else
831  {
832  return 0;
833  }
834 }
835 
836 
837 template< int MAX_ORDER >
838 template< typename T >
840  const UT_BoxT<T> item_boxes[], const int size
841 ) :
842  mySharedNodesSize(0),
843  mySharedNodes(0),
844  myRoot(0),
845  myNumItems(size)
846 {
847  SYS_STATIC_ASSERT( MAX_ORDER >= 2 );
848 
849  UT_ASSERT( size >= 0 );
850 
851  if( size <= 0 )
852  return;
853 
854  mySharedNodesSize = subtreeDetermineNumNodes(MAX_ORDER, size);
855  mySharedNodes = new UT_RNode<MAX_ORDER>[mySharedNodesSize];
856 
857  UT_RNode<MAX_ORDER>* shared_nodes_end(mySharedNodes);
858 
859  // Put item #i in box[i], resulting in boxes_items
860  std::vector< UT_BoxedItemT<T> > boxed_items;
861  boxed_items.resize(size);
862  for( int i = 0; i < size; ++i )
863  {
864  boxed_items[i].myBox = item_boxes[i];
865  boxed_items[i].myItem = i;
866  }
867 
868  // Create the R-tree nodes, based on boxed_items
869  UT_BoxT<T> bounding_box_root;
870  std::vector< UT_BoxT<T> > shared_boxes( MAX_ORDER * mySharedNodesSize );
871  myRoot = subtreeCreate(
872  bounding_box_root,
873  &(shared_boxes[0]),
874  &(boxed_items[0]), &(boxed_items[0]) + boxed_items.size(),
875  mySharedNodes,
876  shared_nodes_end
877  );
878 
879  UT_ASSERT( shared_nodes_end - mySharedNodes == mySharedNodesSize );
880 
881 #if 0
882  std::cout << "RTree stats: " << std::endl;
883  std::cout << "Number of items: " << size << std::endl;
884  std::cout << "Tree size (in node): " << mySharedNodesSize << std::endl;
885  std::cout << "MAX_ORDER (max children/items per node) = " << MAX_ORDER << std::endl;
886  std::cout << "Number of items per node: " << fpreal64(size) / fpreal64(mySharedNodesSize) << std::endl;
887  std::cout << "Max tree depth: " << UTsubtreeComputeMaxDepth(mySharedNodes, myRoot) << std::endl;
888 #endif // 0
889 }
890 
891 template< int MAX_ORDER >
893 {
894  delete[] mySharedNodes;
895  mySharedNodes = 0;
896 }
897 
898 template< int MAX_ORDER >
899 template< typename T>
900 inline void
902  UT_RTreeBoxAssignmentT<T>& assignment,
903  const UT_BoxT<T> item_boxes[]
904 ) const
905 {
906  if( myRoot == 0 )
907  return;
908 
909  assignment.myBoxesForSharedNodes.reserve(
910  MAX_ORDER * mySharedNodesSize
911  );
912 
913  // Allocate room for MAX_ORDER boxes for each shared node
914  // Box c of node n is stored in slot (MAX_ORDER * n) + c
915  assignment.myBoxesForSharedNodes.resize(
916  MAX_ORDER * mySharedNodesSize
917  );
918 
919  UT_BoxT<T> bounding_box_root;
921  bounding_box_root,
922  &(assignment.myBoxesForSharedNodes[0]),
923  mySharedNodes,
924  myRoot,
925  item_boxes
926  );
927 
928 #if 0
929  std::cout << "reserved: " << MAX_ORDER * mySharedNodesSize << std::endl;
930  std::cout << "capacity: " << assignment.myBoxesForSharedNodes.capacity() << std::endl;
931 #endif // 0
932 }
933 
934 template< int MAX_ORDER >
935 template< typename QUERY_SHAPE, typename RESULT_ACCEPTOR, typename T >
936 void
938  RESULT_ACCEPTOR& result_acceptor,
939  const QUERY_SHAPE& query_box,
940  const UT_RTreeBoxAssignmentT<T>& assignment
941 ) const
942 {
943  if( myRoot == 0 )
944  return;
945 
947  result_acceptor,
948  mySharedNodes,
949  &(assignment.myBoxesForSharedNodes[0]),
950  myRoot, query_box
951  );
952 }
953 
955 {
956 public:
958  : myResults(results)
959  , myBaseIndex(baseindex)
960  {
961  }
962 
963  inline void operator()(const int i)
964  {
965  myResults.append(i + myBaseIndex);
966  }
967 
968 private:
969  UT_IntArray& myResults;
970  exint myBaseIndex;
971 
972  // Disallow
977  );
978 };
979 
980 template< typename QUERY_SHAPE, int MAX_ORDER, typename T >
982  UT_IntArray& results,
983  const UT_RTreeGeneric<MAX_ORDER>& tree,
984  const QUERY_SHAPE& query_box,
985  const UT_RTreeBoxAssignmentT<T>& assignment
986 )
987 {
988  results.clear();
989  UT_RTreeResultAppenderIntArray appender(results, 0);
990  tree.getIntersectingItems(appender, query_box, assignment);
991 }
992 
993 template< typename QUERY_SHAPE, int MAX_ORDER, typename T >
995  UT_IntArray& results,
996  const UT_RTreeGeneric<MAX_ORDER>& tree,
997  const QUERY_SHAPE& query_box,
998  const UT_RTreeBoxAssignmentT<T>& assignment,
999  exint baseindex
1000 )
1001 {
1002  UT_RTreeResultAppenderIntArray appender(results, baseindex);
1003  tree.getIntersectingItems(appender, query_box, assignment);
1004 }
1005 
1007 {
1008 public:
1010  myIt(it)
1011  {
1012  }
1013 
1014  inline void operator()(const int i)
1015  {
1016  *myIt++ = i;
1017  }
1018 
1019  int* getIterator() const
1020  {
1021  return myIt;
1022  }
1023 
1024 private:
1025  int* myIt;
1026 
1027  // Disallow
1032  );
1033 };
1034 
1035 template< typename QUERY_SHAPE, int MAX_ORDER, typename T >
1037  const UT_RTreeGeneric<MAX_ORDER>& tree,
1038  const QUERY_SHAPE& query_box,
1039  const UT_RTreeBoxAssignmentT<T>& assignment,
1040  int*const items_begin
1041 )
1042 {
1043  UT_RTreeResultAcceptorRawIntIterator acceptor(items_begin);
1044 
1045  tree.getIntersectingItems(acceptor, query_box, assignment);
1046 
1047  return acceptor.getIterator();
1048 }
1049 
1050 
1051 template< int MAX_ORDER >
1052 template< typename T >
1054  const UT_RTreeBoxAssignmentT<T>& assignment) const
1055 {
1056  using RNode = UT_RNode<MAX_ORDER>;
1057 
1058  UT_BoxT<T> box;
1059 
1060  if ( myRoot == 0 )
1061  return box;
1062 
1063  const UT_BoxT<T>*const root_boxes =
1064  assignment.myBoxesForSharedNodes.data() + (myRoot - mySharedNodes)*MAX_ORDER;
1065 
1066  for( int s = 0; s < MAX_ORDER; ++s )
1067  {
1068  if( (myRoot->mySlots[s] & RNode::SLOT_MASK_INDEX) == RNode::SLOT_VALUE_EMPTY )
1069  break;
1070 
1071  box.absorbBox( root_boxes[s] );
1072  }
1073 
1074  return box;
1075 }
#define SYSmax(a, b)
Definition: SYS_Math.h:1365
void partitionForSubtrees(UT_BoxedItemT< T > *const begin, UT_BoxedItemT< T > *const end, const UT_BoxedItemAxisOrderT< T > &order, int subtree_size, int num_subtrees)
Definition: UT_RTree.C:535
T getMin(const int c) const
Definition: UT_RTree.C:76
UT_BoxT< T > Box
Definition: UT_RTree.C:263
#define SYS_STATIC_ASSERT(expr)
void UTnth_element(IT start, IT nth, IT end, COMPARE isAbeforeB)
Definition: UT_Permute.h:75
void expandDistance(const T l)
Definition: UT_RTree.C:150
static const Slot SLOT_FLAG_INTERNAL
Definition: UT_RTree.C:452
int UTsubtreeComputeMaxDepth(const UT_RNode< MAX_ORDER > shared_nodes[], const UT_RNode< MAX_ORDER > *const node)
Definition: UT_RTree.C:803
UT_BoxT< T > boundingBox(const UT_RTreeBoxAssignmentT< T > &assignment) const
Definition: UT_RTree.C:1053
void setInternal(const bool isInternal)
Definition: UT_RTree.C:372
static const Slot SLOT_MASK_INDEX
Definition: UT_RTree.C:453
void assignPoint(const U p[3])
Definition: UT_RTree.C:97
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
bool isEmpty() const
Definition: UT_RTree.C:65
uint32 Index
Definition: UT_RTree.C:352
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
SYS_FORCE_INLINE T & x(void)
Definition: UT_Vector3.h:581
3D Vector class.
void assignSubtree(const int s, const int index_root_subtree)
Definition: UT_RTree.C:379
png_uint_32 i
Definition: png.h:2877
bool intersects(const UT_BoxT< T > &b) const
Definition: UT_RTree.C:186
GLsizeiptr size
Definition: glcorearb.h:663
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:101
void getIntersectingItems(RESULT_ACCEPTOR &result_acceptor, const QUERY_SHAPE &query_box, const UT_RTreeBoxAssignmentT< T > &assignment) const
Definition: UT_RTree.C:937
const hboost::disable_if_c< VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:132
SYS_FORCE_INLINE T & z(void)
Definition: UT_Vector3.h:585
Slot mySlots[MAX_ORDER]
Definition: UT_RTree.C:472
void absorbPoint(const U p[3])
Definition: UT_RTree.C:111
UT_BoxedItemAxisOrderT(const int axis)
Definition: UT_RTree.C:330
void computeBoundingBox(UT_BoxT< T > &bounding_box, const UT_BoxT< T > *const begin, const UT_BoxT< T > *const end)
Definition: UT_RTree.C:290
bool operator()(const UT_BoxedItemT< T > &a, const UT_BoxedItemT< T > &b)
Definition: UT_RTree.C:339
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
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:102
bool contains(const T *const p) const
Definition: UT_RTree.C:177
UT_BoxT()
Definition: UT_RTree.C:20
int64 exint
Definition: SYS_Types.h:115
double fpreal64
Definition: SYS_Types.h:191
GLuint GLuint end
Definition: glcorearb.h:474
GLintptr offset
Definition: glcorearb.h:664
void createBoxAssignment(UT_RTreeBoxAssignmentT< T > &assignment, const UT_BoxT< T > item_boxes[]) const
Definition: UT_RTree.C:901
void operator()(const int i)
Definition: UT_RTree.C:963
void assignItem(const int s, const int item)
Definition: UT_RTree.C:393
int getNumItems() const
Definition: UT_RTree.C:686
~UT_RNode()
Definition: UT_RTree.C:359
int getSubtree(const int s) const
Definition: UT_RTree.C:414
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
size_t subtreeDetermineNumNodes(const int MAX_ORDER, const size_t size)
Definition: UT_RTree.C:479
UT_RTreeResultAppenderIntArray(UT_IntArray &results, exint baseindex)
Definition: UT_RTree.C:957
SYS_FORCE_INLINE T & y(void)
Definition: UT_Vector3.h:583
int countNumItems() const
Definition: UT_RTree.C:425
void absorbBox(const UT_BoxT< T > &b)
Definition: UT_RTree.C:124
int getLargestAxis() const
Definition: UT_RTree.C:197
bool isInternal() const
Definition: UT_RTree.C:406
static const Slot SLOT_VALUE_EMPTY
Definition: UT_RTree.C:454
UT_RNode< MAX_ORDER > * subtreeCreate(UT_BoxT< T > &bounding_box, UT_BoxT< T > shared_boxes[], UT_BoxedItemT< T > *const begin, UT_BoxedItemT< T > *const end, UT_RNode< MAX_ORDER > *const shared_nodes, UT_RNode< MAX_ORDER > *&shared_nodes_end)
Definition: UT_RTree.C:562
exint append(void)
Definition: UT_Array.h:95
bool intersects(const UT_BoxT< T > &b) const
Definition: UT_RTree.C:237
T getMax(const int c) const
Definition: UT_RTree.C:86
void clear()
Definition: UT_RTree.C:363
void subtreeGetIntersectingItems(RESULT_ACCEPTOR &acceptor, const UT_RNode< MAX_ORDER > *const shared_nodes, const UT_BoxT< T > *const shared_boxes, const UT_RNode< MAX_ORDER > *const node, const QUERY_SHAPE &query_box)
Definition: UT_RTree.C:749
UT_RNode()
Definition: UT_RTree.C:354
void clear()
Resets list to an empty list.
Definition: UT_Array.h:506
int getItem(const int s) const
Definition: UT_RTree.C:442
void subtreeCreateBoxAssignment(UT_BoxT< T > &bounding_box, UT_BoxT< T > *const shared_boxes, const UT_RNode< MAX_ORDER > *const shared_nodes, const UT_RNode< MAX_ORDER > *const node, const UT_BoxT< T > item_boxes[])
Definition: UT_RTree.C:693
#define SYSmin(a, b)
Definition: SYS_Math.h:1366
Index Slot
Definition: UT_RTree.C:451
GLuint GLsizei GLsizei * length
Definition: glcorearb.h:794
unsigned int uint32
Definition: SYS_Types.h:35