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  * Copyright (c) 2022
3  * Side Effects Software Inc. All rights reserved.
4  *
5  * Redistribution and use of Houdini Development Kit samples in source and
6  * binary forms, with or without modification, are permitted provided that the
7  * following conditions are met:
8  * 1. Redistributions of source code must retain the above copyright notice,
9  * this list of conditions and the following disclaimer.
10  * 2. The name of Side Effects Software may not be used to endorse or
11  * promote products derived from this software without specific prior
12  * written permission.
13  *
14  * THIS SOFTWARE IS PROVIDED BY SIDE EFFECTS SOFTWARE `AS IS' AND ANY EXPRESS
15  * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
16  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
17  * NO EVENT SHALL SIDE EFFECTS SOFTWARE BE LIABLE FOR ANY DIRECT, INDIRECT,
18  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
19  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
20  * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
21  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
22  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
23  * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24  *
25  *----------------------------------------------------------------------------
26  * Bounding Volume Hierarchy (BVH) implementation.
27  * To call functions not implemented here, also include UT_BVHImpl.h
28  */
29 
30 #pragma once
31 
32 #ifndef __HDK_UT_BVH_h__
33 #define __HDK_UT_BVH_h__
34 
35 #include <UT/UT_FixedVector.h>
36 #include <UT/UT_SmallArray.h>
37 #include <UT/UT_UniquePtr.h>
38 #include <SYS/SYS_Inline.h>
39 #include <SYS/SYS_StaticAssert.h>
40 #include <SYS/SYS_Types.h>
41 #include <SYS/SYS_TypeTraits.h>
42 #include <limits>
43 
44 template<typename T> class UT_Array;
45 class v4uf;
46 class v4uu;
47 
48 namespace HDK_Sample {
49 
50 namespace UT {
51 
52 template<typename T,uint NAXES>
53 struct Box {
54  T vals[NAXES][2];
55 
56  SYS_FORCE_INLINE Box() noexcept = default;
57  SYS_FORCE_INLINE constexpr Box(const Box &other) noexcept = default;
58  SYS_FORCE_INLINE constexpr Box(Box &&other) noexcept = default;
59  SYS_FORCE_INLINE Box& operator=(const Box &other) noexcept = default;
60  SYS_FORCE_INLINE Box& operator=(Box &&other) noexcept = default;
61 
62  template<typename S>
63  SYS_FORCE_INLINE Box(const Box<S,NAXES>& other) noexcept {
64  SYS_STATIC_ASSERT_MSG((SYSisPOD<Box<T,NAXES>>()) || !SYSisPOD<T>(),
65  "UT::Box should be POD, for better performance in UT_Array, etc.");
66 
67  for (uint axis = 0; axis < NAXES; ++axis) {
68  vals[axis][0] = T(other.vals[axis][0]);
69  vals[axis][1] = T(other.vals[axis][1]);
70  }
71  }
72  template<typename S>
74  for (uint axis = 0; axis < NAXES; ++axis) {
75  vals[axis][0] = pt[axis];
76  vals[axis][1] = pt[axis];
77  }
78  }
79  template<typename S>
80  SYS_FORCE_INLINE Box& operator=(const Box<S,NAXES>& other) noexcept {
81  for (uint axis = 0; axis < NAXES; ++axis) {
82  vals[axis][0] = T(other.vals[axis][0]);
83  vals[axis][1] = T(other.vals[axis][1]);
84  }
85  return *this;
86  }
87 
88  SYS_FORCE_INLINE const T* operator[](const size_t axis) const noexcept {
89  UT_ASSERT_P(axis < NAXES);
90  return vals[axis];
91  }
92  SYS_FORCE_INLINE T* operator[](const size_t axis) noexcept {
93  UT_ASSERT_P(axis < NAXES);
94  return vals[axis];
95  }
96 
97  SYS_FORCE_INLINE void initBounds() noexcept {
98  for (uint axis = 0; axis < NAXES; ++axis) {
99  vals[axis][0] = std::numeric_limits<T>::max();
100  vals[axis][1] = -std::numeric_limits<T>::max();
101  }
102  }
103  /// Copy the source box.
104  /// NOTE: This is so that in templated code that may have a Box or a
105  /// UT_FixedVector, it can call initBounds and still work.
106  SYS_FORCE_INLINE void initBounds(const Box<T,NAXES>& src) noexcept {
107  for (uint axis = 0; axis < NAXES; ++axis) {
108  vals[axis][0] = src.vals[axis][0];
109  vals[axis][1] = src.vals[axis][1];
110  }
111  }
112  /// Initialize with the union of the source boxes.
113  /// NOTE: This is so that in templated code that may have Box's or a
114  /// UT_FixedVector's, it can call initBounds and still work.
115  SYS_FORCE_INLINE void initBoundsUnordered(const Box<T,NAXES>& src0, const Box<T,NAXES>& src1) noexcept {
116  for (uint axis = 0; axis < NAXES; ++axis) {
117  vals[axis][0] = SYSmin(src0.vals[axis][0], src1.vals[axis][0]);
118  vals[axis][1] = SYSmax(src0.vals[axis][1], src1.vals[axis][1]);
119  }
120  }
121  SYS_FORCE_INLINE void combine(const Box<T,NAXES>& src) noexcept {
122  for (uint axis = 0; axis < NAXES; ++axis) {
123  T& minv = vals[axis][0];
124  T& maxv = vals[axis][1];
125  const T curminv = src.vals[axis][0];
126  const T curmaxv = src.vals[axis][1];
127  minv = (minv < curminv) ? minv : curminv;
128  maxv = (maxv > curmaxv) ? maxv : curmaxv;
129  }
130  }
131 
132  template<typename S>
134  void initBounds(const UT_FixedVector<S,NAXES>& pt) noexcept {
135  for (uint axis = 0; axis < NAXES; ++axis) {
136  vals[axis][0] = pt[axis];
137  vals[axis][1] = pt[axis];
138  }
139  }
142  for (uint axis = 0; axis < NAXES; ++axis) {
143  vals[axis][0] = min[axis];
144  vals[axis][1] = max[axis];
145  }
146  }
149  for (uint axis = 0; axis < NAXES; ++axis) {
150  vals[axis][0] = SYSmin(p0[axis], p1[axis]);
151  vals[axis][1] = SYSmax(p0[axis], p1[axis]);
152  }
153  }
155  void enlargeBounds(const UT_FixedVector<T,NAXES>& pt) noexcept {
156  for (uint axis = 0; axis < NAXES; ++axis) {
157  vals[axis][0] = SYSmin(vals[axis][0], pt[axis]);
158  vals[axis][1] = SYSmax(vals[axis][1], pt[axis]);
159  }
160  }
161 
165  for (uint axis = 0; axis < NAXES; ++axis) {
166  v[axis] = vals[axis][0];
167  }
168  return v;
169  }
170 
174  for (uint axis = 0; axis < NAXES; ++axis) {
175  v[axis] = vals[axis][1];
176  }
177  return v;
178  }
179 
180  T diameter2() const noexcept {
181  T diff = (vals[0][1]-vals[0][0]);
182  T sum = diff*diff;
183  for (uint axis = 1; axis < NAXES; ++axis) {
184  diff = (vals[axis][1]-vals[axis][0]);
185  sum += diff*diff;
186  }
187  return sum;
188  }
189  T volume() const noexcept {
190  T product = (vals[0][1]-vals[0][0]);
191  for (uint axis = 1; axis < NAXES; ++axis) {
192  product *= (vals[axis][1]-vals[axis][0]);
193  }
194  return product;
195  }
196  T half_surface_area() const noexcept {
197  if (NAXES==1) {
198  // NOTE: Although this should technically be 1,
199  // that doesn't make any sense as a heuristic,
200  // so we fall back to the "volume" of this box.
201  return (vals[0][1]-vals[0][0]);
202  }
203  if (NAXES==2) {
204  const T d0 = (vals[0][1]-vals[0][0]);
205  const T d1 = (vals[1][1]-vals[1][0]);
206  return d0 + d1;
207  }
208  if (NAXES==3) {
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  return d0*d1 + d1*d2 + d2*d0;
213  }
214  if (NAXES==4) {
215  const T d0 = (vals[0][1]-vals[0][0]);
216  const T d1 = (vals[1][1]-vals[1][0]);
217  const T d2 = (vals[2][1]-vals[2][0]);
218  const T d3 = (vals[3][1]-vals[3][0]);
219  // This is just d0d1d2 + d1d2d3 + d2d3d0 + d3d0d1 refactored.
220  const T d0d1 = d0*d1;
221  const T d2d3 = d2*d3;
222  return d0d1*(d2+d3) + d2d3*(d0+d1);
223  }
224 
225  T sum = 0;
226  for (uint skipped_axis = 0; skipped_axis < NAXES; ++skipped_axis) {
227  T product = 1;
228  for (uint axis = 0; axis < NAXES; ++axis) {
229  if (axis != skipped_axis) {
230  product *= (vals[axis][1]-vals[axis][0]);
231  }
232  }
233  sum += product;
234  }
235  return sum;
236  }
237  T axis_sum() const noexcept {
238  T sum = (vals[0][1]-vals[0][0]);
239  for (uint axis = 1; axis < NAXES; ++axis) {
240  sum += (vals[axis][1]-vals[axis][0]);
241  }
242  return sum;
243  }
245  T &box_tmin,
246  T &box_tmax,
247  const UT_FixedVector<uint,NAXES> &signs,
248  const UT_FixedVector<T,NAXES> &origin,
249  const UT_FixedVector<T,NAXES> &inverse_direction
250  ) const noexcept {
251  for (int axis = 0; axis < NAXES; ++axis)
252  {
253  uint sign = signs[axis];
254  T t1 = (vals[axis][sign] - origin[axis]) * inverse_direction[axis];
255  T t2 = (vals[axis][sign^1] - origin[axis]) * inverse_direction[axis];
256  box_tmin = SYSmax(t1, box_tmin);
257  box_tmax = SYSmin(t2, box_tmax);
258  }
259  }
260  SYS_FORCE_INLINE void intersect(const Box& other, Box& dest) const noexcept {
261  for (int axis = 0; axis < NAXES; ++axis)
262  {
263  dest.vals[axis][0] = SYSmax(vals[axis][0], other.vals[axis][0]);
264  dest.vals[axis][1] = SYSmin(vals[axis][1], other.vals[axis][1]);
265  }
266  }
269  ) const noexcept {
270  T diff = SYSmax(SYSmax(vals[0][0]-p[0], p[0]-vals[0][1]), T(0.0f));
271  T d2 = diff*diff;
272  for (int axis = 1; axis < NAXES; ++axis)
273  {
274  diff = SYSmax(SYSmax(vals[axis][0]-p[axis], p[axis]-vals[axis][1]), T(0.0f));
275  d2 += diff*diff;
276  }
277  return d2;
278  }
281  ) const noexcept {
282  T diff = SYSmax(p[0]-vals[0][0], vals[0][1]-p[0]);
283  T d2 = diff*diff;
284  for (int axis = 1; axis < NAXES; ++axis)
285  {
286  diff = SYSmax(p[axis]-vals[axis][0], vals[axis][1]-p[axis]);
287  d2 += diff*diff;
288  }
289  return d2;
290  }
291 };
292 
293 /// Used by BVH::init to specify the heuristic to use for choosing between different box splits.
294 /// I tried putting this inside the BVH class, but I had difficulty getting it to compile.
295 enum class BVH_Heuristic {
296  /// Tries to minimize the sum of axis lengths of the boxes.
297  /// This is useful for applications where the probability of a box being applicable to a
298  /// query is proportional to the "length", e.g. the probability of a random infinite plane
299  /// intersecting the box.
301 
302  /// Tries to minimize the "surface area" of the boxes.
303  /// In 3D, uses the surface area; in 2D, uses the perimeter; in 1D, uses the axis length.
304  /// This is what most applications, e.g. ray tracing, should use, particularly when the
305  /// probability of a box being applicable to a query is proportional to the surface "area",
306  /// e.g. the probability of a random ray hitting the box.
307  ///
308  /// NOTE: USE THIS ONE IF YOU ARE UNSURE!
309  BOX_AREA,
310 
311  /// Tries to minimize the "volume" of the boxes.
312  /// Uses the product of all axis lengths as a heuristic, (volume in 3D, area in 2D, length in 1D).
313  /// This is useful for applications where the probability of a box being applicable to a
314  /// query is proportional to the "volume", e.g. the probability of a random point being inside the box.
315  BOX_VOLUME,
316 
317  /// Tries to minimize the "radii" of the boxes (i.e. the distance from the centre to a corner).
318  /// This is useful for applications where the probability of a box being applicable to a
319  /// query is proportional to the distance to the box centre, e.g. the probability of a random
320  /// infinite plane being within the "radius" of the centre.
321  BOX_RADIUS,
322 
323  /// Tries to minimize the squared "radii" of the boxes (i.e. the squared distance from the centre to a corner).
324  /// This is useful for applications where the probability of a box being applicable to a
325  /// query is proportional to the squared distance to the box centre, e.g. the probability of a random
326  /// ray passing within the "radius" of the centre.
327  BOX_RADIUS2,
328 
329  /// Tries to minimize the cubed "radii" of the boxes (i.e. the cubed distance from the centre to a corner).
330  /// This is useful for applications where the probability of a box being applicable to a
331  /// query is proportional to the cubed distance to the box centre, e.g. the probability of a random
332  /// point being within the "radius" of the centre.
333  BOX_RADIUS3,
334 
335  /// Tries to minimize the depth of the tree by primarily splitting at the median of the max axis.
336  /// It may fall back to minimizing the area, but the tree depth should be unaffected.
337  ///
338  /// FIXME: This is not fully implemented yet.
340 };
341 
342 template<uint N>
343 class BVH {
344 public:
345  using INT_TYPE = uint;
346  struct Node {
348 
349  static constexpr INT_TYPE theN = N;
350  static constexpr INT_TYPE EMPTY = INT_TYPE(-1);
351  static constexpr INT_TYPE INTERNAL_BIT = (INT_TYPE(1)<<(sizeof(INT_TYPE)*8 - 1));
352  SYS_FORCE_INLINE static INT_TYPE markInternal(INT_TYPE internal_node_num) noexcept {
353  return internal_node_num | INTERNAL_BIT;
354  }
355  SYS_FORCE_INLINE static bool isInternal(INT_TYPE node_int) noexcept {
356  return (node_int & INTERNAL_BIT) != 0;
357  }
358  SYS_FORCE_INLINE static INT_TYPE getInternalNum(INT_TYPE node_int) noexcept {
359  return node_int & ~INTERNAL_BIT;
360  }
361  };
362 private:
363  struct FreeDeleter {
364  SYS_FORCE_INLINE void operator()(Node* p) const {
365  if (p) {
366  // The pointer was allocated with malloc by UT_Array,
367  // so it must be freed with free.
368  free(p);
369  }
370  }
371  };
372 
374  INT_TYPE myNumNodes;
375 public:
376  SYS_FORCE_INLINE BVH() noexcept : myRoot(nullptr), myNumNodes(0) {}
377 
378  template<BVH_Heuristic H,typename T,uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE=INT_TYPE>
379  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;
380 
381  template<BVH_Heuristic H,typename T,uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE=INT_TYPE>
382  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;
383 
386  {
387  return myNumNodes;
388  }
390  const Node *getNodes() const noexcept
391  {
392  return myRoot.get();
393  }
394 
396  void clear() noexcept {
397  myRoot.reset();
398  myNumNodes = 0;
399  }
400 
401  /// For each node, this effectively does:
402  /// LOCAL_DATA local_data[MAX_ORDER];
403  /// bool descend = functors.pre(nodei, parent_data);
404  /// if (!descend)
405  /// return;
406  /// for each child {
407  /// if (isitem(child))
408  /// functors.item(getitemi(child), nodei, local_data[child]);
409  /// else if (isnode(child))
410  /// recurse(getnodei(child), local_data);
411  /// }
412  /// functors.post(nodei, parent_nodei, data_for_parent, num_children, local_data);
413  template<typename LOCAL_DATA,typename FUNCTORS>
414  void traverse(
415  FUNCTORS &functors,
416  LOCAL_DATA *data_for_parent=nullptr) const noexcept;
417 
418  /// This acts like the traverse function, except if the number of nodes in two subtrees
419  /// of a node contain at least parallel_threshold nodes, they may be executed in parallel.
420  /// If parallel_threshold is 0, even item_functor may be executed on items in parallel.
421  /// NOTE: Make sure that your functors don't depend on the order that they're executed in,
422  /// e.g. don't add values from sibling nodes together except in post functor,
423  /// else they might have nondeterministic roundoff or miss some values entirely.
424  template<typename LOCAL_DATA,typename FUNCTORS>
425  void traverseParallel(
426  INT_TYPE parallel_threshold,
427  FUNCTORS &functors,
428  LOCAL_DATA *data_for_parent=nullptr) const noexcept;
429 
430  /// For each node, this effectively does:
431  /// LOCAL_DATA local_data[MAX_ORDER];
432  /// uint descend = functors.pre(nodei, parent_data);
433  /// if (!descend)
434  /// return;
435  /// for each child {
436  /// if (!(descend & (1<<child)))
437  /// continue;
438  /// if (isitem(child))
439  /// functors.item(getitemi(child), nodei, local_data[child]);
440  /// else if (isnode(child))
441  /// recurse(getnodei(child), local_data);
442  /// }
443  /// functors.post(nodei, parent_nodei, data_for_parent, num_children, local_data);
444  template<typename LOCAL_DATA,typename FUNCTORS>
445  void traverseVector(
446  FUNCTORS &functors,
447  LOCAL_DATA *data_for_parent=nullptr) const noexcept;
448 
449  /// Prints a text representation of the tree to stdout.
450  void debugDump() const;
451 
452  template<typename SRC_INT_TYPE>
453  static void createTrivialIndices(SRC_INT_TYPE* indices, const INT_TYPE n) noexcept;
454 
455 private:
456  template<typename LOCAL_DATA,typename FUNCTORS>
457  void traverseHelper(
458  INT_TYPE nodei,
459  INT_TYPE parent_nodei,
460  FUNCTORS &functors,
461  LOCAL_DATA *data_for_parent=nullptr) const noexcept;
462 
463  template<typename LOCAL_DATA,typename FUNCTORS>
464  void traverseParallelHelper(
465  INT_TYPE nodei,
466  INT_TYPE parent_nodei,
467  INT_TYPE parallel_threshold,
468  INT_TYPE next_node_id,
469  FUNCTORS &functors,
470  LOCAL_DATA *data_for_parent=nullptr) const noexcept;
471 
472  template<typename LOCAL_DATA,typename FUNCTORS>
473  void traverseVectorHelper(
474  INT_TYPE nodei,
475  INT_TYPE parent_nodei,
476  FUNCTORS &functors,
477  LOCAL_DATA *data_for_parent=nullptr) const noexcept;
478 
479  template<typename T,uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
480  static void computeFullBoundingBox(Box<T,NAXES>& axes_minmax, const BOX_TYPE* boxes, const INT_TYPE nboxes, SRC_INT_TYPE* indices) noexcept;
481 
482  template<BVH_Heuristic H,typename T,uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
483  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;
484 
485  template<BVH_Heuristic H,typename T,uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
486  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;
487 
488  template<BVH_Heuristic H,typename T,uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
489  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;
490 
491  template<BVH_Heuristic H,typename T,uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
492  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;
493 
494  template<INT_TYPE PARALLEL_THRESHOLD, typename SRC_INT_TYPE>
495  static void adjustParallelChildNodes(INT_TYPE nparallel, UT_Array<Node>& nodes, Node& node, UT_Array<Node>* parallel_nodes, SRC_INT_TYPE* sub_indices) noexcept;
496 
497  template<typename T,typename BOX_TYPE,typename SRC_INT_TYPE>
498  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;
499 
500  template<typename T,typename BOX_TYPE,typename SRC_INT_TYPE>
501  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;
502 
503  /// An overestimate of the number of nodes needed.
504  /// At worst, we could have only 2 children in every leaf, and
505  /// then above that, we have a geometric series with r=1/N and a=(sub_nboxes/2)/N
506  /// The true worst case might be a little worst than this, but
507  /// it's probably fairly unlikely.
508  SYS_FORCE_INLINE static INT_TYPE nodeEstimate(const INT_TYPE nboxes) noexcept {
509  return nboxes/2 + nboxes/(2*(N-1));
510  }
511 
512  template<BVH_Heuristic H,typename T, uint NAXES>
513  SYS_FORCE_INLINE static T unweightedHeuristic(const Box<T, NAXES>& box) noexcept {
515  return box.axis_sum();
516  }
517  if (H == BVH_Heuristic::BOX_AREA) {
518  return box.half_surface_area();
519  }
520  if (H == BVH_Heuristic::BOX_VOLUME) {
521  return box.volume();
522  }
523  if (H == BVH_Heuristic::BOX_RADIUS) {
524  T diameter2 = box.diameter2();
525  return SYSsqrt(diameter2);
526  }
527  if (H == BVH_Heuristic::BOX_RADIUS2) {
528  return box.diameter2();
529  }
530  if (H == BVH_Heuristic::BOX_RADIUS3) {
531  T diameter2 = box.diameter2();
532  return diameter2*SYSsqrt(diameter2);
533  }
534  UT_ASSERT_MSG(0, "BVH_Heuristic::MEDIAN_MAX_AXIS should be handled separately by caller!");
535  return T(1);
536  }
537 
538  /// 16 equal-length spans (15 evenly-spaced splits) should be enough for a decent heuristic
539  static constexpr INT_TYPE NSPANS = 16;
540  static constexpr INT_TYPE NSPLITS = NSPANS-1;
541 
542  /// At least 1/16 of all boxes must be on each side, else we could end up with a very deep tree
543  static constexpr INT_TYPE MIN_FRACTION = 16;
544 };
545 
546 } // UT namespace
547 
548 template<uint N>
550 
551 } // End HDK_Sample namespace
552 #endif
#define SYSmax(a, b)
Definition: SYS_Math.h:1513
SYS_FORCE_INLINE UT_FixedVector< T, NAXES > getMax() const noexcept
Definition: UT_BVH.h:172
void traverseParallel(INT_TYPE parallel_threshold, FUNCTORS &functors, LOCAL_DATA *data_for_parent=nullptr) const noexcept
Definition: UT_BVHImpl.h:392
static SYS_FORCE_INLINE INT_TYPE markInternal(INT_TYPE internal_node_num) noexcept
Definition: UT_BVH.h:352
#define SYS_STATIC_ASSERT_MSG(expr, msg)
SYS_FORCE_INLINE void initBounds() noexcept
Definition: UT_BVH.h:97
Definition: Node.h:52
T half_surface_area() const noexcept
Definition: UT_BVH.h:196
SYS_FORCE_INLINE T * operator[](const size_t axis) noexcept
Definition: UT_BVH.h:92
SYS_FORCE_INLINE void initBounds(const Box< T, NAXES > &src) noexcept
Definition: UT_BVH.h:106
static void createTrivialIndices(SRC_INT_TYPE *indices, const INT_TYPE n) noexcept
Definition: UT_BVHImpl.h:562
void debugDump() const
Prints a text representation of the tree to stdout.
SYS_FORCE_INLINE BVH() noexcept
Definition: UT_BVH.h:376
ImageBuf OIIO_API min(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
GLuint GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat t1
Definition: glew.h:12900
GLenum src
Definition: glcorearb.h:1793
SYS_FORCE_INLINE Box(const UT_FixedVector< S, NAXES > &pt) noexcept
Definition: UT_BVH.h:73
SYS_FORCE_INLINE Box() noexcept=default
SYS_FORCE_INLINE Box & operator=(const Box< S, NAXES > &other) noexcept
Definition: UT_BVH.h:80
SYS_FORCE_INLINE INT_TYPE getNumNodes() const noexcept
Definition: UT_BVH.h:385
void traverse(FUNCTORS &functors, LOCAL_DATA *data_for_parent=nullptr) const noexcept
Definition: UT_BVHImpl.h:349
SYS_FORCE_INLINE const Node * getNodes() const noexcept
Definition: UT_BVH.h:390
std::unique_ptr< T, Deleter > UT_UniquePtr
A smart pointer for unique ownership of dynamically allocated objects.
Definition: UT_UniquePtr.h:39
SYS_FORCE_INLINE void initBounds(const UT_FixedVector< T, NAXES > &min, const UT_FixedVector< T, NAXES > &max) noexcept
Definition: UT_BVH.h:141
T diameter2() const noexcept
Definition: UT_BVH.h:180
#define UT_ASSERT_MSG(ZZ,...)
Definition: UT_Assert.h:156
SYS_FORCE_INLINE void initBounds(const UT_FixedVector< S, NAXES > &pt) noexcept
Definition: UT_BVH.h:134
SYS_FORCE_INLINE void initBoundsUnordered(const UT_FixedVector< T, NAXES > &p0, const UT_FixedVector< T, NAXES > &p1) noexcept
Definition: UT_BVH.h:148
T axis_sum() const noexcept
Definition: UT_BVH.h:237
SYS_FORCE_INLINE T maxDistance2(const UT_FixedVector< T, NAXES > &p) const noexcept
Definition: UT_BVH.h:279
SYS_FORCE_INLINE T minDistance2(const UT_FixedVector< T, NAXES > &p) const noexcept
Definition: UT_BVH.h:267
Definition: VM_SIMD.h:48
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:152
const GLdouble * v
Definition: glcorearb.h:837
SYS_FORCE_INLINE void intersect(const Box &other, Box &dest) const noexcept
Definition: UT_BVH.h:260
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
GLsizei GLenum const void * indices
Definition: glcorearb.h:406
Definition: VM_SIMD.h:188
SYS_FORCE_INLINE void initBoundsUnordered(const Box< T, NAXES > &src0, const Box< T, NAXES > &src1) noexcept
Definition: UT_BVH.h:115
static constexpr INT_TYPE EMPTY
Definition: UT_BVH.h:350
SYS_FORCE_INLINE const T * operator[](const size_t axis) const noexcept
Definition: UT_BVH.h:88
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
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:292
GLdouble n
Definition: glcorearb.h:2008
SYS_FORCE_INLINE void enlargeBounds(const UT_FixedVector< T, NAXES > &pt) noexcept
Definition: UT_BVH.h:155
SYS_FORCE_INLINE void clear() noexcept
Definition: UT_BVH.h:396
static constexpr INT_TYPE theN
Definition: UT_BVH.h:349
GLsizei const GLint box[]
Definition: glew.h:11654
SYS_FORCE_INLINE UT_FixedVector< T, NAXES > getMin() const noexcept
Definition: UT_BVH.h:163
ImageBuf OIIO_API max(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
GA_API const UT_StringHolder N
void traverseVector(FUNCTORS &functors, LOCAL_DATA *data_for_parent=nullptr) const noexcept
Definition: UT_BVHImpl.h:516
GLfloat f
Definition: glcorearb.h:1926
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:244
Definition: ImathBox.h:37
#define const
Definition: zconf.h:214
static SYS_FORCE_INLINE bool isInternal(INT_TYPE node_int) noexcept
Definition: UT_BVH.h:355
#define SYSmin(a, b)
Definition: SYS_Math.h:1514
T volume() const noexcept
Definition: UT_BVH.h:189
SYS_FORCE_INLINE void combine(const Box< T, NAXES > &src) noexcept
Definition: UT_BVH.h:121
unsigned int uint
Definition: SYS_Types.h:45
static SYS_FORCE_INLINE INT_TYPE getInternalNum(INT_TYPE node_int) noexcept
Definition: UT_BVH.h:358
T vals[NAXES][2]
Definition: UT_BVH.h:54
static constexpr INT_TYPE INTERNAL_BIT
Definition: UT_BVH.h:351