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