HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups 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 #include <VM/VM_SIMD.h>
18 
19 template< typename T >
20 inline
22 {
23  myMin[0] = std::numeric_limits<T>::max();
24  myMin[1] = std::numeric_limits<T>::max();
25  myMin[2] = std::numeric_limits<T>::max();
26 
27  myMax[0] = -std::numeric_limits<T>::max();
28  myMax[1] = -std::numeric_limits<T>::max();
29  myMax[2] = -std::numeric_limits<T>::max();
30 }
31 
32 template< typename T >
33 template< typename U >
34 inline
35 UT_BoxT<T>::UT_BoxT(const U p[3])
36 {
37  myMin[0] = myMax[0] = p[0];
38  myMin[1] = myMax[1] = p[1];
39  myMin[2] = myMax[2] = p[2];
40 }
41 
42 template< typename T >
43 template< typename U >
44 inline
46 {
47  myMin[0] = myMax[0] = p.x();
48  myMin[1] = myMax[1] = p.y();
49  myMin[2] = myMax[2] = p.z();
50 }
51 
52 template< typename T >
53 inline
55 {
56  myMin[0] = bbox.xmin();
57  myMax[0] = bbox.xmax();
58  myMin[1] = bbox.ymin();
59  myMax[1] = bbox.ymax();
60  myMin[2] = bbox.zmin();
61  myMax[2] = bbox.zmax();
62 }
63 
64 template< typename T >
65 inline bool
67 {
68  return(
69  (myMin[0] > myMax[0]) ||
70  (myMin[1] > myMax[1]) ||
71  (myMin[2] > myMax[2])
72  );
73 }
74 
75 template< typename T >
76 inline T
77 UT_BoxT<T>::getMin(const int c) const
78 {
79  UT_ASSERT_P( (0 <= c) && (c < 3) );
80  UT_ASSERT_P( !isEmpty() );
81 
82  return myMin[c];
83 }
84 
85 template< typename T >
86 inline T
87 UT_BoxT<T>::getMax(const int c) const
88 {
89  UT_ASSERT_P( (0 <= c) && (c < 3) );
90  UT_ASSERT_P( !isEmpty() );
91 
92  return myMax[c];
93 }
94 
95 template< typename T >
96 template< typename U >
97 inline void
99 {
100  myMin[0] = p[0];
101  myMin[1] = p[1];
102  myMin[2] = p[2];
103 
104  myMax[0] = p[0];
105  myMax[1] = p[1];
106  myMax[2] = p[2];
107 }
108 
109 template< typename T >
110 template< typename U >
111 inline void
113 {
114  myMin[0] = (myMin[0] > p[0]) ? p[0] : myMin[0];
115  myMin[1] = (myMin[1] > p[1]) ? p[1] : myMin[1];
116  myMin[2] = (myMin[2] > p[2]) ? p[2] : myMin[2];
117 
118  myMax[0] = (myMax[0] < p[0]) ? p[0] : myMax[0];
119  myMax[1] = (myMax[1] < p[1]) ? p[1] : myMax[1];
120  myMax[2] = (myMax[2] < p[2]) ? p[2] : myMax[2];
121 }
122 
123 template< typename T >
124 inline void
126 {
127  myMin[0] = (myMin[0] > b.myMin[0]) ? b.myMin[0] : myMin[0];
128  myMin[1] = (myMin[1] > b.myMin[1]) ? b.myMin[1] : myMin[1];
129  myMin[2] = (myMin[2] > b.myMin[2]) ? b.myMin[2] : myMin[2];
130 
131  myMax[0] = (myMax[0] < b.myMax[0]) ? b.myMax[0] : myMax[0];
132  myMax[1] = (myMax[1] < b.myMax[1]) ? b.myMax[1] : myMax[1];
133  myMax[2] = (myMax[2] < b.myMax[2]) ? b.myMax[2] : myMax[2];
134 }
135 
136 template< typename T >
137 inline void
139 {
140  myMin[0] = (myMin[0] > b.xmin()) ? b.xmin() : myMin[0];
141  myMin[1] = (myMin[1] > b.ymin()) ? b.ymin() : myMin[1];
142  myMin[2] = (myMin[2] > b.zmin()) ? b.zmin() : myMin[2];
143 
144  myMax[0] = (myMax[0] < b.xmax()) ? b.xmax() : myMax[0];
145  myMax[1] = (myMax[1] < b.ymax()) ? b.ymax() : myMax[1];
146  myMax[2] = (myMax[2] < b.zmax()) ? b.zmax() : myMax[2];
147 }
148 
149 template< typename T >
150 inline void
152 {
153  if( isEmpty() )
154  return;
155 
156  myMin[0] -= l;
157  myMin[1] -= l;
158  myMin[2] -= l;
159 
160  myMax[0] += l;
161  myMax[1] += l;
162  myMax[2] += l;
163 }
164 
165 template< typename T >
166 inline void
167 UT_BoxT<T>::expandDistance(const T l, int axis)
168 {
169  if( isEmpty() )
170  return;
171 
172  myMin[axis] -= l;
173  myMax[axis] += l;
174 }
175 
176 template< typename T >
177 inline bool
178 UT_BoxT<T>::contains(const T*const p) const
179 {
180  return ( (myMin[0] <= p[0]) && (p[0] <= myMax[0]) &&
181  (myMin[1] <= p[1]) && (p[1] <= myMax[1]) &&
182  (myMin[2] <= p[2]) && (p[2] <= myMax[2]) );
183 }
184 
185 template< typename T >
186 inline bool
188 {
189  return (
190  (SYSmax(myMin[0], b.myMin[0]) <= SYSmin(myMax[0], b.myMax[0])) &&
191  (SYSmax(myMin[1], b.myMin[1]) <= SYSmin(myMax[1], b.myMax[1])) &&
192  (SYSmax(myMin[2], b.myMin[2]) <= SYSmin(myMax[2], b.myMax[2]))
193  );
194 }
195 
196 template< >
197 inline bool
199 {
200 #if 1
201  // We have to load from the wrong vector & swizzle or
202  // we risk reading past a page boundary, triggering a fault,
203  // even though we don't use the results of the w() component.
204  v4uf tmax( &myMin[2] );
205  v4uf tmin( &myMin[0] );
206  tmax = tmax.swizzle<1, 2, 3, 0>();
207 
208  v4uf bmax( &b.myMin[2] );
209  v4uf bmin( &b.myMin[0] );
210  bmax = bmax.swizzle<1, 2, 3, 0>();
211 
212  tmin = vmax(tmin, bmin);
213  tmax = vmin(tmax, bmax);
214  v4uu valid = tmin <= tmax;
215 
216  int validmask;
217  validmask = signbits(valid);
218 
219  return ((validmask & 0x7) == 0x7);
220 #else
221  return (
222  (SYSmax(myMin[0], b.myMin[0]) <= SYSmin(myMax[0], b.myMax[0])) &&
223  (SYSmax(myMin[1], b.myMin[1]) <= SYSmin(myMax[1], b.myMax[1])) &&
224  (SYSmax(myMin[2], b.myMin[2]) <= SYSmin(myMax[2], b.myMax[2]))
225  );
226 #endif
227 }
228 
229 
230 template< typename T >
231 inline int
233 {
234  if( isEmpty() )
235  return 0;
236 
237  int max_axis(0);
238  T max_length(myMax[0] - myMin[0]);
239 
240  T length(0);
241 
242  length = myMax[1] - myMin[1];
243  if( length > max_length )
244  {
245  max_length = length;
246  max_axis = 1;
247  }
248 
249  length = myMax[2] - myMin[2];
250  if( length > max_length )
251  {
252  max_length = length;
253  max_axis = 2;
254  }
255 
256  return max_axis;
257 }
258 
259 template< typename T >
260 inline std::ostream& operator<<(std::ostream& os, const UT_BoxT<T>& b)
261 {
262  os << "Box{ min = ";
263  os << b.getMin(0) << ", " << b.getMin(1) << ", " << b.getMin(2);
264  os << ", max = ";
265  os << b.getMax(0) << ", " << b.getMax(1) << ", " << b.getMax(2);
266  os << " }";
267  return os;
268 }
269 
270 template< typename T >
271 inline
273 {
274  myBounds[0].assign(std::numeric_limits<T>::max(),
276  0);
277  myBounds[1].assign(std::numeric_limits<T>::max(),
279  0);
280  myBounds[2].assign(std::numeric_limits<T>::max(),
282  0);
283 }
284 
285 template< typename T >
286 inline
288 {
289  myBounds[0].x() = bbox.xmin();
290  myBounds[0].y() = bbox.xmax();
291  myBounds[0].z() = 0;
292  myBounds[1].x() = bbox.ymin();
293  myBounds[1].y() = bbox.ymax();
294  myBounds[1].z() = 0;
295  myBounds[2].x() = bbox.zmin();
296  myBounds[2].y() = bbox.zmax();
297  myBounds[2].z() = 0;
298 }
299 
300 template< typename T >
301 inline
303 {
304  for (int i = 0; i < 3; i++)
305  {
306  float startmin = start(i, 0);
307  float startmax = start(i, 1);
308 
309  float endmin = end(i, 0);
310  float endmax = end(i, 1);
311 
312  // Solve for minimal velocity.
313  myBounds[i].x() = startmin;
314  myBounds[i].y() = startmin + SYSmax(startmax - startmin, endmax - endmin);
315  myBounds[i].z() = endmin - startmin;
316  }
317 }
318 
319 template< typename T >
320 inline bool
322 {
323  return(
324  (myBounds[0].x() > myBounds[0].y()) ||
325  (myBounds[1].x() > myBounds[1].y()) ||
326  (myBounds[2].x() > myBounds[2].y())
327  );
328 }
329 
330 template< typename T >
331 inline T
332 UT_VelBoxT<T>::getMin(const int c) const
333 {
334  UT_ASSERT_P( (0 <= c) && (c < 3) );
335  UT_ASSERT_P( !isEmpty() );
336 
337  return myBounds[c].x() + SYSmin(myBounds[c].z(), (T)0);
338 }
339 
340 template< typename T >
341 inline T
342 UT_VelBoxT<T>::getMax(const int c) const
343 {
344  UT_ASSERT_P( (0 <= c) && (c < 3) );
345  UT_ASSERT_P( !isEmpty() );
346 
347  return myBounds[c].y() + SYSmax(myBounds[c].z(), (T)0);
348 }
349 
350 template< typename T >
351 inline void
353 {
354  for (int i = 0; i < 3; i++)
355  {
356  float startmin = SYSmin(myBounds[i].x(), b.myBounds[i].x());
357  float startmax = SYSmax(myBounds[i].y(), b.myBounds[i].y());
358 
359  float endmin = SYSmin(myBounds[i].x() + myBounds[i].z(), b.myBounds[i].x() + b.myBounds[i].z());
360  float endmax = SYSmax(myBounds[i].y() + myBounds[i].z(), b.myBounds[i].y() + b.myBounds[i].z());
361 
362  // Solve for minimal velocity.
363  myBounds[i].x() = startmin;
364  myBounds[i].y() = startmin + SYSmax(startmax - startmin, endmax - endmin);
365  myBounds[i].z() = endmin - startmin;
366  }
367 }
368 
369 template< typename T >
370 inline bool
372 {
373  for (int i = 0; i < 3; i++)
374  {
375  T relvel = b.myBounds[i].z() - myBounds[i].z();
376 
377  // b is moving at the speed myVel[i]
378  T bmin = b.myBounds[i].x() + SYSmin(relvel, (T)0);
379  T bmax = b.myBounds[i].y() + SYSmax(relvel, (T)0);
380  if (SYSmax(myBounds[i].x(), bmin) > SYSmin(myBounds[i].y(), bmax))
381  return false;
382  }
383  return true;
384 }
385 
386 template< typename T >
387 inline int
389 {
390  if( isEmpty() )
391  return 0;
392 
393  int max_axis(0);
394  T max_length(myBounds[0].y() - myBounds[0].x());
395 
396  T length(0);
397 
398  length = myBounds[1].y() - myBounds[1].x();
399  if( length > max_length )
400  {
401  max_length = length;
402  max_axis = 1;
403  }
404 
405  length = myBounds[2].y() - myBounds[2].x();
406  if( length > max_length )
407  {
408  max_length = length;
409  max_axis = 2;
410  }
411 
412  return max_axis;
413 }
414 
415 template< typename T >
416 inline std::ostream& operator<<(std::ostream& os, const UT_VelBoxT<T>& b)
417 {
418  os << "Box{ min = ";
419  os << b.getMin(0) << ", " << b.getMin(1) << ", " << b.getMin(2);
420  os << ", max = ";
421  os << b.getMax(0) << ", " << b.getMax(1) << ", " << b.getMax(2);
422  os << ", vel = ";
423  os << b.getVel(0) << ", " << b.getVel(1) << ", " << b.getVel(2);
424  os << " }";
425  return os;
426 }
427 
428 template< typename T >
429 inline bool
431 {
432  // We calculate whether the box intersects the sphere by
433  // calculating the distance from the sphere center to the
434  // minimum / maximum axis coordinate (for each axis), squaring,
435  // and adding together to compare to the sphere radius
436  T min_distance = 0;
437  for( int axis = 0; axis < 3; axis++ )
438  {
439  if( myCentre[axis] < b.getMin(axis) )
440  {
441  T difference = myCentre[axis] - b.getMin(axis);
442  min_distance += difference * difference;
443  }
444  else if( myCentre[axis] > b.getMax(axis) )
445  {
446  T difference = myCentre[axis] - b.getMax(axis);
447  min_distance += difference * difference;
448  }
449  }
450  return min_distance <= myRadius*myRadius;
451 }
452 
453 template< typename BOXTYPE>
455 {
456  typedef BOXTYPE Box;
457 
459  int myItem;
460 
462  myBox(),
463  myItem(-1)
464  {
465  }
466 };
467 
468 template< typename T >
469 inline std::ostream& operator<<(std::ostream& os, const UT_BoxedItemT<T>& bf)
470 {
471  os << "BoxedItem{ ";
472  os << "box = ";
473  os << bf.myBox << ", ";
474  os << "item = ";
475  os << bf.myItem;
476  os << " }";
477  return os;
478 }
479 
480 // Compute the bounding box for a range of boxes [begin, end)
481 template< typename BOXTYPE>
482 inline void
484  BOXTYPE& bounding_box,
485  const BOXTYPE*const begin, const BOXTYPE*const end
486 )
487 {
488  UT_ASSERT_P( end != begin );
489 
490  bounding_box = *begin;
491 
492  for( const BOXTYPE* i = begin + 1; i != end; ++i )
493  {
494  bounding_box.absorbBox(*i);
495  }
496 }
497 
498 // Compute the bounding box for all the boxes in
499 // a range of boxed items [begin, end)
500 template< typename BOXTYPE >
501 inline void
503  BOXTYPE& bounding_box,
504  const UT_BoxedItemT<BOXTYPE>*const begin, const UT_BoxedItemT<BOXTYPE>*const end
505 )
506 {
507  UT_ASSERT_P( end != begin );
508 
509  bounding_box = begin->myBox;
510 
511  for( const UT_BoxedItemT<BOXTYPE>* i = begin + 1; i != end; ++i )
512  {
513  bounding_box.absorbBox(i->myBox);
514  }
515 }
516 
517 // Sort boxed items in the direction of an axis, by their centers
518 template< typename T >
520 {
521  int myAxis;
522 
523  explicit UT_BoxedItemAxisOrderT(const int axis) :
524  myAxis(axis)
525  {
526  }
527 
529  {
530  }
531 
533  {
534  typename T::Scalar amid = a.myBox.getMin(myAxis) + a.myBox.getMax(myAxis);
535  typename T::Scalar bmid = b.myBox.getMin(myAxis) + b.myBox.getMax(myAxis);
536 
537  return amid < bmid;
538  }
539 };
540 
541 template< int MAX_ORDER >
542 class UT_RNode
543 {
544 public:
545  typedef uint32 Index;
546 
548  {
549  clear();
550  }
551 
553  {
554  }
555 
556  void clear()
557  {
558  setInternal(false);
559  for( int s = 0; s < MAX_ORDER; ++s )
560  {
562  }
563  }
564 
565  void setInternal(const bool isInternal)
566  {
567  mySlots[0] = ( (mySlots[0] & SLOT_MASK_INDEX) |
568  (isInternal ? SLOT_FLAG_INTERNAL : 0) );
569  }
570 
571  // Assuming this is an internal node, assign a node index to slot s
572  void assignSubtree(const int s, const int index_root_subtree)
573  {
574  UT_ASSERT_P( isInternal() );
575  UT_ASSERT_P( (0 <= s) && (s < MAX_ORDER) );
576  UT_ASSERT_P( 0 <= index_root_subtree );
577  UT_ASSERT_P(
578  (static_cast<uint32>(index_root_subtree) & SLOT_MASK_INDEX) ==
579  static_cast<uint32>(index_root_subtree)
580  );
581 
582  mySlots[s] = index_root_subtree | SLOT_FLAG_INTERNAL;
583  }
584 
585  // Assign an item to slot s
586  void assignItem(const int s, const int item)
587  {
588  UT_ASSERT_P( !isInternal() );
589  UT_ASSERT_P( (0 <= s) && (s < MAX_ORDER) );
590  UT_ASSERT_P( 0 <= item );
591  UT_ASSERT_P(
592  (static_cast<uint32>(item) & SLOT_MASK_INDEX) ==
593  static_cast<uint32>(item)
594  );
595 
596  mySlots[s] = item;
597  }
598 
599  bool isInternal() const
600  {
601  return ((mySlots[0] & SLOT_FLAG_INTERNAL) != 0);
602  }
603 
604  // Get node stored in slot.
605  // This assumes that the last assignment to this slot was an node!
606  // (not an item)
607  int getSubtree(const int s) const
608  {
609  UT_ASSERT_P( isInternal() );
610  UT_ASSERT_P( (0 <= s) && (s < MAX_ORDER) );
612 
613  return (mySlots[s] & SLOT_MASK_INDEX);
614  }
615 
616  // For internal nodes, count the number of children
617  // For leaf nodes, count the number of items
618  int countNumItems() const
619  {
620  int num_items(0);
621  for( int s = 0; s < MAX_ORDER; ++s )
622  {
624  break;
625 
626  ++num_items;
627  }
628 
629  return num_items;
630  }
631 
632  // Get item stored in slot.
633  // This assumes that the last assignment to this slot was an item!
634  // (not a node)
635  int getItem(const int s) const
636  {
637  UT_ASSERT_P( !isInternal() );
638  UT_ASSERT_P( (0 <= s) && (s < MAX_ORDER) );
640 
641  return (mySlots[s] & SLOT_MASK_INDEX);
642  }
643 
644  typedef Index Slot;
645  static const Slot SLOT_FLAG_INTERNAL = 0x80000000;
646  static const Slot SLOT_MASK_INDEX = 0x7fffffff;
648 
649  //
650  // mySlots[0] has a bit that defines whether the node is an internal
651  // node. This is the SLOT_FLAG_INTERNAL bit.
652  // In an internal node, each non-empty slot has the index of a child
653  // node.
654  // In a leaf node, each non-empty slot has the index of an item.
655  //
656  // A node (internal or leaf) may not always be full
657  // (fewer than MAX_ORDER children for internal node case, or fewer than
658  // MAX_ORDER items for leaf case).
659  // When the node is not full, then the empty slots form
660  // a contiguous range after all the nonempty slots.
661  // The full range consists of the slots s in the half-open range
662  // [ 0, getNumItems() )
663  //
664 
665  Slot mySlots[MAX_ORDER];
666 };
667 
668 // Determine the exact number of nodes needed to store an R-tree of MAX_ORDER
669 // with "size" elements. The O(log n) cost of this calculation is insignificant compared to
670 // the time it takes to construct the tree.
671 inline size_t
673  const int MAX_ORDER,
674  const size_t size
675 )
676 {
677  int num_nodes(0);
678 
679  if( size > MAX_ORDER )
680  {
681  // Internal node
682 
683  ++num_nodes;
684 
685  size_t m(MAX_ORDER);
686  while( m * MAX_ORDER < size )
687  m *= MAX_ORDER;
688 
689  UT_ASSERT_P( MAX_ORDER <= m );
690  UT_ASSERT_P( m < size );
691 
692  // Count number of nodes for the at most MAX_ORDER subtrees that
693  // have exactly m elements
694 
695  const int num_subtrees_size_m( size / m );
696 
697  UT_ASSERT_P( num_subtrees_size_m <= MAX_ORDER );
698 
699  const size_t num_nodes_for_m( subtreeDetermineNumNodes(MAX_ORDER, m) );
700 
701  num_nodes += num_subtrees_size_m * num_nodes_for_m;
702 
703  // Count number of nodes for the subtree with the less than m
704  // remaining elements (if this exists)
705 
706  const size_t num_remaining_items( size % m );
707  if( num_remaining_items > 0 )
708  {
709  num_nodes += subtreeDetermineNumNodes(MAX_ORDER, num_remaining_items);
710  }
711  }
712  else
713  {
714  // Leaf node
715 
716  ++num_nodes;
717  }
718 
719  return num_nodes;
720 }
721 
722 /// Partition the range of boxed items [begin, end) according to the given
723 /// comparison function such that all items in the range [0, m-1] are less than
724 /// or equal to all items in [m, 2m-1], which are less than or equal to all
725 /// items in [2m, 3m-1], etc, where m is the subtree size.
726 template< typename BOXTYPE >
727 inline void
730  const UT_BoxedItemAxisOrderT<BOXTYPE> &order,
731  int subtree_size, int num_subtrees
732 )
733 {
734  if (num_subtrees <= 1)
735  return;
736 
737  // Choose a multiple of the subtree size that's close to the middle, and
738  // partition so that all items in [begin, begin + i) are less than or equal
739  // to all items in [begin + i, end).
740  const int mid = num_subtrees / 2;
741  const int i = mid * subtree_size;
742  UTnth_element(begin, begin + i, end, order);
743 
744  // Recursively partition each side.
745  partitionForSubtrees(begin, begin + i, order, subtree_size, mid);
746  partitionForSubtrees(begin + i, end, order, subtree_size,
747  num_subtrees - mid);
748 }
749 
750 // Create a subtree for the range of boxed items [begin, end).
751 // Return a pointer to the subtree root (this points into in shared_nodes)
752 // In addition, bounding_box will be a bounding box for the subtree.
753 template< int MAX_ORDER, typename BOXTYPE >
754 inline UT_RNode<MAX_ORDER>*
756  BOXTYPE& bounding_box,
757  BOXTYPE shared_boxes[],
759  UT_RNode<MAX_ORDER>*const shared_nodes,
760  UT_RNode<MAX_ORDER>*& shared_nodes_end
761 )
762 {
763  SYS_STATIC_ASSERT( MAX_ORDER >= 2 );
764 
765  UT_RNode<MAX_ORDER>* node(shared_nodes_end++);
766  node->clear();
767 
768  // node_boxes is the sub-array that contains the at most MAX_ORDER boxes
769  // for the node that we're building
770  BOXTYPE*const node_boxes(
771  shared_boxes +
772  ((node - shared_nodes) * MAX_ORDER)
773  );
774 
775  const size_t size(end - begin);
776 
777  UT_ASSERT_P( size > 0 );
778 
779  computeBoundingBoxItem(bounding_box, begin, end);
780 
781  if( size > MAX_ORDER )
782  {
783  // Create an internal node at most MAX_ORDER nonempty slots.
784  // slot s will have the index of the root of a subtree,
785  // which is contained in node_boxes[s]
786 
787  node->setInternal(true);
788 
789  // Partition in a way that is balanced but that aims
790  // to keep the number of unused slots in leaves very small
791  // Pick "m" to be the ideal number of items per subtree.
792  size_t m(MAX_ORDER);
793  while( m * MAX_ORDER < size )
794  m *= MAX_ORDER;
795 
796  UT_ASSERT_P( MAX_ORDER <= m );
797  UT_ASSERT_P( m < size );
798 
799  size_t offset(0);
800 
801  // Create at most MAX_ORDER subtrees, each of which has exactly m elements
802  const int num_subtrees_size_m( size / m );
803 
804  UT_ASSERT_P( num_subtrees_size_m <= MAX_ORDER );
805 
806  // TODO: perhaps splitting along a single axis is not the best
807  UT_BoxedItemAxisOrderT<BOXTYPE> order(bounding_box.getLargestAxis());
808  // Partition the elements for each subtree.
809  partitionForSubtrees(begin, end, order, m, num_subtrees_size_m);
810 
811  for( int s = 0; s < num_subtrees_size_m; ++s )
812  {
813  if( size - offset < m )
814  break;
815 
816  const size_t next_offset( offset + m );
817 
818  node->assignSubtree(
819  s,
821  node_boxes[s],
822  shared_boxes,
823  begin + offset, begin + next_offset,
824  shared_nodes,
825  shared_nodes_end
826  ) - shared_nodes //FIXME: ugly pointer arithmetic
827  );
828 
829  offset = next_offset;
830  }
831 
832  // If needed, create a subtree for any remaining elements (strictly less than m)
833  const size_t num_remaining_items( size % m );
834  if( num_remaining_items > 0 )
835  {
836  UT_ASSERT_P( num_subtrees_size_m < MAX_ORDER );
837  UT_ASSERT_P( num_remaining_items == size - offset );
838 
839  const size_t next_offset( offset + num_remaining_items );
840 
841  node->assignSubtree(
842  num_subtrees_size_m,
844  node_boxes[num_subtrees_size_m],
845  shared_boxes,
846  begin + offset, begin + next_offset,
847  shared_nodes,
848  shared_nodes_end
849  ) - shared_nodes //FIXME: ugly pointer arithmetic
850  );
851 
852  offset = next_offset;
853  }
854 
855  UT_ASSERT_P( offset == size );
856 
857  UT_ASSERT_P( node->countNumItems() > 0 );
858  }
859  else
860  {
861  // Create a leaf with size nonempty slots.
862  // Each slot has the index of a shared node box.
863  node->setInternal(false);
864 
865  int s(0);
866  for( const UT_BoxedItemT<BOXTYPE>* i = begin; i != end; ++i )
867  {
868  node_boxes[s] = i->myBox;
869  node->assignItem(s, i->myItem);
870  ++s;
871  }
872  }
873 
874  return node;
875 }
876 
877 template< int MAX_ORDER >
878 inline int
880 {
881  return myNumItems;
882 }
883 
884 template< int MAX_ORDER, typename BOXTYPE>
885 inline void
887  BOXTYPE& bounding_box,
888  BOXTYPE*const shared_boxes,
889  const UT_RNode<MAX_ORDER>*const shared_nodes,
890  const UT_RNode<MAX_ORDER>*const node,
891  const BOXTYPE item_boxes[]
892 )
893 {
894  using RNode = UT_RNode<MAX_ORDER>;
895 
896  UT_ASSERT_P( node != 0 );
897 
898  // node_boxes is the sub-array that contains the MAX_ORDER boxes
899  // for the node that we're visiting
900  BOXTYPE*const node_boxes(
901  shared_boxes +
902  ((node - shared_nodes) * MAX_ORDER)
903  );
904 
905  if( node->isInternal() )
906  {
907  for( int s = 0; s < MAX_ORDER; ++s )
908  {
909  if( (node->mySlots[s] & RNode::SLOT_MASK_INDEX) == RNode::SLOT_VALUE_EMPTY )
910  break;
911 
913  node_boxes[s],
914  shared_boxes,
915  shared_nodes,
916  shared_nodes + node->getSubtree(s),
917  item_boxes
918  );
919  }
920  }
921  else
922  {
923  int s = 0;
924  for( ; s < MAX_ORDER; ++s )
925  {
926  if( (node->mySlots[s] & RNode::SLOT_MASK_INDEX) == RNode::SLOT_VALUE_EMPTY )
927  break;
928 
929  node_boxes[s] = item_boxes[node->getItem(s)];
930  }
931  for( ; s < MAX_ORDER; ++s )
932  {
933  node_boxes[s] = BOXTYPE(); // Empty set
934  }
935  }
936 
937  computeBoundingBox(bounding_box, node_boxes, node_boxes + MAX_ORDER);
938 }
939 
940 template< typename QUERY_SHAPE, typename RESULT_ACCEPTOR, int MAX_ORDER, typename BOXTYPE >
941 inline void
943  RESULT_ACCEPTOR& acceptor,
944  const UT_RNode<MAX_ORDER>*const shared_nodes,
945  const BOXTYPE*const shared_boxes,
946  const UT_RNode<MAX_ORDER>*const node,
947  const QUERY_SHAPE& query_box
948 )
949 {
950  using RNode = UT_RNode<MAX_ORDER>;
951 
952  UT_ASSERT_P( node != 0 );
953 
954  // node_boxes is the sub-array that contains the MAX_ORDER boxes
955  // for the node that we're visiting
956  const BOXTYPE*const node_boxes(
957  shared_boxes +
958  ((node - shared_nodes) * MAX_ORDER)
959  );
960 
961  if( node->isInternal() )
962  {
963  for( int s = 0; s < MAX_ORDER; ++s )
964  {
965  if( (node->mySlots[s] & RNode::SLOT_MASK_INDEX) == RNode::SLOT_VALUE_EMPTY )
966  break;
967 
968  if( query_box.intersects(node_boxes[s]) )
969  {
971  acceptor,
972  shared_nodes, shared_boxes,
973  shared_nodes + node->getSubtree(s),
974  query_box
975  );
976  }
977  }
978  }
979  else
980  {
981  for( int s = 0; s < MAX_ORDER; ++s )
982  {
983  if( (node->mySlots[s] & RNode::SLOT_MASK_INDEX) == RNode::SLOT_VALUE_EMPTY )
984  break;
985 
986  if( query_box.intersects(node_boxes[s]) )
987  {
988  acceptor(node->getItem(s));
989  }
990  }
991  }
992 }
993 
994 template< typename QUERY_SHAPE, typename RESULT_ACCEPTOR, int MAX_ORDER, typename BOXTYPE, int BATCH_SIZE >
995 inline void
997  RESULT_ACCEPTOR& acceptor,
998  const UT_RNode<MAX_ORDER>*const shared_nodes,
999  const BOXTYPE*const shared_boxes,
1000  const UT_RNode<MAX_ORDER>*const node,
1001  const QUERY_SHAPE *query_boxes
1002 )
1003 {
1004  using RNode = UT_RNode<MAX_ORDER>;
1005 
1006  UT_ASSERT_P( node != 0 );
1007 
1008  // node_boxes is the sub-array that contains the MAX_ORDER boxes
1009  // for the node that we're visiting
1010  const BOXTYPE*const node_boxes(
1011  shared_boxes +
1012  ((node - shared_nodes) * MAX_ORDER)
1013  );
1014 
1015  if( node->isInternal() )
1016  {
1017  for( int s = 0; s < MAX_ORDER; ++s )
1018  {
1019  if( (node->mySlots[s] & RNode::SLOT_MASK_INDEX) == RNode::SLOT_VALUE_EMPTY )
1020  break;
1021 
1022  for (int i = 0; i < BATCH_SIZE; i++)
1023  {
1024  if( query_boxes[i].intersects(node_boxes[s]) )
1025  {
1026  subtreeGetIntersectingItemsBatch<QUERY_SHAPE, RESULT_ACCEPTOR, MAX_ORDER, BOXTYPE, BATCH_SIZE>(
1027  acceptor,
1028  shared_nodes, shared_boxes,
1029  shared_nodes + node->getSubtree(s),
1030  query_boxes
1031  );
1032  break;
1033  }
1034  }
1035  }
1036  }
1037  else
1038  {
1039  for( int s = 0; s < MAX_ORDER; ++s )
1040  {
1041  if( (node->mySlots[s] & RNode::SLOT_MASK_INDEX) == RNode::SLOT_VALUE_EMPTY )
1042  break;
1043 
1044  for (int i = 0; i < BATCH_SIZE; i++)
1045  {
1046  if( query_boxes[i].intersects(node_boxes[s]) )
1047  {
1048  acceptor(i, node->getItem(s));
1049  }
1050  }
1051  }
1052  }
1053 }
1054 
1055 template< int MAX_ORDER >
1056 inline int
1058  const UT_RNode<MAX_ORDER> shared_nodes[],
1059  const UT_RNode<MAX_ORDER>*const node
1060 )
1061 {
1062  using RNode = UT_RNode<MAX_ORDER>;
1063 
1064  UT_ASSERT_P( node != 0 );
1065 
1066  if( node->isInternal() )
1067  {
1068  int max_depth_children(0);
1069 
1070 
1071  for( int s = 0; s < MAX_ORDER; ++s )
1072  {
1073  if( (node->mySlots[s] & RNode::SLOT_MASK_INDEX) == RNode::SLOT_VALUE_EMPTY )
1074  break;
1075 
1076  max_depth_children = std::max(
1077  max_depth_children,
1078  UTsubtreeComputeMaxDepth(shared_nodes, shared_nodes + node->getSubtree(s))
1079  );
1080  }
1081 
1082  return 1 + max_depth_children;
1083  }
1084  else
1085  {
1086  return 0;
1087  }
1088 }
1089 
1090 
1091 template< int MAX_ORDER >
1092 template< typename BOXTYPE >
1094  const BOXTYPE item_boxes[], const int size
1095 ) :
1096  mySharedNodesSize(0),
1097  mySharedNodes(0),
1098  myRoot(0),
1099  myNumItems(size)
1100 {
1101  SYS_STATIC_ASSERT( MAX_ORDER >= 2 );
1102 
1103  UT_ASSERT_P( size >= 0 );
1104 
1105  if( size <= 0 )
1106  return;
1107 
1108  mySharedNodesSize = subtreeDetermineNumNodes(MAX_ORDER, size);
1109  mySharedNodes = new UT_RNode<MAX_ORDER>[mySharedNodesSize];
1110 
1111  UT_RNode<MAX_ORDER>* shared_nodes_end(mySharedNodes);
1112 
1113  // Put item #i in box[i], resulting in boxes_items
1114  std::vector< UT_BoxedItemT<BOXTYPE> > boxed_items;
1115  boxed_items.resize(size);
1116  for( int i = 0; i < size; ++i )
1117  {
1118  boxed_items[i].myBox = item_boxes[i];
1119  boxed_items[i].myItem = i;
1120  }
1121 
1122  // Create the R-tree nodes, based on boxed_items
1123  BOXTYPE bounding_box_root;
1124  std::vector< BOXTYPE > shared_boxes( MAX_ORDER * mySharedNodesSize );
1125  myRoot = subtreeCreate(
1126  bounding_box_root,
1127  &(shared_boxes[0]),
1128  &(boxed_items[0]), &(boxed_items[0]) + boxed_items.size(),
1129  mySharedNodes,
1130  shared_nodes_end
1131  );
1132 
1133  UT_ASSERT_P( shared_nodes_end - mySharedNodes == mySharedNodesSize );
1134 
1135 #if 0
1136  std::cout << "RTree stats: " << std::endl;
1137  std::cout << "Number of items: " << size << std::endl;
1138  std::cout << "Tree size (in node): " << mySharedNodesSize << std::endl;
1139  std::cout << "MAX_ORDER (max children/items per node) = " << MAX_ORDER << std::endl;
1140  std::cout << "Number of items per node: " << fpreal64(size) / fpreal64(mySharedNodesSize) << std::endl;
1141  std::cout << "Max tree depth: " << UTsubtreeComputeMaxDepth(mySharedNodes, myRoot) << std::endl;
1142 #endif // 0
1143 }
1144 
1145 template< int MAX_ORDER >
1147 {
1148  delete[] mySharedNodes;
1149  mySharedNodes = 0;
1150 }
1151 
1152 template< int MAX_ORDER >
1153 template< typename BOXTYPE>
1154 inline void
1156  UT_RTreeAssignmentT<BOXTYPE>& assignment,
1157  const BOXTYPE item_boxes[]
1158 ) const
1159 {
1160  if( myRoot == 0 )
1161  return;
1162 
1163  assignment.myBoxesForSharedNodes.reserve(
1164  MAX_ORDER * mySharedNodesSize
1165  );
1166 
1167  // Allocate room for MAX_ORDER boxes for each shared node
1168  // Box c of node n is stored in slot (MAX_ORDER * n) + c
1169  assignment.myBoxesForSharedNodes.resize(
1170  MAX_ORDER * mySharedNodesSize
1171  );
1172 
1173  BOXTYPE bounding_box_root;
1175  bounding_box_root,
1176  &(assignment.myBoxesForSharedNodes[0]),
1177  mySharedNodes,
1178  myRoot,
1179  item_boxes
1180  );
1181 
1182 #if 0
1183  std::cout << "reserved: " << MAX_ORDER * mySharedNodesSize << std::endl;
1184  std::cout << "capacity: " << assignment.myBoxesForSharedNodes.capacity() << std::endl;
1185 #endif // 0
1186 }
1187 
1188 template< int MAX_ORDER >
1189 template< typename QUERY_SHAPE, typename RESULT_ACCEPTOR, typename BOXTYPE >
1190 void
1192  RESULT_ACCEPTOR& result_acceptor,
1193  const QUERY_SHAPE& query_box,
1194  const UT_RTreeAssignmentT<BOXTYPE>& assignment
1195 ) const
1196 {
1197  if( myRoot == 0 )
1198  return;
1199 
1201  result_acceptor,
1202  mySharedNodes,
1203  &(assignment.myBoxesForSharedNodes[0]),
1204  myRoot, query_box
1205  );
1206 }
1207 
1208 template< int MAX_ORDER >
1209 template< typename QUERY_SHAPE, typename RESULT_ACCEPTOR, typename BOXTYPE, int BATCH_SIZE >
1210 void
1212  RESULT_ACCEPTOR& result_acceptor,
1213  const QUERY_SHAPE *query_boxes,
1214  const UT_RTreeAssignmentT<BOXTYPE>& assignment
1215 ) const
1216 {
1217  if( myRoot == 0 )
1218  return;
1219 
1220  subtreeGetIntersectingItemsBatch< QUERY_SHAPE, RESULT_ACCEPTOR, MAX_ORDER, BOXTYPE, BATCH_SIZE> (
1221  result_acceptor,
1222  mySharedNodes,
1223  &(assignment.myBoxesForSharedNodes[0]),
1224  myRoot, query_boxes
1225  );
1226 }
1227 
1229 {
1230 public:
1232  : myResults(results)
1233  , myBaseIndex(baseindex)
1234  {
1235  }
1236 
1237  inline void operator()(const int i)
1238  {
1239  myResults.append(i + myBaseIndex);
1240  }
1241 
1242 private:
1243  UT_Array<int>& myResults;
1244  exint myBaseIndex;
1245 
1246  // Disallow
1249  UT_RTreeResultAppenderIntArray& operator=(
1251  );
1252 };
1253 
1255 {
1256 public:
1258  : myResults(results)
1259  , myBaseIndex(baseindex)
1260  {
1261  }
1262 
1263  inline void operator()(const int batch, const int i)
1264  {
1265  myResults[batch].append(i + myBaseIndex);
1266  }
1267 
1268 private:
1269  UT_Array<int> *myResults;
1270  exint myBaseIndex;
1271 
1272  // Disallow
1277  );
1278 };
1279 
1280 template< typename QUERY_SHAPE, int MAX_ORDER, typename BOXTYPE >
1282  UT_Array<int>& results,
1283  const UT_RTreeGeneric<MAX_ORDER>& tree,
1284  const QUERY_SHAPE& query_box,
1285  const UT_RTreeAssignmentT<BOXTYPE>& assignment
1286 )
1287 {
1288  results.clear();
1289  UT_RTreeResultAppenderIntArray appender(results, 0);
1290  tree.getIntersectingItems(appender, query_box, assignment);
1291 }
1292 
1293 template< typename QUERY_SHAPE, int MAX_ORDER, typename BOXTYPE, int BATCH_SIZE >
1295  UT_Array<int> *results,
1296  const UT_RTreeGeneric<MAX_ORDER>& tree,
1297  const QUERY_SHAPE *query_boxes,
1298  const UT_RTreeAssignmentT<BOXTYPE>& assignment
1299 )
1300 {
1301  UT_RTreeResultAppenderBatchIntArray appender(results, 0);
1302  tree.template getIntersectingItemsBatch<QUERY_SHAPE, UT_RTreeResultAppenderBatchIntArray, BOXTYPE, BATCH_SIZE>(appender, query_boxes, assignment);
1303 }
1304 
1305 template< typename QUERY_SHAPE, int MAX_ORDER, typename BOXTYPE >
1307  UT_Array<int>& results,
1308  const UT_RTreeGeneric<MAX_ORDER>& tree,
1309  const QUERY_SHAPE& query_box,
1310  const UT_RTreeAssignmentT<BOXTYPE>& assignment,
1311  exint baseindex
1312 )
1313 {
1314  UT_RTreeResultAppenderIntArray appender(results, baseindex);
1315  tree.getIntersectingItems(appender, query_box, assignment);
1316 }
1317 
1319 {
1320 public:
1322  myIt(it)
1323  {
1324  }
1325 
1326  inline void operator()(const int i)
1327  {
1328  *myIt++ = i;
1329  }
1330 
1331  int* getIterator() const
1332  {
1333  return myIt;
1334  }
1335 
1336 private:
1337  int* myIt;
1338 
1339  // Disallow
1344  );
1345 };
1346 
1347 template< typename QUERY_SHAPE, int MAX_ORDER, typename BOXTYPE >
1349  const UT_RTreeGeneric<MAX_ORDER>& tree,
1350  const QUERY_SHAPE& query_box,
1351  const UT_RTreeAssignmentT<BOXTYPE>& assignment,
1352  int*const items_begin
1353 )
1354 {
1355  UT_RTreeResultAcceptorRawIntIterator acceptor(items_begin);
1356 
1357  tree.getIntersectingItems(acceptor, query_box, assignment);
1358 
1359  return acceptor.getIterator();
1360 }
1361 
1362 
1363 template< int MAX_ORDER >
1364 template< typename BOXTYPE >
1366  const UT_RTreeAssignmentT<BOXTYPE>& assignment) const
1367 {
1368  using RNode = UT_RNode<MAX_ORDER>;
1369 
1370  BOXTYPE box;
1371 
1372  if (myRoot == 0)
1373  return box;
1374 
1375  const BOXTYPE*const root_boxes =
1376  assignment.myBoxesForSharedNodes.data() + (myRoot - mySharedNodes)*MAX_ORDER;
1377 
1378  for (int s = 0; s < MAX_ORDER; ++s)
1379  {
1380  if ((myRoot->mySlots[s] & RNode::SLOT_MASK_INDEX) == RNode::SLOT_VALUE_EMPTY)
1381  break;
1382 
1383  box.absorbBox(root_boxes[s]);
1384  }
1385 
1386  return box;
1387 }
1388 
1389 
1390 template< int MAX_ORDER >
1391 template<typename LOCAL_DATA,typename PRE_FUNCTOR,typename ITEM_FUNCTOR,typename POST_FUNCTOR>
1392 void
1394  PRE_FUNCTOR &pre_functor,
1395  ITEM_FUNCTOR &item_functor,
1396  POST_FUNCTOR &post_functor,
1397  LOCAL_DATA *data_for_parent) const
1398 {
1399  if (!myRoot)
1400  return;
1401 
1402  traverseHelper(myRoot-mySharedNodes, -1, pre_functor, item_functor, post_functor, data_for_parent);
1403 }
1404 template< int MAX_ORDER >
1405 template<typename LOCAL_DATA,typename PRE_FUNCTOR,typename ITEM_FUNCTOR,typename POST_FUNCTOR>
1406 void
1408  int nodei,
1409  int parent_nodei,
1410  PRE_FUNCTOR &pre_functor,
1411  ITEM_FUNCTOR &item_functor,
1412  POST_FUNCTOR &post_functor,
1413  LOCAL_DATA *data_for_parent) const
1414 {
1415  using RNode = UT_RNode<MAX_ORDER>;
1416  const RNode &node = mySharedNodes[nodei];
1417  LOCAL_DATA local_data[MAX_ORDER];
1418  bool descend = pre_functor(nodei, data_for_parent);
1419  if (!descend)
1420  return;
1421  const int nsub = node.countNumItems();
1422  if (node.isInternal())
1423  {
1424  for (int s = 0; s < nsub; ++s)
1425  traverseHelper(node.getSubtree(s), nodei, pre_functor, item_functor, post_functor, &local_data[s]);
1426  }
1427  else
1428  {
1429  for (int s = 0; s < nsub; ++s)
1430  item_functor(node.getItem(s), nodei, local_data[s]);
1431  }
1432  post_functor(nodei, parent_nodei, data_for_parent, nsub, local_data);
1433 }
1434 
1435 template <>
1436 inline void
1437 subtreeGetIntersectingItemsBatch<UT_BoxT<float>,
1439  4,
1441  4>
1442  (
1443  UT_RTreeResultAppenderBatchIntArray& acceptor,
1444  const UT_RNode<4>*const shared_nodes,
1445  const UT_BoxT<float>*const shared_boxes,
1446  const UT_RNode<4>*const node,
1447  const UT_BoxT<float> *query_boxes
1448 )
1449 {
1450  using RNode = UT_RNode<4>;
1451 
1452  UT_ASSERT_P( node != 0 );
1453 
1454  // node_boxes is the sub-array that contains the MAX_ORDER boxes
1455  // for the node that we're visiting
1456  const UT_BoxT<float>*const node_boxes(
1457  shared_boxes +
1458  ((node - shared_nodes) * 4)
1459  );
1460 
1461  v4uf qmin[3];
1462  v4uf qmax[3];
1463 
1464  for (int i = 0; i < 3; i++)
1465  {
1466  qmin[i] = v4uf(query_boxes[0].getMin(i),
1467  query_boxes[1].getMin(i),
1468  query_boxes[2].getMin(i),
1469  query_boxes[3].getMin(i));
1470  qmax[i] = v4uf(query_boxes[0].getMax(i),
1471  query_boxes[1].getMax(i),
1472  query_boxes[2].getMax(i),
1473  query_boxes[3].getMax(i));
1474  }
1475 
1476 
1477  if( node->isInternal() )
1478  {
1479  int liveslots = 0;
1480  const UT_RNode<4>* childnodes[4];
1481 
1482  for( int s = 0; s < 4; ++s )
1483  {
1484  if( (node->mySlots[s] & RNode::SLOT_MASK_INDEX) == RNode::SLOT_VALUE_EMPTY )
1485  break;
1486 
1487  v4uu valid(0);
1488  v4uf tmax, tmin;
1489  int validmask = 0;
1490 
1491  for (int i = 0; i < 3; i++)
1492  {
1493  // Extract node box & splat.
1494  tmin = v4uf(node_boxes[s].getMin(i));
1495  tmax = v4uf(node_boxes[s].getMax(i));
1496 
1497  // Do intersection of 4 query boxes with node box.
1498  tmin = vmax(tmin, qmin[i]);
1499  tmax = vmin(tmax, qmax[i]);
1500  valid |= tmin > tmax;
1501 
1502  validmask = _mm_movemask_ps(V4SF(valid.vector));
1503  if (validmask == 0xf)
1504  break;
1505  }
1506 
1507  if (validmask != 0xf)
1508  {
1509  childnodes[liveslots++] = shared_nodes + node->getSubtree(s);
1510  }
1511  }
1512 
1513  for (int s = 0; s < liveslots; s++)
1514  {
1515  subtreeGetIntersectingItemsBatch<UT_BoxT<float>, UT_RTreeResultAppenderBatchIntArray, 4, UT_BoxT<float>, 4>(
1516  acceptor,
1517  shared_nodes, shared_boxes,
1518  childnodes[s],
1519  query_boxes
1520  );
1521  }
1522  }
1523  else
1524  {
1525  for( int s = 0; s < 4; ++s )
1526  {
1527  if( (node->mySlots[s] & RNode::SLOT_MASK_INDEX) == RNode::SLOT_VALUE_EMPTY )
1528  break;
1529 
1530  v4uu valid(0);
1531  int validmask = 0;
1532  v4uf tmax, tmin;
1533 
1534  for (int i = 0; i < 3; i++)
1535  {
1536  // Extract node box & splat.
1537  tmin = v4uf(node_boxes[s].getMin(i));
1538  tmax = v4uf(node_boxes[s].getMax(i));
1539 
1540  // Do intersection of 4 query boxes with node box.
1541  tmin = vmax(tmin, qmin[i]);
1542  tmax = vmin(tmax, qmax[i]);
1543  valid |= tmin > tmax;
1544 
1545  validmask = _mm_movemask_ps(V4SF(valid.vector));
1546  if (validmask == 0xf)
1547  break;
1548  }
1549 
1550  if (validmask != 0xf)
1551  {
1552  for (int i = 0; i < 4; i++)
1553  {
1554  if (! (valid[i] & (1 << i)) )
1555  {
1556  acceptor(i, node->getItem(s));
1557  }
1558  }
1559  }
1560  }
1561  }
1562 }
void partitionForSubtrees(UT_BoxedItemT< BOXTYPE > *const begin, UT_BoxedItemT< BOXTYPE > *const end, const UT_BoxedItemAxisOrderT< BOXTYPE > &order, int subtree_size, int num_subtrees)
Definition: UT_RTree.C:728
void computeBoundingBoxItem(BOXTYPE &bounding_box, const UT_BoxedItemT< BOXTYPE > *const begin, const UT_BoxedItemT< BOXTYPE > *const end)
Definition: UT_RTree.C:502
#define SYSmax(a, b)
Definition: SYS_Math.h:1367
T getMin(const int c) const
Definition: UT_RTree.C:77
#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:151
static const Slot SLOT_FLAG_INTERNAL
Definition: UT_RTree.C:645
int UTsubtreeComputeMaxDepth(const UT_RNode< MAX_ORDER > shared_nodes[], const UT_RNode< MAX_ORDER > *const node)
Definition: UT_RTree.C:1057
GLuint start
Definition: glcorearb.h:474
GLdouble GLdouble GLdouble z
Definition: glcorearb.h:847
void setInternal(const bool isInternal)
Definition: UT_RTree.C:565
void UTappendIntersectingItemsBatch(UT_Array< int > *results, const UT_RTreeGeneric< MAX_ORDER > &tree, const QUERY_SHAPE *query_boxes, const UT_RTreeAssignmentT< BOXTYPE > &assignment)
Definition: UT_RTree.C:1294
void subtreeGetIntersectingItems(RESULT_ACCEPTOR &acceptor, const UT_RNode< MAX_ORDER > *const shared_nodes, const BOXTYPE *const shared_boxes, const UT_RNode< MAX_ORDER > *const node, const QUERY_SHAPE &query_box)
Definition: UT_RTree.C:942
static const Slot SLOT_MASK_INDEX
Definition: UT_RTree.C:646
void assignPoint(const U p[3])
Definition: UT_RTree.C:98
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
bool isEmpty() const
Definition: UT_RTree.C:66
uint32 Index
Definition: UT_RTree.C:545
GLint y
Definition: glcorearb.h:102
SYS_FORCE_INLINE T & x(void)
Definition: UT_Vector3.h:498
3D Vector class.
void assignSubtree(const int s, const int index_root_subtree)
Definition: UT_RTree.C:572
BOXTYPE boundingBox(const UT_RTreeAssignmentT< BOXTYPE > &assignment) const
Definition: UT_RTree.C:1365
png_uint_32 i
Definition: png.h:2877
bool intersects(const UT_BoxT< T > &b) const
Definition: UT_RTree.C:187
UT_RNode< MAX_ORDER > * subtreeCreate(BOXTYPE &bounding_box, BOXTYPE shared_boxes[], UT_BoxedItemT< BOXTYPE > *const begin, UT_BoxedItemT< BOXTYPE > *const end, UT_RNode< MAX_ORDER > *const shared_nodes, UT_RNode< MAX_ORDER > *&shared_nodes_end)
Definition: UT_RTree.C:755
GLsizeiptr size
Definition: glcorearb.h:663
void subtreeGetIntersectingItemsBatch(RESULT_ACCEPTOR &acceptor, const UT_RNode< MAX_ORDER > *const shared_nodes, const BOXTYPE *const shared_boxes, const UT_RNode< MAX_ORDER > *const node, const QUERY_SHAPE *query_boxes)
Definition: UT_RTree.C:996
void getIntersectingItemsBatch(RESULT_ACCEPTOR &batch_result_acceptor, const QUERY_SHAPE *query_box, const UT_RTreeAssignmentT< BOXTYPE > &assignment) const
Definition: UT_RTree.C:1211
SYS_FORCE_INLINE T & z(void)
Definition: UT_Vector3.h:502
void UTappendIntersectingItems(UT_Array< int > &results, const UT_RTreeGeneric< MAX_ORDER > &tree, const QUERY_SHAPE &query_box, const UT_RTreeAssignmentT< BOXTYPE > &assignment, exint baseindex)
Definition: UT_RTree.C:1306
int getLargestAxis() const
Definition: UT_RTree.C:388
Slot mySlots[MAX_ORDER]
Definition: UT_RTree.C:665
void absorbPoint(const U p[3])
Definition: UT_RTree.C:112
UT_BoxedItemAxisOrderT(const int axis)
Definition: UT_RTree.C:523
bool operator()(const UT_BoxedItemT< T > &a, const UT_BoxedItemT< T > &b)
Definition: UT_RTree.C:532
bool contains(const T *const p) const
Definition: UT_RTree.C:178
UT_BoxT()
Definition: UT_RTree.C:21
int64 exint
Definition: SYS_Types.h:116
const std::enable_if<!VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:133
Definition: VM_SIMD.h:48
void UTgetIntersectingItems(UT_Array< int > &results, const UT_RTreeGeneric< MAX_ORDER > &tree, const QUERY_SHAPE &query_box, const UT_RTreeAssignmentT< BOXTYPE > &assignment)
Definition: UT_RTree.C:1281
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:125
double fpreal64
Definition: SYS_Types.h:192
BOXTYPE Box
Definition: UT_RTree.C:456
GLuint GLuint end
Definition: glcorearb.h:474
GLintptr offset
Definition: glcorearb.h:664
void operator()(const int i)
Definition: UT_RTree.C:1237
Definition: VM_SIMD.h:180
void assignItem(const int s, const int item)
Definition: UT_RTree.C:586
void traverse(PRE_FUNCTOR &pre_functor, ITEM_FUNCTOR &item_functor, POST_FUNCTOR &post_functor, LOCAL_DATA *data_for_parent=nullptr) const
Definition: UT_RTree.C:1393
#define V4SF(A)
UT_RTreeResultAppenderIntArray(UT_Array< int > &results, exint baseindex)
Definition: UT_RTree.C:1231
int getNumItems() const
Definition: UT_RTree.C:879
~UT_RNode()
Definition: UT_RTree.C:552
int getSubtree(const int s) const
Definition: UT_RTree.C:607
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
bool intersects(const UT_VelBoxT< T > &b) const
Definition: UT_RTree.C:371
size_t subtreeDetermineNumNodes(const int MAX_ORDER, const size_t size)
Definition: UT_RTree.C:672
void getIntersectingItems(RESULT_ACCEPTOR &result_acceptor, const QUERY_SHAPE &query_box, const UT_RTreeAssignmentT< BOXTYPE > &assignment) const
Definition: UT_RTree.C:1191
T getMin(const int c) const
Definition: UT_RTree.C:332
SYS_FORCE_INLINE T & y(void)
Definition: UT_Vector3.h:500
int countNumItems() const
Definition: UT_RTree.C:618
void absorbBox(const UT_BoxT< T > &b)
Definition: UT_RTree.C:125
int getLargestAxis() const
Definition: UT_RTree.C:232
void computeBoundingBox(BOXTYPE &bounding_box, const BOXTYPE *const begin, const BOXTYPE *const end)
Definition: UT_RTree.C:483
T getMax(const int c) const
Definition: UT_RTree.C:342
bool isEmpty() const
Definition: UT_RTree.C:321
bool isInternal() const
Definition: UT_RTree.C:599
bool intersects(const Box< Vec3< T > > &b, const Line3< T > &r, Vec3< T > &ip)
Definition: ImathBoxAlgo.h:728
v4si vector
Definition: VM_SIMD.h:177
static const Slot SLOT_VALUE_EMPTY
Definition: UT_RTree.C:647
GLint GLenum GLint x
Definition: glcorearb.h:408
exint append(void)
Definition: UT_Array.h:95
SYS_FORCE_INLINE v4uf swizzle() const
Definition: VM_SIMD.h:323
void subtreeCreateAssignment(BOXTYPE &bounding_box, BOXTYPE *const shared_boxes, const UT_RNode< MAX_ORDER > *const shared_nodes, const UT_RNode< MAX_ORDER > *const node, const BOXTYPE item_boxes[])
Definition: UT_RTree.C:886
bool intersects(const UT_BoxT< T > &b) const
Definition: UT_RTree.C:430
Definition: ImathBox.h:72
T getMax(const int c) const
Definition: UT_RTree.C:87
UT_VelBoxT()
Definition: UT_RTree.C:272
void absorbBox(const UT_VelBoxT< T > &b)
Definition: UT_RTree.C:352
void operator()(const int batch, const int i)
Definition: UT_RTree.C:1263
void clear()
Definition: UT_RTree.C:556
UT_RNode()
Definition: UT_RTree.C:547
void clear()
Resets list to an empty list.
Definition: UT_Array.h:513
int getItem(const int s) const
Definition: UT_RTree.C:635
#define SYSmin(a, b)
Definition: SYS_Math.h:1368
void createAssignment(UT_RTreeAssignmentT< BOXTYPE > &assignment, const BOXTYPE item_boxes[]) const
Definition: UT_RTree.C:1155
Index Slot
Definition: UT_RTree.C:644
UT_RTreeResultAppenderBatchIntArray(UT_Array< int > *results, exint baseindex)
Definition: UT_RTree.C:1257
UT_Vector3T< T > getMin() const
Definition: UT_RTree.h:55
GLuint GLsizei GLsizei * length
Definition: glcorearb.h:794
UT_Vector3T< T > getMax() const
Definition: UT_RTree.h:57
unsigned int uint32
Definition: SYS_Types.h:36