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