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) 2021
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,bool INSTANTIATED>
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,bool INSTANTIATED>
135  for (uint axis = 0; axis < NAXES; ++axis) {
136  vals[axis][0] = pt[axis];
137  vals[axis][1] = pt[axis];
138  }
139  }
140  template<bool INSTANTIATED>
143  for (uint axis = 0; axis < NAXES; ++axis) {
144  vals[axis][0] = min[axis];
145  vals[axis][1] = max[axis];
146  }
147  }
148  template<bool INSTANTIATED>
151  for (uint axis = 0; axis < NAXES; ++axis) {
152  vals[axis][0] = SYSmin(p0[axis], p1[axis]);
153  vals[axis][1] = SYSmax(p0[axis], p1[axis]);
154  }
155  }
156  template<bool INSTANTIATED>
159  for (uint axis = 0; axis < NAXES; ++axis) {
160  vals[axis][0] = SYSmin(vals[axis][0], pt[axis]);
161  vals[axis][1] = SYSmax(vals[axis][1], pt[axis]);
162  }
163  }
164 
168  for (uint axis = 0; axis < NAXES; ++axis) {
169  v[axis] = vals[axis][0];
170  }
171  return v;
172  }
173 
177  for (uint axis = 0; axis < NAXES; ++axis) {
178  v[axis] = vals[axis][1];
179  }
180  return v;
181  }
182 
183  T diameter2() const noexcept {
184  T diff = (vals[0][1]-vals[0][0]);
185  T sum = diff*diff;
186  for (uint axis = 1; axis < NAXES; ++axis) {
187  diff = (vals[axis][1]-vals[axis][0]);
188  sum += diff*diff;
189  }
190  return sum;
191  }
192  T volume() const noexcept {
193  T product = (vals[0][1]-vals[0][0]);
194  for (uint axis = 1; axis < NAXES; ++axis) {
195  product *= (vals[axis][1]-vals[axis][0]);
196  }
197  return product;
198  }
199  T half_surface_area() const noexcept {
200  if (NAXES==1) {
201  // NOTE: Although this should technically be 1,
202  // that doesn't make any sense as a heuristic,
203  // so we fall back to the "volume" of this box.
204  return (vals[0][1]-vals[0][0]);
205  }
206  if (NAXES==2) {
207  const T d0 = (vals[0][1]-vals[0][0]);
208  const T d1 = (vals[1][1]-vals[1][0]);
209  return d0 + d1;
210  }
211  if (NAXES==3) {
212  const T d0 = (vals[0][1]-vals[0][0]);
213  const T d1 = (vals[1][1]-vals[1][0]);
214  const T d2 = (vals[2][1]-vals[2][0]);
215  return d0*d1 + d1*d2 + d2*d0;
216  }
217  if (NAXES==4) {
218  const T d0 = (vals[0][1]-vals[0][0]);
219  const T d1 = (vals[1][1]-vals[1][0]);
220  const T d2 = (vals[2][1]-vals[2][0]);
221  const T d3 = (vals[3][1]-vals[3][0]);
222  // This is just d0d1d2 + d1d2d3 + d2d3d0 + d3d0d1 refactored.
223  const T d0d1 = d0*d1;
224  const T d2d3 = d2*d3;
225  return d0d1*(d2+d3) + d2d3*(d0+d1);
226  }
227 
228  T sum = 0;
229  for (uint skipped_axis = 0; skipped_axis < NAXES; ++skipped_axis) {
230  T product = 1;
231  for (uint axis = 0; axis < NAXES; ++axis) {
232  if (axis != skipped_axis) {
233  product *= (vals[axis][1]-vals[axis][0]);
234  }
235  }
236  sum += product;
237  }
238  return sum;
239  }
240  T axis_sum() const noexcept {
241  T sum = (vals[0][1]-vals[0][0]);
242  for (uint axis = 1; axis < NAXES; ++axis) {
243  sum += (vals[axis][1]-vals[axis][0]);
244  }
245  return sum;
246  }
247  template<bool INSTANTIATED0,bool INSTANTIATED1>
249  T &box_tmin,
250  T &box_tmax,
253  const UT_FixedVector<T,NAXES,INSTANTIATED1> &inverse_direction
254  ) const noexcept {
255  for (int axis = 0; axis < NAXES; ++axis)
256  {
257  uint sign = signs[axis];
258  T t1 = (vals[axis][sign] - origin[axis]) * inverse_direction[axis];
259  T t2 = (vals[axis][sign^1] - origin[axis]) * inverse_direction[axis];
260  box_tmin = SYSmax(t1, box_tmin);
261  box_tmax = SYSmin(t2, box_tmax);
262  }
263  }
264  SYS_FORCE_INLINE void intersect(const Box& other, Box& dest) const noexcept {
265  for (int axis = 0; axis < NAXES; ++axis)
266  {
267  dest.vals[axis][0] = SYSmax(vals[axis][0], other.vals[axis][0]);
268  dest.vals[axis][1] = SYSmin(vals[axis][1], other.vals[axis][1]);
269  }
270  }
271  template<bool INSTANTIATED>
274  ) const noexcept {
275  T diff = SYSmax(SYSmax(vals[0][0]-p[0], p[0]-vals[0][1]), T(0.0f));
276  T d2 = diff*diff;
277  for (int axis = 1; axis < NAXES; ++axis)
278  {
279  diff = SYSmax(SYSmax(vals[axis][0]-p[axis], p[axis]-vals[axis][1]), T(0.0f));
280  d2 += diff*diff;
281  }
282  return d2;
283  }
284  template<bool INSTANTIATED>
287  ) const noexcept {
288  T diff = SYSmax(p[0]-vals[0][0], vals[0][1]-p[0]);
289  T d2 = diff*diff;
290  for (int axis = 1; axis < NAXES; ++axis)
291  {
292  diff = SYSmax(p[axis]-vals[axis][0], vals[axis][1]-p[axis]);
293  d2 += diff*diff;
294  }
295  return d2;
296  }
297 };
298 
299 /// Used by BVH::init to specify the heuristic to use for choosing between different box splits.
300 /// I tried putting this inside the BVH class, but I had difficulty getting it to compile.
301 enum class BVH_Heuristic {
302  /// Tries to minimize the sum of axis lengths of the boxes.
303  /// This is useful for applications where the probability of a box being applicable to a
304  /// query is proportional to the "length", e.g. the probability of a random infinite plane
305  /// intersecting the box.
307 
308  /// Tries to minimize the "surface area" of the boxes.
309  /// In 3D, uses the surface area; in 2D, uses the perimeter; in 1D, uses the axis length.
310  /// This is what most applications, e.g. ray tracing, should use, particularly when the
311  /// probability of a box being applicable to a query is proportional to the surface "area",
312  /// e.g. the probability of a random ray hitting the box.
313  ///
314  /// NOTE: USE THIS ONE IF YOU ARE UNSURE!
315  BOX_AREA,
316 
317  /// Tries to minimize the "volume" of the boxes.
318  /// Uses the product of all axis lengths as a heuristic, (volume in 3D, area in 2D, length in 1D).
319  /// This is useful for applications where the probability of a box being applicable to a
320  /// query is proportional to the "volume", e.g. the probability of a random point being inside the box.
321  BOX_VOLUME,
322 
323  /// Tries to minimize the "radii" of the boxes (i.e. the 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 distance to the box centre, e.g. the probability of a random
326  /// infinite plane being within the "radius" of the centre.
327  BOX_RADIUS,
328 
329  /// Tries to minimize the squared "radii" of the boxes (i.e. the squared 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 squared distance to the box centre, e.g. the probability of a random
332  /// ray passing within the "radius" of the centre.
333  BOX_RADIUS2,
334 
335  /// Tries to minimize the cubed "radii" of the boxes (i.e. the cubed distance from the centre to a corner).
336  /// This is useful for applications where the probability of a box being applicable to a
337  /// query is proportional to the cubed distance to the box centre, e.g. the probability of a random
338  /// point being within the "radius" of the centre.
339  BOX_RADIUS3,
340 
341  /// Tries to minimize the depth of the tree by primarily splitting at the median of the max axis.
342  /// It may fall back to minimizing the area, but the tree depth should be unaffected.
343  ///
344  /// FIXME: This is not fully implemented yet.
346 };
347 
348 template<uint N>
349 class BVH {
350 public:
351  using INT_TYPE = uint;
352  struct Node {
354 
355  static constexpr INT_TYPE theN = N;
356  static constexpr INT_TYPE EMPTY = INT_TYPE(-1);
357  static constexpr INT_TYPE INTERNAL_BIT = (INT_TYPE(1)<<(sizeof(INT_TYPE)*8 - 1));
358  SYS_FORCE_INLINE static INT_TYPE markInternal(INT_TYPE internal_node_num) noexcept {
359  return internal_node_num | INTERNAL_BIT;
360  }
361  SYS_FORCE_INLINE static bool isInternal(INT_TYPE node_int) noexcept {
362  return (node_int & INTERNAL_BIT) != 0;
363  }
364  SYS_FORCE_INLINE static INT_TYPE getInternalNum(INT_TYPE node_int) noexcept {
365  return node_int & ~INTERNAL_BIT;
366  }
367  };
368 private:
369  struct FreeDeleter {
370  SYS_FORCE_INLINE void operator()(Node* p) const {
371  if (p) {
372  // The pointer was allocated with malloc by UT_Array,
373  // so it must be freed with free.
374  free(p);
375  }
376  }
377  };
378 
380  INT_TYPE myNumNodes;
381 public:
382  SYS_FORCE_INLINE BVH() noexcept : myRoot(nullptr), myNumNodes(0) {}
383 
384  template<BVH_Heuristic H,typename T,uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE=INT_TYPE>
385  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;
386 
387  template<BVH_Heuristic H,typename T,uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE=INT_TYPE>
388  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;
389 
392  {
393  return myNumNodes;
394  }
396  const Node *getNodes() const noexcept
397  {
398  return myRoot.get();
399  }
400 
402  void clear() noexcept {
403  myRoot.reset();
404  myNumNodes = 0;
405  }
406 
407  /// For each node, this effectively does:
408  /// LOCAL_DATA local_data[MAX_ORDER];
409  /// bool descend = functors.pre(nodei, parent_data);
410  /// if (!descend)
411  /// return;
412  /// for each child {
413  /// if (isitem(child))
414  /// functors.item(getitemi(child), nodei, local_data[child]);
415  /// else if (isnode(child))
416  /// recurse(getnodei(child), local_data);
417  /// }
418  /// functors.post(nodei, parent_nodei, data_for_parent, num_children, local_data);
419  template<typename LOCAL_DATA,typename FUNCTORS>
420  void traverse(
421  FUNCTORS &functors,
422  LOCAL_DATA *data_for_parent=nullptr) const noexcept;
423 
424  /// This acts like the traverse function, except if the number of nodes in two subtrees
425  /// of a node contain at least parallel_threshold nodes, they may be executed in parallel.
426  /// If parallel_threshold is 0, even item_functor may be executed on items in parallel.
427  /// NOTE: Make sure that your functors don't depend on the order that they're executed in,
428  /// e.g. don't add values from sibling nodes together except in post functor,
429  /// else they might have nondeterministic roundoff or miss some values entirely.
430  template<typename LOCAL_DATA,typename FUNCTORS>
431  void traverseParallel(
432  INT_TYPE parallel_threshold,
433  FUNCTORS &functors,
434  LOCAL_DATA *data_for_parent=nullptr) const noexcept;
435 
436  /// For each node, this effectively does:
437  /// LOCAL_DATA local_data[MAX_ORDER];
438  /// uint descend = functors.pre(nodei, parent_data);
439  /// if (!descend)
440  /// return;
441  /// for each child {
442  /// if (!(descend & (1<<child)))
443  /// continue;
444  /// if (isitem(child))
445  /// functors.item(getitemi(child), nodei, local_data[child]);
446  /// else if (isnode(child))
447  /// recurse(getnodei(child), local_data);
448  /// }
449  /// functors.post(nodei, parent_nodei, data_for_parent, num_children, local_data);
450  template<typename LOCAL_DATA,typename FUNCTORS>
451  void traverseVector(
452  FUNCTORS &functors,
453  LOCAL_DATA *data_for_parent=nullptr) const noexcept;
454 
455  /// Prints a text representation of the tree to stdout.
456  void debugDump() const;
457 
458  template<typename SRC_INT_TYPE>
459  static void createTrivialIndices(SRC_INT_TYPE* indices, const INT_TYPE n) noexcept;
460 
461 private:
462  template<typename LOCAL_DATA,typename FUNCTORS>
463  void traverseHelper(
464  INT_TYPE nodei,
465  INT_TYPE parent_nodei,
466  FUNCTORS &functors,
467  LOCAL_DATA *data_for_parent=nullptr) const noexcept;
468 
469  template<typename LOCAL_DATA,typename FUNCTORS>
470  void traverseParallelHelper(
471  INT_TYPE nodei,
472  INT_TYPE parent_nodei,
473  INT_TYPE parallel_threshold,
474  INT_TYPE next_node_id,
475  FUNCTORS &functors,
476  LOCAL_DATA *data_for_parent=nullptr) const noexcept;
477 
478  template<typename LOCAL_DATA,typename FUNCTORS>
479  void traverseVectorHelper(
480  INT_TYPE nodei,
481  INT_TYPE parent_nodei,
482  FUNCTORS &functors,
483  LOCAL_DATA *data_for_parent=nullptr) const noexcept;
484 
485  template<typename T,uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
486  static void computeFullBoundingBox(Box<T,NAXES>& axes_minmax, const BOX_TYPE* boxes, const INT_TYPE nboxes, SRC_INT_TYPE* indices) noexcept;
487 
488  template<BVH_Heuristic H,typename T,uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
489  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;
490 
491  template<BVH_Heuristic H,typename T,uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
492  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;
493 
494  template<BVH_Heuristic H,typename T,uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
495  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;
496 
497  template<BVH_Heuristic H,typename T,uint NAXES,typename BOX_TYPE,typename SRC_INT_TYPE>
498  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;
499 
500  template<INT_TYPE PARALLEL_THRESHOLD, typename SRC_INT_TYPE>
501  static void adjustParallelChildNodes(INT_TYPE nparallel, UT_Array<Node>& nodes, Node& node, UT_Array<Node>* parallel_nodes, SRC_INT_TYPE* sub_indices) noexcept;
502 
503  template<typename T,typename BOX_TYPE,typename SRC_INT_TYPE>
504  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;
505 
506  template<typename T,typename BOX_TYPE,typename SRC_INT_TYPE>
507  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;
508 
509  /// An overestimate of the number of nodes needed.
510  /// At worst, we could have only 2 children in every leaf, and
511  /// then above that, we have a geometric series with r=1/N and a=(sub_nboxes/2)/N
512  /// The true worst case might be a little worst than this, but
513  /// it's probably fairly unlikely.
514  SYS_FORCE_INLINE static INT_TYPE nodeEstimate(const INT_TYPE nboxes) noexcept {
515  return nboxes/2 + nboxes/(2*(N-1));
516  }
517 
518  template<BVH_Heuristic H,typename T, uint NAXES>
519  SYS_FORCE_INLINE static T unweightedHeuristic(const Box<T, NAXES>& box) noexcept {
520  if (H == BVH_Heuristic::BOX_PERIMETER) {
521  return box.axis_sum();
522  }
523  if (H == BVH_Heuristic::BOX_AREA) {
524  return box.half_surface_area();
525  }
526  if (H == BVH_Heuristic::BOX_VOLUME) {
527  return box.volume();
528  }
529  if (H == BVH_Heuristic::BOX_RADIUS) {
530  T diameter2 = box.diameter2();
531  return SYSsqrt(diameter2);
532  }
533  if (H == BVH_Heuristic::BOX_RADIUS2) {
534  return box.diameter2();
535  }
536  if (H == BVH_Heuristic::BOX_RADIUS3) {
537  T diameter2 = box.diameter2();
538  return diameter2*SYSsqrt(diameter2);
539  }
540  UT_ASSERT_MSG(0, "BVH_Heuristic::MEDIAN_MAX_AXIS should be handled separately by caller!");
541  return T(1);
542  }
543 
544  /// 16 equal-length spans (15 evenly-spaced splits) should be enough for a decent heuristic
545  static constexpr INT_TYPE NSPANS = 16;
546  static constexpr INT_TYPE NSPLITS = NSPANS-1;
547 
548  /// At least 1/16 of all boxes must be on each side, else we could end up with a very deep tree
549  static constexpr INT_TYPE MIN_FRACTION = 16;
550 };
551 
552 } // UT namespace
553 
554 template<uint N>
556 
557 } // End HDK_Sample namespace
558 #endif
#define SYSmax(a, b)
Definition: SYS_Math.h:1521
vint4 max(const vint4 &a, const vint4 &b)
Definition: simd.h:4703
SYS_FORCE_INLINE UT_FixedVector< T, NAXES > getMax() const noexcept
Definition: UT_BVH.h:175
void traverseParallel(INT_TYPE parallel_threshold, FUNCTORS &functors, LOCAL_DATA *data_for_parent=nullptr) const noexcept
Definition: UT_BVHImpl.h:392
SYS_FORCE_INLINE void initBoundsUnordered(const UT_FixedVector< T, NAXES, INSTANTIATED > &p0, const UT_FixedVector< T, NAXES, INSTANTIATED > &p1) noexcept
Definition: UT_BVH.h:150
GLenum src
Definition: glew.h:2410
static SYS_FORCE_INLINE INT_TYPE markInternal(INT_TYPE internal_node_num) noexcept
Definition: UT_BVH.h:358
#define SYS_STATIC_ASSERT_MSG(expr, msg)
SYS_FORCE_INLINE void initBounds() noexcept
Definition: UT_BVH.h:97
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:248
T half_surface_area() const noexcept
Definition: UT_BVH.h:199
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
SYS_FORCE_INLINE T minDistance2(const UT_FixedVector< T, NAXES, INSTANTIATED > &p) const noexcept
Definition: UT_BVH.h:272
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:382
const GLdouble * v
Definition: glew.h:1391
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:391
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:396
std::unique_ptr< T, Deleter > UT_UniquePtr
A smart pointer for unique ownership of dynamically allocated objects.
Definition: UT_UniquePtr.h:33
T diameter2() const noexcept
Definition: UT_BVH.h:183
#define UT_ASSERT_MSG(ZZ,...)
Definition: UT_Assert.h:138
T axis_sum() const noexcept
Definition: UT_BVH.h:240
GLclampf f
Definition: glew.h:3499
Definition: VM_SIMD.h:46
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:134
GLuint GLuint GLsizei GLenum const void * indices
Definition: glew.h:1253
SYS_FORCE_INLINE void intersect(const Box &other, Box &dest) const noexcept
Definition: UT_BVH.h:264
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
Definition: VM_SIMD.h:186
GLsizei n
Definition: glew.h:4040
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:356
SYS_FORCE_INLINE const T * operator[](const size_t axis) const noexcept
Definition: UT_BVH.h:88
SYS_FORCE_INLINE void initBounds(const UT_FixedVector< T, NAXES, INSTANTIATED > &min, const UT_FixedVector< T, NAXES, INSTANTIATED > &max) noexcept
Definition: UT_BVH.h:142
int sign(T a)
Definition: ImathFun.h:63
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
SYS_FORCE_INLINE void enlargeBounds(const UT_FixedVector< T, NAXES, INSTANTIATED > &pt) noexcept
Definition: UT_BVH.h:158
SYS_FORCE_INLINE T maxDistance2(const UT_FixedVector< T, NAXES, INSTANTIATED > &p) const noexcept
Definition: UT_BVH.h:285
SYS_FORCE_INLINE void clear() noexcept
Definition: UT_BVH.h:402
static constexpr INT_TYPE theN
Definition: UT_BVH.h:355
SYS_FORCE_INLINE Box(const UT_FixedVector< S, NAXES, INSTANTIATED > &pt) noexcept
Definition: UT_BVH.h:73
GLfloat GLfloat p
Definition: glew.h:16321
SYS_FORCE_INLINE UT_FixedVector< T, NAXES > getMin() const noexcept
Definition: UT_BVH.h:166
GLuint GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat t1
Definition: glew.h:12681
GA_API const UT_StringHolder N
void traverseVector(FUNCTORS &functors, LOCAL_DATA *data_for_parent=nullptr) const noexcept
Definition: UT_BVHImpl.h:516
Definition: ImathBox.h:72
#define const
Definition: zconf.h:214
vint4 min(const vint4 &a, const vint4 &b)
Definition: simd.h:4694
static SYS_FORCE_INLINE bool isInternal(INT_TYPE node_int) noexcept
Definition: UT_BVH.h:361
#define SYSmin(a, b)
Definition: SYS_Math.h:1522
T volume() const noexcept
Definition: UT_BVH.h:192
SYS_FORCE_INLINE void combine(const Box< T, NAXES > &src) noexcept
Definition: UT_BVH.h:121
SYS_FORCE_INLINE void initBounds(const UT_FixedVector< S, NAXES, INSTANTIATED > &pt) noexcept
Definition: UT_BVH.h:134
unsigned int uint
Definition: SYS_Types.h:45
static SYS_FORCE_INLINE INT_TYPE getInternalNum(INT_TYPE node_int) noexcept
Definition: UT_BVH.h:364
T vals[NAXES][2]
Definition: UT_BVH.h:54
static constexpr INT_TYPE INTERNAL_BIT
Definition: UT_BVH.h:357