HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_BVH.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: UT_BVH.h (UT Library, C++)
7  *
8  * COMMENTS: Bounding Volume Hierarchy (BVH) implementation.
9  * To call functions not implemented here, also include
10  * UT_BVHImpl.h
11  */
12 
13 #pragma once
14 
15 #ifndef __UT_BVH_h__
16 #define __UT_BVH_h__
17 
18 #include "UT_FixedVector.h"
19 #include "UT_SmallArray.h"
20 #include "UT_UniquePtr.h"
21 #include <SYS/SYS_Inline.h>
22 #include <SYS/SYS_StaticAssert.h>
23 #include <SYS/SYS_Types.h>
24 #include <SYS/SYS_TypeTraits.h>
25 #include <limits>
26 #include <stdlib.h>
27 
28 #define BVH_TRY_ALL_AXES 0
29 
30 template<typename T> class UT_Array;
31 class v4uf;
32 class v4uu;
33 
34 namespace UT {
35 
36 template<typename T,uint NAXES>
37 struct Box {
38  T vals[NAXES][2];
39 
40  SYS_FORCE_INLINE Box() noexcept = default;
41  SYS_FORCE_INLINE constexpr Box(const Box &other) noexcept = default;
42  SYS_FORCE_INLINE constexpr Box(Box &&other) noexcept = default;
43  SYS_FORCE_INLINE Box& operator=(const Box &other) noexcept = default;
44  SYS_FORCE_INLINE Box& operator=(Box &&other) noexcept = default;
45 
46  template<typename S>
47  SYS_FORCE_INLINE Box(const Box<S,NAXES>& other) noexcept {
48  SYS_STATIC_ASSERT_MSG((SYSisPOD<Box<T,NAXES>>()) || !SYSisPOD<T>(),
49  "UT::Box should be POD, for better performance in UT_Array, etc.");
50 
51  for (uint axis = 0; axis < NAXES; ++axis) {
52  vals[axis][0] = T(other.vals[axis][0]);
53  vals[axis][1] = T(other.vals[axis][1]);
54  }
55  }
56 
57  template< typename TS >
58  SYS_FORCE_INLINE explicit Box(const TS& pt) noexcept
59  {
60  SYS_STATIC_ASSERT( SYS_IsFixedArrayOf_v< TS, T, NAXES > );
61 
62  for (uint axis = 0; axis < NAXES; ++axis) {
63  vals[axis][0] = pt[axis];
64  vals[axis][1] = pt[axis];
65  }
66  }
67 
68  template<typename S>
69  SYS_FORCE_INLINE Box& operator=(const Box<S,NAXES>& other) noexcept {
70  for (uint axis = 0; axis < NAXES; ++axis) {
71  vals[axis][0] = T(other.vals[axis][0]);
72  vals[axis][1] = T(other.vals[axis][1]);
73  }
74  return *this;
75  }
76 
77  SYS_FORCE_INLINE const T* operator[](const size_t axis) const noexcept {
78  UT_ASSERT_P(axis < NAXES);
79  return vals[axis];
80  }
81  SYS_FORCE_INLINE T* operator[](const size_t axis) noexcept {
82  UT_ASSERT_P(axis < NAXES);
83  return vals[axis];
84  }
85 
86  SYS_FORCE_INLINE void initBounds() noexcept {
87  for (uint axis = 0; axis < NAXES; ++axis) {
88  vals[axis][0] = std::numeric_limits<T>::max();
89  vals[axis][1] = -std::numeric_limits<T>::max();
90  }
91  }
92  /// Copy the source box.
93  /// NOTE: This is so that in templated code that may have a Box or a
94  /// UT_FixedVector, it can call initBounds and still work.
95  SYS_FORCE_INLINE void initBounds(const Box<T,NAXES>& src) noexcept {
96  for (uint axis = 0; axis < NAXES; ++axis) {
97  vals[axis][0] = src.vals[axis][0];
98  vals[axis][1] = src.vals[axis][1];
99  }
100  }
101  /// Initialize with the union of the source boxes.
102  /// NOTE: This is so that in templated code that may have Box's or a
103  /// UT_FixedVector's, it can call initBounds and still work.
104  SYS_FORCE_INLINE void initBoundsUnordered(const Box<T,NAXES>& src0, const Box<T,NAXES>& src1) noexcept {
105  for (uint axis = 0; axis < NAXES; ++axis) {
106  vals[axis][0] = SYSmin(src0.vals[axis][0], src1.vals[axis][0]);
107  vals[axis][1] = SYSmax(src0.vals[axis][1], src1.vals[axis][1]);
108  }
109  }
110  SYS_FORCE_INLINE void combine(const Box<T,NAXES>& src) noexcept {
111  for (uint axis = 0; axis < NAXES; ++axis) {
112  T& minv = vals[axis][0];
113  T& maxv = vals[axis][1];
114  const T curminv = src.vals[axis][0];
115  const T curmaxv = src.vals[axis][1];
116  minv = (minv < curminv) ? minv : curminv;
117  maxv = (maxv > curmaxv) ? maxv : curmaxv;
118  }
119  }
121  combine(src);
122  }
123 
124  template< typename TS >
126  void initBounds(const TS& pt) noexcept
127  {
128  SYS_STATIC_ASSERT( SYS_IsFixedArrayOf_v< TS, T, NAXES > );
129 
130  for (uint axis = 0; axis < NAXES; ++axis) {
131  vals[axis][0] = pt[axis];
132  vals[axis][1] = pt[axis];
133  }
134  }
135 
136  template< typename TS >
139  const TS& min,
140  const TS& max
141  ) noexcept
142  {
143  SYS_STATIC_ASSERT( SYS_IsFixedArrayOf_v< TS, T, NAXES > );
144 
145  for (uint axis = 0; axis < NAXES; ++axis) {
146  vals[axis][0] = min[axis];
147  vals[axis][1] = max[axis];
148  }
149  }
150 
151  template< typename TS >
153  void initBoundsUnordered(const TS& p0, const TS& p1) noexcept
154  {
155  SYS_STATIC_ASSERT( SYS_IsFixedArrayOf_v< TS, T, NAXES > );
156 
157  for (uint axis = 0; axis < NAXES; ++axis) {
158  vals[axis][0] = SYSmin(p0[axis], p1[axis]);
159  vals[axis][1] = SYSmax(p0[axis], p1[axis]);
160  }
161  }
162 
163  template< typename TS >
165  void enlargeBounds(const TS& pt) noexcept
166  {
167  SYS_STATIC_ASSERT( SYS_IsFixedArrayOf_v< TS, T, NAXES > );
168 
169  for (uint axis = 0; axis < NAXES; ++axis) {
170  vals[axis][0] = SYSmin(vals[axis][0], pt[axis]);
171  vals[axis][1] = SYSmax(vals[axis][1], pt[axis]);
172  }
173  }
174 
175  template< typename TS >
176  SYS_FORCE_INLINE void combine(const TS& pt) noexcept
177  {
178  SYS_STATIC_ASSERT( SYS_IsFixedArrayOf_v< TS, T, NAXES > );
179 
180  enlargeBounds(pt);
181  }
182 
186  for (uint axis = 0; axis < NAXES; ++axis) {
187  v[axis] = vals[axis][0];
188  }
189  return v;
190  }
191 
195  for (uint axis = 0; axis < NAXES; ++axis) {
196  v[axis] = vals[axis][1];
197  }
198  return v;
199  }
200 
201  T diameter2() const noexcept {
202  T diff = (vals[0][1]-vals[0][0]);
203  T sum = diff*diff;
204  for (uint axis = 1; axis < NAXES; ++axis) {
205  diff = (vals[axis][1]-vals[axis][0]);
206  sum += diff*diff;
207  }
208  return sum;
209  }
210  T volume() const noexcept {
211  T product = (vals[0][1]-vals[0][0]);
212  for (uint axis = 1; axis < NAXES; ++axis) {
213  product *= (vals[axis][1]-vals[axis][0]);
214  }
215  return product;
216  }
217  T half_surface_area() const noexcept {
218  if (NAXES==1) {
219  // NOTE: Although this should technically be 1,
220  // that doesn't make any sense as a heuristic,
221  // so we fall back to the "volume" of this box.
222  return (vals[0][1]-vals[0][0]);
223  }
224  if (NAXES==2) {
225  const T d0 = (vals[0][1]-vals[0][0]);
226  const T d1 = (vals[1][1]-vals[1][0]);
227  return d0 + d1;
228  }
229  if (NAXES==3) {
230  const T d0 = (vals[0][1]-vals[0][0]);
231  const T d1 = (vals[1][1]-vals[1][0]);
232  const T d2 = (vals[2][1]-vals[2][0]);
233  return d0*d1 + d1*d2 + d2*d0;
234  }
235  if (NAXES==4) {
236  const T d0 = (vals[0][1]-vals[0][0]);
237  const T d1 = (vals[1][1]-vals[1][0]);
238  const T d2 = (vals[2][1]-vals[2][0]);
239  const T d3 = (vals[3][1]-vals[3][0]);
240  // This is just d0d1d2 + d1d2d3 + d2d3d0 + d3d0d1 refactored.
241  const T d0d1 = d0*d1;
242  const T d2d3 = d2*d3;
243  return d0d1*(d2+d3) + d2d3*(d0+d1);
244  }
245 
246  T sum = 0;
247  for (uint skipped_axis = 0; skipped_axis < NAXES; ++skipped_axis) {
248  T product = 1;
249  for (uint axis = 0; axis < NAXES; ++axis) {
250  if (axis != skipped_axis) {
251  product *= (vals[axis][1]-vals[axis][0]);
252  }
253  }
254  sum += product;
255  }
256  return sum;
257  }
258  T axis_sum() const noexcept {
259  T sum = (vals[0][1]-vals[0][0]);
260  for (uint axis = 1; axis < NAXES; ++axis) {
261  sum += (vals[axis][1]-vals[axis][0]);
262  }
263  return sum;
264  }
265 
267  T &box_tmin,
268  T &box_tmax,
269  const UT_FixedVector<uint,NAXES> &signs,
270  const UT_FixedVector<T,NAXES> &origin,
271  const UT_FixedVector<T,NAXES> &inverse_direction
272  ) const noexcept {
273  for (int axis = 0; axis < NAXES; ++axis)
274  {
275  uint sign = signs[axis];
276  T t1 = (vals[axis][sign] - origin[axis]) * inverse_direction[axis];
277  T t2 = (vals[axis][sign^1] - origin[axis]) * inverse_direction[axis];
278  box_tmin = SYSmax(t1, box_tmin);
279  box_tmax = SYSmin(t2, box_tmax);
280  }
281  }
282  /// Intersect the box expanded by the specified tolerance in all axes.
284  T &box_tmin,
285  T &box_tmax,
286  const UT_FixedVector<uint,NAXES> &signs,
287  const UT_FixedVector<T,NAXES> &origin,
288  const UT_FixedVector<T,NAXES> &inverse_direction,
289  T tolerance
290  ) const noexcept {
291  for (int axis = 0; axis < NAXES; ++axis)
292  {
293  uint sign = signs[axis];
294  T local_vals[2] = {
295  vals[axis][0] - tolerance,
296  vals[axis][1] + tolerance
297  };
298  T t1 = (local_vals[sign] - origin[axis]) * inverse_direction[axis];
299  T t2 = (local_vals[sign^1] - origin[axis]) * inverse_direction[axis];
300  box_tmin = SYSmax(t1, box_tmin);
301  box_tmax = SYSmin(t2, box_tmax);
302  }
303  }
304  SYS_FORCE_INLINE void intersect(const Box& other, Box& dest) const noexcept {
305  for (int axis = 0; axis < NAXES; ++axis)
306  {
307  dest.vals[axis][0] = SYSmax(vals[axis][0], other.vals[axis][0]);
308  dest.vals[axis][1] = SYSmin(vals[axis][1], other.vals[axis][1]);
309  }
310  }
311 
314  ) const noexcept {
315  T diff = SYSmax(SYSmax(vals[0][0]-p[0], p[0]-vals[0][1]), T(0.0f));
316  T d2 = diff*diff;
317  for (int axis = 1; axis < NAXES; ++axis)
318  {
319  diff = SYSmax(SYSmax(vals[axis][0]-p[axis], p[axis]-vals[axis][1]), T(0.0f));
320  d2 += diff*diff;
321  }
322  return d2;
323  }
324 
327  ) const noexcept {
328  T diff = SYSmax(p[0]-vals[0][0], vals[0][1]-p[0]);
329  T d2 = diff*diff;
330  for (int axis = 1; axis < NAXES; ++axis)
331  {
332  diff = SYSmax(p[axis]-vals[axis][0], vals[axis][1]-p[axis]);
333  d2 += diff*diff;
334  }
335  return d2;
336  }
337 
338  template< typename TS >
339  auto isInside(const TS &pt) const noexcept -> decltype(vals[0][0] <= pt[0])
340  {
341  SYS_STATIC_ASSERT( SYS_IsFixedArrayOf_v< TS, T, NAXES > );
342 
343  SYS_STATIC_ASSERT( NAXES == 3 );
344  return
345  vals[0][0] <= pt[0] && vals[0][1] >= pt[0] &&
346  vals[1][0] <= pt[1] && vals[1][1] >= pt[1] &&
347  vals[2][0] <= pt[2] && vals[2][1] >= pt[2];
348  }
349 };
350 
351 /// Used by BVH::init to specify the heuristic to use for choosing between different box splits.
352 /// I tried putting this inside the BVH class, but I had difficulty getting it to compile.
353 enum class BVH_Heuristic {
354  /// Tries to minimize the sum of axis lengths of the boxes.
355  /// This is useful for applications where the probability of a box being applicable to a
356  /// query is proportional to the "length", e.g. the probability of a random infinite plane
357  /// intersecting the box.
359 
360  /// Tries to minimize the "surface area" of the boxes.
361  /// In 3D, uses the surface area; in 2D, uses the perimeter; in 1D, uses the axis length.
362  /// This is what most applications, e.g. ray tracing, should use, particularly when the
363  /// probability of a box being applicable to a query is proportional to the surface "area",
364  /// e.g. the probability of a random ray hitting the box.
365  ///
366  /// NOTE: USE THIS ONE IF YOU ARE UNSURE!
367  BOX_AREA,
368 
369  /// Tries to minimize the "volume" of the boxes.
370  /// Uses the product of all axis lengths as a heuristic, (volume in 3D, area in 2D, length in 1D).
371  /// This is useful for applications where the probability of a box being applicable to a
372  /// query is proportional to the "volume", e.g. the probability of a random point being inside the box.
373  BOX_VOLUME,
374 
375  /// Tries to minimize the "radii" of the boxes (i.e. the distance from the centre to a corner).
376  /// This is useful for applications where the probability of a box being applicable to a
377  /// query is proportional to the distance to the box centre, e.g. the probability of a random
378  /// infinite plane being within the "radius" of the centre.
379  BOX_RADIUS,
380 
381  /// Tries to minimize the squared "radii" of the boxes (i.e. the squared distance from the centre to a corner).
382  /// This is useful for applications where the probability of a box being applicable to a
383  /// query is proportional to the squared distance to the box centre, e.g. the probability of a random
384  /// ray passing within the "radius" of the centre.
385  BOX_RADIUS2,
386 
387  /// Tries to minimize the cubed "radii" of the boxes (i.e. the cubed distance from the centre to a corner).
388  /// This is useful for applications where the probability of a box being applicable to a
389  /// query is proportional to the cubed distance to the box centre, e.g. the probability of a random
390  /// point being within the "radius" of the centre.
391  BOX_RADIUS3,
392 
393  /// Tries to minimize the depth of the tree by primarily splitting at the median of the max axis.
394  /// It may fall back to minimizing the area, but the tree depth should be unaffected.
395  ///
396  /// FIXME: This is not fully implemented yet.
398 };
399 
400 template<uint N>
401 class BVH {
402 public:
403  using INT_TYPE = uint;
404  struct Node {
406 
407  static constexpr INT_TYPE theN = N;
408  static constexpr INT_TYPE EMPTY = INT_TYPE(-1);
409  static constexpr INT_TYPE INTERNAL_BIT = (INT_TYPE(1)<<(sizeof(INT_TYPE)*8 - 1));
410  SYS_FORCE_INLINE static INT_TYPE markInternal(INT_TYPE internal_node_num) noexcept {
411  return internal_node_num | INTERNAL_BIT;
412  }
413  SYS_FORCE_INLINE static bool isInternal(INT_TYPE node_int) noexcept {
414  return (node_int & INTERNAL_BIT) != 0;
415  }
416  SYS_FORCE_INLINE static INT_TYPE getInternalNum(INT_TYPE node_int) noexcept {
417  return node_int & ~INTERNAL_BIT;
418  }
419  };
420 private:
421  struct FreeDeleter {
422  SYS_FORCE_INLINE void operator()(Node* p) const {
423  if (p) {
424  // The pointer was allocated with malloc by UT_Array,
425  // so it must be freed with free.
426  free(p);
427  }
428  }
429  };
430 
432  INT_TYPE myNumNodes;
433 public:
434  SYS_FORCE_INLINE BVH() noexcept : myRoot(nullptr), myNumNodes(0) {}
435 
436  template<BVH_Heuristic H,typename T,uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE=INT_TYPE>
437  void init(const BOX_TYPE* boxes, const INT_TYPE nboxes, SRC_INT_TYPE* indices=nullptr, bool reorder_indices=false, INT_TYPE max_items_per_leaf=1) noexcept;
438 
439  template<BVH_Heuristic H,typename T,uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE=INT_TYPE>
440  void init(Box<T,NAXES> axes_minmax, const BOX_TYPE* boxes, INT_TYPE nboxes, SRC_INT_TYPE* indices=nullptr, bool reorder_indices=false, INT_TYPE max_items_per_leaf=1) noexcept;
441 
444  {
445  return myNumNodes;
446  }
448  const Node *getNodes() const noexcept
449  {
450  return myRoot.get();
451  }
452 
453  /// Returns the maximum depth of any leaf
454  int getMaxDepth() const noexcept;
455 
456  /// Returns the minimum depth of the first non-internal node.
457  int getPureInternalDepth() const noexcept;
458 
460  void clear() noexcept {
461  myRoot.reset();
462  myNumNodes = 0;
463  }
464 
465  /// For each node, this effectively does:
466  /// LOCAL_DATA local_data[MAX_ORDER];
467  /// bool descend = functors.pre(nodei, parent_data);
468  /// if (!descend)
469  /// return;
470  /// for each child {
471  /// if (isitem(child))
472  /// functors.item(getitemi(child), nodei, local_data[child]);
473  /// else if (isnode(child))
474  /// recurse(getnodei(child), local_data);
475  /// }
476  /// functors.post(nodei, parent_nodei, data_for_parent, num_children, local_data);
477  template<typename LOCAL_DATA,typename FUNCTORS>
478  void traverse(
479  FUNCTORS &functors,
480  LOCAL_DATA *data_for_parent=nullptr) const noexcept;
481 
482  /// This acts like the traverse function, except if the number of nodes in two subtrees
483  /// of a node contain at least parallel_threshold nodes, they may be executed in parallel.
484  /// If parallel_threshold is 0, even item_functor may be executed on items in parallel.
485  /// NOTE: Make sure that your functors don't depend on the order that they're executed in,
486  /// e.g. don't add values from sibling nodes together except in post functor,
487  /// else they might have nondeterministic roundoff or miss some values entirely.
488  template<typename LOCAL_DATA,typename FUNCTORS>
489  void traverseParallel(
490  INT_TYPE parallel_threshold,
491  FUNCTORS &functors,
492  LOCAL_DATA *data_for_parent=nullptr) const noexcept;
493 
494  /// For each node, this effectively does:
495  /// LOCAL_DATA local_data[MAX_ORDER];
496  /// uint descend = functors.pre(nodei, parent_data);
497  /// if (!descend)
498  /// return;
499  /// for each child {
500  /// if (!(descend & (1<<child)))
501  /// continue;
502  /// if (isitem(child))
503  /// functors.item(getitemi(child), nodei, local_data[child]);
504  /// else if (isnode(child))
505  /// recurse(getnodei(child), local_data);
506  /// }
507  /// functors.post(nodei, parent_nodei, data_for_parent, num_children, local_data);
508  template<typename LOCAL_DATA,typename FUNCTORS>
509  void traverseVector(
510  FUNCTORS &functors,
511  LOCAL_DATA *data_for_parent=nullptr) const noexcept;
512 
513  /// Prints a text representation of the tree to stdout.
514  void debugDump() const;
515 
516  template<typename SRC_INT_TYPE>
517  static void createTrivialIndices(SRC_INT_TYPE* indices, const INT_TYPE n) noexcept;
518 
519 private:
520  template<typename LOCAL_DATA,typename FUNCTORS>
521  void traverseHelper(
522  INT_TYPE nodei,
523  INT_TYPE parent_nodei,
524  FUNCTORS &functors,
525  LOCAL_DATA *data_for_parent=nullptr) const noexcept;
526 
527  template<typename LOCAL_DATA,typename FUNCTORS>
528  void traverseParallelHelper(
529  INT_TYPE nodei,
530  INT_TYPE parent_nodei,
531  INT_TYPE parallel_threshold,
532  INT_TYPE next_node_id,
533  FUNCTORS &functors,
534  LOCAL_DATA *data_for_parent=nullptr) const noexcept;
535 
536  template<typename LOCAL_DATA,typename FUNCTORS>
537  void traverseVectorHelper(
538  INT_TYPE nodei,
539  INT_TYPE parent_nodei,
540  FUNCTORS &functors,
541  LOCAL_DATA *data_for_parent=nullptr) const noexcept;
542 
543  template<typename T,uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
544  static void computeFullBoundingBox(Box<T,NAXES>& axes_minmax, const BOX_TYPE* boxes, const INT_TYPE nboxes, SRC_INT_TYPE* indices) noexcept;
545 
546  template<BVH_Heuristic H,typename T,uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
547  static void initNode(UT_Array<Node>& nodes, Node &node, const Box<T,NAXES>& axes_minmax, const BOX_TYPE* boxes, SRC_INT_TYPE* indices, const INT_TYPE nboxes) noexcept;
548 
549  template<BVH_Heuristic H,typename T,uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
550  static void initNodeReorder(UT_Array<Node>& nodes, Node &node, const Box<T,NAXES>& axes_minmax, const BOX_TYPE* boxes, SRC_INT_TYPE* indices, const INT_TYPE nboxes, const INT_TYPE indices_offset, const INT_TYPE max_items_per_leaf) noexcept;
551 
552  template<BVH_Heuristic H,typename T,uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
553  static void multiSplit(const Box<T,NAXES>& axes_minmax, const BOX_TYPE* boxes, SRC_INT_TYPE* indices, INT_TYPE nboxes, SRC_INT_TYPE* sub_indices[N+1], Box<T,NAXES> sub_boxes[N]) noexcept;
554 
555  template<BVH_Heuristic H,typename T,uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
556  static void split(const Box<T,NAXES>& axes_minmax, const BOX_TYPE* boxes, SRC_INT_TYPE* indices, INT_TYPE nboxes, SRC_INT_TYPE*& split_indices, Box<T,NAXES>* split_boxes) noexcept;
557 
558 #if BVH_TRY_ALL_AXES
559  template<BVH_Heuristic H,typename T,uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
560  static void splitMiddleCountAxis(const INT_TYPE axis, T &best_heuristic, const BOX_TYPE* boxes, SRC_INT_TYPE* indices, INT_TYPE nboxes, SRC_INT_TYPE*& split_indices, Box<T,NAXES>* split_boxes) noexcept;
561 
562  template<BVH_Heuristic H,typename T,uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
563  static void splitLargeCountAxis(
564  const INT_TYPE axis, const T axis_min, const T axis_length,
565  T &best_heuristic, INT_TYPE &best_axis, INT_TYPE &best_split_index,
566  Box<T,NAXES> &best_left_split_box,
567  Box<T,NAXES> &best_right_split_box,
568  INT_TYPE &best_left_count_split,
569  INT_TYPE &maxaxis_first_left_count,
570  INT_TYPE &maxaxis_last_left_count,
571  const BOX_TYPE* boxes, SRC_INT_TYPE* indices, INT_TYPE nboxes) noexcept;
572 #endif
573 
574  template<INT_TYPE PARALLEL_THRESHOLD, typename SRC_INT_TYPE>
575  static void adjustParallelChildNodes(INT_TYPE nparallel, UT_Array<Node>& nodes, Node& node, UT_Array<Node>* parallel_nodes, SRC_INT_TYPE* sub_indices) noexcept;
576 
577  template<typename T,typename BOX_TYPE,typename SRC_INT_TYPE>
578  static void nthElement(const BOX_TYPE* boxes, SRC_INT_TYPE* indices, const SRC_INT_TYPE* indices_end, const uint axis, SRC_INT_TYPE*const nth) noexcept;
579 
580  template<typename T,typename BOX_TYPE,typename SRC_INT_TYPE>
581  static void partitionByCentre(const BOX_TYPE* boxes, SRC_INT_TYPE*const indices, const SRC_INT_TYPE*const indices_end, const uint axis, const T pivotx2, SRC_INT_TYPE*& ppivot_start, SRC_INT_TYPE*& ppivot_end) noexcept;
582 
583  /// An overestimate of the number of nodes needed.
584  /// At worst, we could have only 2 children in every leaf, and
585  /// then above that, we have a geometric series with r=1/N and a=(sub_nboxes/2)/N
586  /// The true worst case might be a little worst than this, but
587  /// it's probably fairly unlikely.
588  SYS_FORCE_INLINE static INT_TYPE nodeEstimate(const INT_TYPE nboxes) noexcept {
589  return nboxes/2 + nboxes/(2*(N-1));
590  }
591 
592  template<BVH_Heuristic H,typename T, uint NAXES>
593  SYS_FORCE_INLINE static T unweightedHeuristic(const Box<T, NAXES>& box) noexcept {
594  if (H == BVH_Heuristic::BOX_PERIMETER) {
595  return box.axis_sum();
596  }
597  if (H == BVH_Heuristic::BOX_AREA) {
598  return box.half_surface_area();
599  }
600  if (H == BVH_Heuristic::BOX_VOLUME) {
601  return box.volume();
602  }
603  if (H == BVH_Heuristic::BOX_RADIUS) {
604  T diameter2 = box.diameter2();
605  return SYSsqrt(diameter2);
606  }
607  if (H == BVH_Heuristic::BOX_RADIUS2) {
608  return box.diameter2();
609  }
610  if (H == BVH_Heuristic::BOX_RADIUS3) {
611  T diameter2 = box.diameter2();
612  return diameter2*SYSsqrt(diameter2);
613  }
614  UT_ASSERT_MSG(0, "BVH_Heuristic::MEDIAN_MAX_AXIS should be handled separately by caller!");
615  return T(1);
616  }
617 
618  int getMaxDepthHelper(INT_TYPE curnode, int depth) const noexcept;
619  int getPureInternalDepthHelper(INT_TYPE curnode, int depth) const noexcept;
620 
621  /// 16 equal-length spans (15 evenly-spaced splits) should be enough for a decent heuristic
622  static constexpr INT_TYPE NSPANS = 16;
623  static constexpr INT_TYPE NSPLITS = NSPANS-1;
624 
625  /// At least 1/16 of all boxes must be on each side, else we could end up with a very deep tree
626  static constexpr INT_TYPE MIN_FRACTION = 16;
627 };
628 
629 /// Fills in node_boxes, possibly in parallel if there are enough nodes.
630 /// ITEM_BOX should act like UT::Box<T,NAXES>, and the length should be the number of items.
631 /// NODE_BOX should act like UT::Box<T,NAXES>, and the length should be bvh.getNumNodes().
632 template<uint BVH_N,typename ITEM_BOX,typename NODE_BOX>
634  const UT::BVH<BVH_N>& bvh,
635  const ITEM_BOX* item_boxes,
636  NODE_BOX* node_boxes) noexcept;
637 
638 /// Fills in node_boxes as interleaved child boxes, possibly in parallel if there are enough nodes.
639 /// ITEM_BOX should act like UT::Box<T,NAXES>, and the length should be the number of items.
640 /// NODE_BOX should act like UT::Box<v4uf,NAXES> or UT::Box<UT_FixedVector<T,BVH_N>,NAXES>, and the length should be bvh.getNumNodes().
641 template<uint NAXES,typename T,uint BVH_N,typename ITEM_BOX,typename NODE_BOX>
643  const UT::BVH<BVH_N>& bvh,
644  const ITEM_BOX* item_boxes,
645  NODE_BOX* node_boxes,
646  float expand_factor=0.0f) noexcept;
647 
648 /// Fills in node_boxes as interleaved child boxes, possibly in parallel if there are enough nodes.
649 /// ITEM_BOX should act like UT::Box<T,NAXES> or UT_FixedVector<T,NAXES>, and the length should be the number of items.
650 /// NODE_BOX should act like UT::Box<v4uf,NAXES> or UT::Box<UT_FixedVector<T,4>,NAXES>, and the length should be bvh.getNumNodes().
651 template<uint NAXES,typename T,typename ITEM_BOX,typename NODE_BOX,typename INT_TYPE0=uint>
653  const UT::BVH<4>& bvh,
654  const ITEM_BOX* item_boxes,
655  NODE_BOX* node_boxes,
656  const v4uu* node_nitems,
657  const INT_TYPE0* indices_mapping=nullptr) noexcept;
658 
659 using BVHUnorderedStack = UT_Array<UT::BVH<4>::INT_TYPE>;
660 using BVHUnorderedStackSmall = UT_SmallArray<UT::BVH<4>::INT_TYPE,128>;
661 
662 /// Fills box_indices array with the indices of all boxes intersecting query_box.
663 /// NOTE: This does not clear out previous contents of indices, so that you
664 /// can easily query intersection with multiple boxes.
665 /// WARNING: DO NOT depend on the order of box_indices. If you need a consistent order, sort it.
666 template<uint NAXES,typename INT_TYPE>
668  const UT::BVH<4>& bvh,
669  const UT::Box<v4uf,NAXES>* node_boxes,
670  const UT::Box<float,NAXES>& query_box,
671  UT_Array<INT_TYPE>& box_indices,
672  BVHUnorderedStack& stack) noexcept;
673 
674 template<uint NAXES,typename INT_TYPE>
676  const UT::BVH<4>& bvh,
677  const UT::Box<v4uf,NAXES>* node_boxes,
678  const UT::Box<float,NAXES>& query_box,
679  UT_Array<INT_TYPE>& box_indices,
680  BVHUnorderedStack& stack) noexcept;
681 
682 template<uint NAXES,typename INT_TYPE>
684  const UT::BVH<4>& bvh,
685  const UT::Box<v4uf,NAXES>* node_boxes,
686  const UT::Box<float,NAXES>& query_box,
687  UT_Array<INT_TYPE>& box_indices,
688  BVHUnorderedStack& stack) noexcept;
689 
690 template<uint NAXES,typename INT_TYPE, int BATCH_SIZE>
692  const UT::BVH<4>& bvh,
693  const UT::Box<v4uf,NAXES>* node_boxes,
694  const UT::Box<float,NAXES> *query_box,
695  UT_Array<INT_TYPE> *box_indices,
696  BVHUnorderedStack& stack) noexcept;
697 
698 /// Computes the number of items per node entry and fills in node_nitems.
699 inline void computeNodeNItems(
700  const UT::BVH<4>& bvh,
701  v4uu* node_nitems,
702  exint nitems) noexcept;
703 
707 
708  SYS_FORCE_INLINE BVHOrderedStackEntry() noexcept = default;
709  SYS_FORCE_INLINE BVHOrderedStackEntry(const BVHOrderedStackEntry& other) noexcept = default;
710  SYS_FORCE_INLINE BVHOrderedStackEntry(BVHOrderedStackEntry&& other) noexcept = default;
711  SYS_FORCE_INLINE BVHOrderedStackEntry& operator=(const BVHOrderedStackEntry& other) noexcept = default;
712  SYS_FORCE_INLINE BVHOrderedStackEntry& operator=(BVHOrderedStackEntry&& other) noexcept = default;
713  SYS_FORCE_INLINE explicit BVHOrderedStackEntry(float dist_squared, UT::BVH<4>::INT_TYPE node) noexcept
714  : myDistSquared(dist_squared)
715  , myNode(node)
716  {}
717  SYS_FORCE_INLINE bool operator<(const BVHOrderedStackEntry& other) const {
718  return (myDistSquared < other.myDistSquared) ||
719  ((myDistSquared == other.myDistSquared) && (myNode < other.myNode));
720  }
721  SYS_FORCE_INLINE bool operator<=(const BVHOrderedStackEntry& other) const {
722  return (myDistSquared < other.myDistSquared) ||
723  ((myDistSquared == other.myDistSquared) && (myNode <= other.myNode));
724  }
725  SYS_FORCE_INLINE bool operator>(const BVHOrderedStackEntry& other) const {
726  return (myDistSquared > other.myDistSquared) ||
727  ((myDistSquared == other.myDistSquared) && (myNode > other.myNode));
728  }
729  SYS_FORCE_INLINE bool operator>=(const BVHOrderedStackEntry& other) const {
730  return (myDistSquared > other.myDistSquared) ||
731  ((myDistSquared == other.myDistSquared) && (myNode >= other.myNode));
732  }
733  SYS_FORCE_INLINE bool operator==(const BVHOrderedStackEntry& other) const {
734  return (myDistSquared == other.myDistSquared) &&
735  (myNode == other.myNode);
736  }
737  SYS_FORCE_INLINE bool operator!=(const BVHOrderedStackEntry& other) const {
738  return !(*this == other);
739  }
740 };
743 
745  constexpr ZeroRadiiWrapper() = default;
746  constexpr ZeroRadiiWrapper(const ZeroRadiiWrapper&) = default;
747  constexpr float operator[](exint i) const noexcept {
748  return 0.0f;
749  }
750 };
751 
753  const float myRadius;
754  SYS_FORCE_INLINE constexpr
755  SingleRadiusWrapper(const float radius)
756  : myRadius(radius)
757  {}
758  SYS_FORCE_INLINE constexpr
759  float operator[](exint i) const noexcept {
760  return myRadius;
761  }
762 };
763 
764 template<typename T>
765 constexpr bool allRadiiZero(const T& array) noexcept { return false; }
766 
767 constexpr bool allRadiiZero(const ZeroRadiiWrapper& array) noexcept { return true; }
768 
769 template<typename T>
770 constexpr bool allRadiiZero(const T*const array) noexcept { return !array; }
771 
772 template<typename QUERY_POINT>
774  QUERY_POINT &myQueryPoint;
775 
776  /// isValid() doesn't need to be called if theAllPointsValid is true.
777  static constexpr bool theAllPointsValid = QUERY_POINT::theAllPointsValid;
778 
780  BVHQueryPointWrapper(QUERY_POINT& query_point)
781  : myQueryPoint(query_point)
782  {}
783 
784  /// NOTE: This doesn't necessarily need to be const, for subclasses that have
785  /// a limit on the number of invalid points hit before giving up, for example.
787  bool isValid(uint tree_point_index) const {
788  return myQueryPoint.isValid(tree_point_index);
789  }
790 
791  /// This must be the exact distance squared.
792  template<typename POSITION,typename RADIUS_ARRAY>
794  float queryDistance2(const POSITION& tree_point, const RADIUS_ARRAY& radii, uint index) const {
795  return myQueryPoint.queryDistance2(tree_point, radii, index);
796  }
797 
798  /// The distance squared can be an underestimate, but not an overestimate,
799  /// of the true distance squared. The reverse is the case if farthest is true.
800  /// Also, if farthest is true, max_dist_squared is actually min_dist_squared.
801  template<bool farthest,uint NAXES>
803  uint boxHitAndDist2(const UT::Box<v4uf,NAXES>& boxes, const float max_dist_squared, const uint internal_node_num, v4uf& dist2) const {
804  return myQueryPoint.template boxHitAndDist2<farthest>(boxes, max_dist_squared, internal_node_num, dist2);
805  }
806 };
807 
808 /// NOTE: If farthest is true, max_dist_squared is actually min_dist_squared.
809 /// NOTE: If indices_mapping is non-null, it maps from BVH item indices to
810 /// indices into positions and radii.
811 /// NOTE: If reordered is true, item indices in bvh must be monotone strictly
812 /// increasing, but may not be contiguous, so that multiple points can be
813 /// in the same leaf. This is independent of whether indices_mapping is
814 /// valid, but no mapping means that positions and radii would have to be
815 /// reordered too.
816 template<bool farthest,bool reordered,bool use_max_points,uint NAXES,typename QUERY_POINT,typename INT_TYPE0,typename POSITION_ARRAY,typename RADIUS_ARRAY>
817 void findClosestPoints(
818  const UT::BVH<4>& bvh,
819  const UT::Box<v4uf,NAXES>* node_boxes,
820  const v4uu* node_nitems,
821  const INT_TYPE0* indices_mapping,
822  const POSITION_ARRAY& positions,
823  QUERY_POINT& query_point,
824  BVHOrderedStack& stack,
825  BVHOrderedStack& output_queue,
826  const RADIUS_ARRAY& radii = ZeroRadiiWrapper(),
827  exint max_points = std::numeric_limits<exint>::max(),
828  float max_dist_squared = std::numeric_limits<float>::max()) noexcept;
829 
830 } // UT namespace
831 
832 template<uint N>
833 using UT_BVH = UT::BVH<N>;
834 
835 #undef BVH_TRY_ALL_AXES
836 
837 #endif
SYS_FORCE_INLINE bool operator==(const BVHOrderedStackEntry &other) const
Definition: UT_BVH.h:733
#define SYSmax(a, b)
Definition: SYS_Math.h:1513
SYS_FORCE_INLINE uint boxHitAndDist2(const UT::Box< v4uf, NAXES > &boxes, const float max_dist_squared, const uint internal_node_num, v4uf &dist2) const
Definition: UT_BVH.h:803
#define SYS_STATIC_ASSERT(expr)
constexpr bool allRadiiZero(const T &array) noexcept
Definition: UT_BVH.h:765
static constexpr INT_TYPE EMPTY
Definition: UT_BVH.h:408
void findClosestPoints(const UT::BVH< 4 > &bvh, const UT::Box< v4uf, NAXES > *node_boxes, const v4uu *node_nitems, const INT_TYPE0 *indices_mapping, const POSITION_ARRAY &positions, QUERY_POINT &query_point, BVHOrderedStack &stack, BVHOrderedStack &output_queue, const RADIUS_ARRAY &radii=ZeroRadiiWrapper(), exint max_points=std::numeric_limits< exint >::max(), float max_dist_squared=std::numeric_limits< float >::max()) noexcept
Definition: UT_BVHImpl.h:4039
SYS_FORCE_INLINE void combine(const TS &pt) noexcept
Definition: UT_BVH.h:176
SYS_FORCE_INLINE void intersect(const Box &other, Box &dest) const noexcept
Definition: UT_BVH.h:304
void traverseParallel(INT_TYPE parallel_threshold, FUNCTORS &functors, LOCAL_DATA *data_for_parent=nullptr) const noexcept
Definition: UT_BVHImpl.h:471
#define SYS_STATIC_ASSERT_MSG(expr, msg)
Definition: UT_BVH.h:37
INT_TYPE child[N]
Definition: UT_BVH.h:405
Definition: Node.h:52
T half_surface_area() const noexcept
Definition: UT_BVH.h:217
static SYS_FORCE_INLINE INT_TYPE markInternal(INT_TYPE internal_node_num) noexcept
Definition: UT_BVH.h:410
int getPureInternalDepth() const noexcept
Returns the minimum depth of the first non-internal node.
Definition: UT_BVHImpl.h:418
SYS_FORCE_INLINE bool operator!=(const BVHOrderedStackEntry &other) const
Definition: UT_BVH.h:737
int64 exint
Definition: SYS_Types.h:125
SYS_FORCE_INLINE void initBounds(const Box< T, NAXES > &src) noexcept
Definition: UT_BVH.h:95
SYS_FORCE_INLINE UT_FixedVector< T, NAXES > getMin() const noexcept
Definition: UT_BVH.h:184
SYS_FORCE_INLINE constexpr SingleRadiusWrapper(const float radius)
Definition: UT_BVH.h:755
ImageBuf OIIO_API min(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
SYS_FORCE_INLINE void initBounds() noexcept
Definition: UT_BVH.h:86
GLuint GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat t1
Definition: glew.h:12900
SYS_FORCE_INLINE void enlargeBounds(const TS &pt) noexcept
Definition: UT_BVH.h:165
SYS_FORCE_INLINE BVHQueryPointWrapper(QUERY_POINT &query_point)
Definition: UT_BVH.h:780
SYS_FORCE_INLINE UT_FixedVector< T, NAXES > getMax() const noexcept
Definition: UT_BVH.h:193
SYS_FORCE_INLINE bool operator>(const BVHOrderedStackEntry &other) const
Definition: UT_BVH.h:725
int getMaxDepth() const noexcept
Returns the maximum depth of any leaf.
Definition: UT_BVHImpl.h:362
GLenum src
Definition: glcorearb.h:1793
SYS_FORCE_INLINE constexpr float operator[](exint i) const noexcept
Definition: UT_BVH.h:759
std::unique_ptr< T, Deleter > UT_UniquePtr
A smart pointer for unique ownership of dynamically allocated objects.
Definition: UT_UniquePtr.h:39
void getIntersectingBoxesFromStack(const UT::BVH< 4 > &bvh, const UT::Box< v4uf, NAXES > *node_boxes, const UT::Box< float, NAXES > &query_box, UT_Array< INT_TYPE > &box_indices, BVHUnorderedStack &stack) noexcept
Definition: UT_BVHImpl.h:2467
SYS_FORCE_INLINE T minDistance2(const UT_FixedVector< T, NAXES > &p) const noexcept
Definition: UT_BVH.h:312
#define UT_ASSERT_MSG(ZZ,...)
Definition: UT_Assert.h:156
SYS_FORCE_INLINE void clear() noexcept
Definition: UT_BVH.h:460
float myDistSquared
Definition: UT_BVH.h:705
GLint GLint GLsizei GLsizei GLsizei depth
Definition: glcorearb.h:476
SYS_FORCE_INLINE T * operator[](const size_t axis) noexcept
Definition: UT_BVH.h:81
GLenum array
Definition: glew.h:9108
T axis_sum() const noexcept
Definition: UT_BVH.h:258
UT::BVH< 4 >::INT_TYPE myNode
Definition: UT_BVH.h:706
void computeNodeNItems(const UT::BVH< 4 > &bvh, v4uu *node_nitems, exint nitems) noexcept
Computes the number of items per node entry and fills in node_nitems.
Definition: UT_BVHImpl.h:3011
SYS_FORCE_INLINE void initBounds(const TS &min, const TS &max) noexcept
Definition: UT_BVH.h:138
void getIntersectingNodes(const UT::BVH< 4 > &bvh, const UT::Box< v4uf, NAXES > *node_boxes, const UT::Box< float, NAXES > &query_box, UT_Array< INT_TYPE > &box_indices, BVHUnorderedStack &stack) noexcept
Definition: UT_BVHImpl.h:2609
QUERY_POINT & myQueryPoint
Definition: UT_BVH.h:774
SYS_FORCE_INLINE Box() noexcept=default
SYS_FORCE_INLINE bool operator>=(const BVHOrderedStackEntry &other) const
Definition: UT_BVH.h:729
SYS_FORCE_INLINE T maxDistance2(const UT_FixedVector< T, NAXES > &p) const noexcept
Definition: UT_BVH.h:325
SYS_FORCE_INLINE bool operator<=(const BVHOrderedStackEntry &other) const
Definition: UT_BVH.h:721
Definition: VM_SIMD.h:48
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:152
SYS_FORCE_INLINE const Node * getNodes() const noexcept
Definition: UT_BVH.h:448
void debugDump() const
Prints a text representation of the tree to stdout.
const GLdouble * v
Definition: glcorearb.h:837
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
GLsizei GLenum const void * indices
Definition: glcorearb.h:406
SYS_FORCE_INLINE BVH() noexcept
Definition: UT_BVH.h:434
Definition: VM_SIMD.h:188
T diameter2() const noexcept
Definition: UT_BVH.h:201
SYS_FORCE_INLINE void createBVHNodeBoxes(const UT::BVH< BVH_N > &bvh, const ITEM_BOX *item_boxes, NODE_BOX *node_boxes) noexcept
Definition: UT_BVHImpl.h:2094
SYS_FORCE_INLINE void createBVHInterleavedBoxes(const UT::BVH< BVH_N > &bvh, const ITEM_BOX *item_boxes, NODE_BOX *node_boxes, float expand_factor=0.0f) noexcept
Definition: UT_BVHImpl.h:2139
GLfloat GLfloat p
Definition: glew.h:16656
STATIC_INLINE uint64_t H(uint64_t x, uint64_t y, uint64_t mul, int r)
Definition: farmhash.h:701
IMATH_HOSTDEVICE constexpr int sign(T a) IMATH_NOEXCEPT
Definition: ImathFun.h:33
auto isInside(const TS &pt) const noexcept-> decltype(vals[0][0]<=pt[0])
Definition: UT_BVH.h:339
T vals[NAXES][2]
Definition: UT_BVH.h:38
void init(const BOX_TYPE *boxes, const INT_TYPE nboxes, SRC_INT_TYPE *indices=nullptr, bool reorder_indices=false, INT_TYPE max_items_per_leaf=1) noexcept
Definition: UT_BVHImpl.h:274
void traverse(FUNCTORS &functors, LOCAL_DATA *data_for_parent=nullptr) const noexcept
Definition: UT_BVHImpl.h:428
GLdouble n
Definition: glcorearb.h:2008
static void createTrivialIndices(SRC_INT_TYPE *indices, const INT_TYPE n) noexcept
Definition: UT_BVHImpl.h:642
static constexpr bool theAllPointsValid
isValid() doesn't need to be called if theAllPointsValid is true.
Definition: UT_BVH.h:777
static SYS_FORCE_INLINE INT_TYPE getInternalNum(INT_TYPE node_int) noexcept
Definition: UT_BVH.h:416
GLsizei const GLint box[]
Definition: glew.h:11654
SYS_FORCE_INLINE float queryDistance2(const POSITION &tree_point, const RADIUS_ARRAY &radii, uint index) const
This must be the exact distance squared.
Definition: UT_BVH.h:794
SYS_FORCE_INLINE Box & operator=(const Box< S, NAXES > &other) noexcept
Definition: UT_BVH.h:69
SYS_FORCE_INLINE void intersectTol(T &box_tmin, T &box_tmax, const UT_FixedVector< uint, NAXES > &signs, const UT_FixedVector< T, NAXES > &origin, const UT_FixedVector< T, NAXES > &inverse_direction, T tolerance) const noexcept
Intersect the box expanded by the specified tolerance in all axes.
Definition: UT_BVH.h:283
void getIntersectingBoxesBatch(const UT::BVH< 4 > &bvh, const UT::Box< v4uf, NAXES > *node_boxes, const UT::Box< float, NAXES > *query_box, UT_Array< INT_TYPE > *box_indices, BVHUnorderedStack &stack) noexcept
Definition: UT_BVHImpl.h:2756
UT_Array< BVHOrderedStackEntry > BVHOrderedStack
Definition: UT_BVH.h:741
SYS_FORCE_INLINE void initBounds(const TS &pt) noexcept
Definition: UT_BVH.h:126
GLuint index
Definition: glcorearb.h:786
SYS_FORCE_INLINE INT_TYPE getNumNodes() const noexcept
Definition: UT_BVH.h:443
ImageBuf OIIO_API max(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
GA_API const UT_StringHolder N
SYS_FORCE_INLINE void initBoundsUnordered(const TS &p0, const TS &p1) noexcept
Definition: UT_BVH.h:153
SYS_FORCE_INLINE void intersect(T &box_tmin, T &box_tmax, const UT_FixedVector< uint, NAXES > &signs, const UT_FixedVector< T, NAXES > &origin, const UT_FixedVector< T, NAXES > &inverse_direction) const noexcept
Definition: UT_BVH.h:266
GLfloat f
Definition: glcorearb.h:1926
static constexpr INT_TYPE INTERNAL_BIT
Definition: UT_BVH.h:409
static constexpr INT_TYPE theN
Definition: UT_BVH.h:407
Definition: ImathBox.h:37
SYS_FORCE_INLINE void initBoundsUnordered(const Box< T, NAXES > &src0, const Box< T, NAXES > &src1) noexcept
Definition: UT_BVH.h:104
T volume() const noexcept
Definition: UT_BVH.h:210
void getIntersectingBoxes(const UT::BVH< 4 > &bvh, const UT::Box< v4uf, NAXES > *node_boxes, const UT::Box< float, NAXES > &query_box, UT_Array< INT_TYPE > &box_indices, BVHUnorderedStack &stack) noexcept
Definition: UT_BVHImpl.h:2444
BVH_Heuristic
Definition: UT_BVH.h:353
constexpr float operator[](exint i) const noexcept
Definition: UT_BVH.h:747
static SYS_FORCE_INLINE bool isInternal(INT_TYPE node_int) noexcept
Definition: UT_BVH.h:413
#define const
Definition: zconf.h:214
SYS_FORCE_INLINE Box(const TS &pt) noexcept
Definition: UT_BVH.h:58
SYS_FORCE_INLINE bool operator<(const BVHOrderedStackEntry &other) const
Definition: UT_BVH.h:717
SYS_FORCE_INLINE void enlargeBounds(const Box< T, NAXES > &src) noexcept
Definition: UT_BVH.h:120
SYS_FORCE_INLINE void combine(const Box< T, NAXES > &src) noexcept
Definition: UT_BVH.h:110
#define SYSmin(a, b)
Definition: SYS_Math.h:1514
const float myRadius
Definition: UT_BVH.h:753
unsigned int uint
Definition: SYS_Types.h:45
void traverseVector(FUNCTORS &functors, LOCAL_DATA *data_for_parent=nullptr) const noexcept
Definition: UT_BVHImpl.h:596
SYS_FORCE_INLINE const T * operator[](const size_t axis) const noexcept
Definition: UT_BVH.h:77
constexpr ZeroRadiiWrapper()=default
Definition: UT_BVH.h:704
SYS_FORCE_INLINE bool isValid(uint tree_point_index) const
Definition: UT_BVH.h:787