HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
GEO_BVHImpl.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: GEO_BVHImpl.h (GEO Library, C++)
7  *
8  * COMMENTS: Bounding Volume Hierarchy (BVH) implementation for GEO_Detail.
9  */
10 
11 #pragma once
12 
13 #include "GEO_BVH.h"
14 #include <GA/GA_Detail.h>
15 #include <GA/GA_Handle.h>
16 #include <GA/GA_Iterator.h>
17 #include <GA/GA_SplittableRange.h>
18 #include <GA/GA_Types.h>
19 #include <UT/UT_Array.h>
20 #include <UT/UT_BVH.h>
21 #include <UT/UT_BVHImpl.h>
22 #include <UT/UT_ParallelUtil.h>
23 #include <UT/UT_RootFinder.h>
24 #include <UT/UT_SmallArray.h>
25 #include <UT/UT_StopWatch.h>
26 #include <SYS/SYS_Math.h>
27 #include <limits>
28 
29 #define GEO_BVH_INTERLEAVED 1
30 
31 namespace GEO {
32 
33 template<uint NAXES,typename SUBCLASS>
35 {
36  myTree.clear();
37  myNodeBoxes.reset();
38  myPositions.setCapacity(0);
39  myRadii.setCapacity(0);
40  myPosAttrib.clear();
41  myRadAttrib.clear();
42  myPoints.clear();
43  myHasCurvesOrPoints = false;
44 }
45 
46 template<typename VectorType>
47 static bool
48 geoIntersectSphere(
49  VectorType rel_origin, const VectorType &direction,
50  float radius, float &t0, float &t1)
51 {
52  // NOTE: direction should already be normalized!
53 
54  // To stabilize the quadratic equation, we move closer to the centre of the
55  // sphere...
56  float rayt = SYSsqrt(rel_origin.length2()); // SYSsqrt(rel_origin.length2() / direction.length2());
57  VectorType p = rel_origin + rayt*direction;
58 
59  //float a = direction.length2();
60  float b = 2.0F * dot(p, direction);
61  float c = p.length2() - radius*radius;
62 
63  float d = b*b - 4.0F*c; // b*b - 4.0F*a*c
64  if (d < 0)
65  return false;
66 
67  //a = 0.5F/a;
68  d = SYSsqrt(d);
69 
70  t0 = rayt-(b+d); //rayt + a*(-b-d);
71 
72  // TODO: Exclude t1 if rmbackface
73  t1 = rayt-(b-d); //rayt + a*(-b+d);
74 
75  return true;
76 }
77 
78 template<uint NAXES,typename SUBCLASS>
79 template<bool USE_TOLERANCE>
80 struct BVHBase<NAXES,SUBCLASS>::SingleHitFunctor
81 {
83  HitInfo &hit_info) noexcept
84  : myHitInfo(hit_info)
85  , myNestingArrayBase(hit_info.myNestedItemIndices ? hit_info.myNestedItemIndices->size() : 0)
86  {}
87  SYS_FORCE_INLINE void noHit() noexcept
88  {
89  myHitInfo.myItemIndex = -1;
90  myHitInfo.myUVW.assign(0,0,0);
91  myHitInfo.myT = -1.0f;
92  }
94  const UT_Vector3 &hit_uvw,
95  const float t,
96  const uint index,
97  float &limit_t) noexcept
98  {
99  myHitInfo.myItemIndex = index;
100  myHitInfo.myUVW = hit_uvw;
101  // Clear local portion of nesting array
102  if (myHitInfo.myNestedItemIndices)
103  myHitInfo.myNestedItemIndices->setSize(myNestingArrayBase);
104  myHitInfo.myT = t;
105  limit_t = t;
106  }
108  {
109  hit_info.myNestedItemIndices = myHitInfo.myNestedItemIndices;
110  }
112  {
113  return myHitInfo.myNestedItemIndices;
114  }
116  {
117  return myNestingArrayBase;
118  }
119  SYS_FORCE_INLINE VectorType getNormal(const HitInfo &hit_info) const noexcept
120  { return VectorType(); }
121  SYS_FORCE_INLINE void setNormal(const VectorType &nml) noexcept {}
122  SYS_FORCE_INLINE void setNormal(HitInfo &hit_info, const VectorType &nml) const noexcept {}
123  SYS_FORCE_INLINE UT_Array<HitInfo> *getHitArray() noexcept { return nullptr; }
124  SYS_FORCE_INLINE exint nestingArrayBase() const noexcept { return myNestingArrayBase; }
125  SYS_FORCE_INLINE UT_Vector3 &lastUVW() noexcept { return myHitInfo.myUVW; }
126 
127  constexpr static bool theAllHits = false;
128  constexpr static bool theNeedsNormal = false;
129  constexpr static bool theUseTolerance = USE_TOLERANCE;
130 
131  using InfoType = HitInfo;
132 
135  float myTolerance;
136 };
137 
138 template<uint NAXES,typename SUBCLASS>
139 template<bool USE_TOLERANCE>
140 struct BVHBase<NAXES,SUBCLASS>::SingleHitAndNormalFunctor
141 {
143  HitInfoAndNormal &hit_info) noexcept
144  : myHitInfo(hit_info)
145  , myNestingArrayBase(hit_info.myNestedItemIndices ? hit_info.myNestedItemIndices->size() : 0)
146  {}
147  SYS_FORCE_INLINE void noHit() noexcept
148  {
149  myHitInfo.myItemIndex = -1;
150  myHitInfo.myUVW.assign(0,0,0);
151  myHitInfo.myT = -1.0f;
152  }
154  const UT_Vector3 &hit_uvw,
155  const float t,
156  const uint index,
157  float &limit_t) noexcept
158  {
159  myHitInfo.myItemIndex = index;
160  myHitInfo.myUVW = hit_uvw;
161  // Clear local portion of nesting array
162  if (myHitInfo.myNestedItemIndices)
163  myHitInfo.myNestedItemIndices->setSize(myNestingArrayBase);
164  myHitInfo.myT = t;
165  limit_t = t;
166  }
168  {
169  hit_info.myNestedItemIndices = myHitInfo.myNestedItemIndices;
170  }
172  {
173  return myHitInfo.myNestedItemIndices;
174  }
175  SYS_FORCE_INLINE const VectorType &getNormal(const HitInfoAndNormal &hit_info) const noexcept
176  { return hit_info.myNml; }
177  SYS_FORCE_INLINE void setNormal(const VectorType &nml) noexcept
178  {
179  myHitInfo.myNml = nml;
180  }
181  SYS_FORCE_INLINE void setNormal(HitInfoAndNormal &hit_info, const VectorType &nml) const noexcept
182  {
183  hit_info.myNml = nml;
184  }
186  SYS_FORCE_INLINE exint nestingArrayBase() const noexcept { return myNestingArrayBase; }
187  SYS_FORCE_INLINE UT_Vector3 &lastUVW() noexcept { return myHitInfo.myUVW; }
188 
189  constexpr static bool theAllHits = false;
190  constexpr static bool theNeedsNormal = true;
191  constexpr static bool theUseTolerance = USE_TOLERANCE;
192 
194 
197  float myTolerance;
198 };
199 
200 template<uint NAXES,typename SUBCLASS>
201 template<bool USE_TOLERANCE>
202 struct BVHBase<NAXES,SUBCLASS>::AllHitsFunctor
203 {
205  UT_Array<HitInfo> &hit_info,
206  UT_Array<exint> *nesting_temp_array) noexcept
207  : myHitInfo(hit_info)
208  , myNestingTempArray(nesting_temp_array)
209  {}
210  SYS_FORCE_INLINE void noHit() noexcept
211  {
212  // Just don't add a hit.
213  }
215  const UT_Vector3 &hit_uvw,
216  const float t,
217  const uint index,
218  float &limit_t) noexcept
219  {
220  HitInfo hit_info;
221  if (!myNestingTempArray || myNestingTempArray->isEmpty())
222  {
223  // Not nested
224  hit_info.myItemIndex = index;
225  }
226  else
227  {
228  // myItemIndex is the top-most index.
229  hit_info.myItemIndex = (*myNestingTempArray)[0];
230  UT_Array<exint> *new_array = new UT_Array<exint>();
231  hit_info.myNestedItemIndices = new_array;
232  exint n = myNestingTempArray->size();
233  new_array->setSizeNoInit(n);
234  for (exint i = 1; i < n; ++i)
235  {
236  (*new_array)[i-1] = (*myNestingTempArray)[i];
237  }
238  (*new_array)[n-1] = index;
239  }
240  hit_info.myUVW = hit_uvw;
241  hit_info.myT = t;
242  myHitInfo.append(hit_info);
243  }
244  SYS_FORCE_INLINE void setNestingArrayInto(HitInfo &hit_info) noexcept {}
246  {
247  return myNestingTempArray;
248  }
249  SYS_FORCE_INLINE VectorType getNormal(const HitInfo &hit_info) const noexcept
250  { return VectorType(); }
251  SYS_FORCE_INLINE void setNormal(const VectorType &nml) noexcept {}
252  SYS_FORCE_INLINE void setNormal(HitInfo &hit_info, const VectorType &nml) const noexcept {}
253  SYS_FORCE_INLINE UT_Array<HitInfo> *getHitArray() noexcept { return &myHitInfo; }
254  SYS_FORCE_INLINE exint nestingArrayBase() const noexcept { return 0; }
255  SYS_FORCE_INLINE UT_Vector3 &lastUVW() noexcept { return myHitInfo.last().myUVW; }
256 
257  constexpr static bool theAllHits = true;
258  constexpr static bool theNeedsNormal = false;
259  constexpr static bool theUseTolerance = USE_TOLERANCE;
260 
261  /// NOTE: Intentionally not the array type. See use in GU_BVH::intersectPrim
262  using InfoType = HitInfo;
263 
266  float myTolerance;
267 };
268 
269 template<uint NAXES,typename SUBCLASS>
270 template<bool USE_TOLERANCE>
271 struct BVHBase<NAXES,SUBCLASS>::AllHitsAndNormalsFunctor
272 {
274  UT_Array<HitInfoAndNormal> &hit_info,
275  UT_Array<exint> *nesting_temp_array) noexcept
276  : myHitInfo(hit_info)
277  , myNestingTempArray(nesting_temp_array)
278  {}
279  SYS_FORCE_INLINE void noHit() noexcept
280  {
281  // Just don't add a hit.
282  }
284  const UT_Vector3 &hit_uvw,
285  const float t,
286  const uint index,
287  float &limit_t) noexcept
288  {
289  HitInfoAndNormal hit_info;
290  if (!myNestingTempArray || myNestingTempArray->isEmpty())
291  {
292  // Not nested
293  hit_info.myItemIndex = index;
294  }
295  else
296  {
297  // myItemIndex is the top-most index.
298  hit_info.myItemIndex = (*myNestingTempArray)[0];
299  UT_Array<exint> *new_array = new UT_Array<exint>();
300  hit_info.myNestedItemIndices = new_array;
301  exint n = myNestingTempArray->size();
302  new_array->setSizeNoInit(n);
303  for (exint i = 1; i < n; ++i)
304  {
305  (*new_array)[i-1] = (*myNestingTempArray)[i];
306  }
307  (*new_array)[n-1] = index;
308  }
309  hit_info.myUVW = hit_uvw;
310  hit_info.myT = t;
311  myHitInfo.append(hit_info);
312  }
315  {
316  return myNestingTempArray;
317  }
318  SYS_FORCE_INLINE VectorType getNormal(const HitInfoAndNormal &hit_info) const noexcept
319  { return hit_info.myNml; }
320  SYS_FORCE_INLINE void setNormal(const VectorType &nml) noexcept
321  {
322  myHitInfo.last().myNml = nml;
323  }
324  SYS_FORCE_INLINE void setNormal(HitInfoAndNormal &hit_info, const VectorType &nml) const noexcept
325  {
326  hit_info.myNml = nml;
327  }
328  SYS_FORCE_INLINE UT_Array<HitInfoAndNormal> *getHitArray() noexcept { return &myHitInfo; }
329  SYS_FORCE_INLINE exint nestingArrayBase() const noexcept { return 0; }
330  SYS_FORCE_INLINE UT_Vector3 &lastUVW() noexcept { return myHitInfo.last().myUVW; }
331 
332  constexpr static bool theAllHits = true;
333  constexpr static bool theNeedsNormal = true;
334  constexpr static bool theUseTolerance = USE_TOLERANCE;
335 
336  /// NOTE: Intentionally not the array type. See use in GU_BVH::intersectPrim
338 
341  float myTolerance;
342 };
343 
344 template<uint NAXES,typename SUBCLASS>
345 template<bool farthest,bool rm_backface,bool reverse,typename HitInfoType>
347  const VectorType &origin,
348  const VectorType &direction,
349  HitInfoType &hit_info,
350  float outer_tmin,
351  float outer_tmax) const noexcept
352 {
354  sendRayGeneric<farthest,rm_backface,reverse>(origin, direction, functor, outer_tmin, outer_tmax);
355 }
356 
357 template<uint NAXES,typename SUBCLASS>
358 template<bool farthest,bool rm_backface,bool reverse,typename HitInfoType>
360  const VectorType &origin,
361  const VectorType &direction,
362  HitInfoType &hit_info,
363  float default_radius,
364  float outer_tmin,
365  float outer_tmax) const noexcept
366 {
367  if (!myHasCurvesOrPoints || !myRadii.isEmpty() || default_radius == 0)
368  {
369  // Either there are no points/curves, or we have explicit radii.
370  sendRay<farthest,rm_backface,reverse>(origin, direction, hit_info, outer_tmin, outer_tmax);
371  return;
372  }
374  functor.myTolerance = default_radius;
375  sendRayGeneric<farthest,rm_backface,reverse>(origin, direction, functor, outer_tmin, outer_tmax);
376 }
377 
378 template<uint NAXES,typename SUBCLASS>
379 template<bool rm_backface,bool reverse,bool sort,typename HitInfoType>
381  const VectorType &origin,
382  const VectorType &direction,
383  UT_Array<HitInfoType> &hit_info,
384  UT_Array<exint> *nesting_temp_array,
385  float duplicate_tolerance,
386  float outer_tmin,
387  float outer_tmax) const noexcept
388 {
389  UT_ASSERT_MSG(sort || duplicate_tolerance==0, "Can't remove duplicates if we're not sorting!");
390 
392  sendRayGeneric<false,rm_backface,reverse>(origin, direction, functor, outer_tmin, outer_tmax);
393 
394  if (!sort || hit_info.size() <= 1)
395  return;
396 
397  // Sort by t, breaking ties by index
398  hit_info.sort([](const HitInfo &a, const HitInfo &b) -> bool {
399  if (a.myT < b.myT)
400  return true;
401  if (a.myT > b.myT)
402  return false;
403  // FIXME: Check nesting array, if non-null!!!
404  return (a.myItemIndex < b.myItemIndex);
405  });
406 
407  if (duplicate_tolerance <= 0)
408  return;
409 
410  float prev_t = hit_info[0].myT;
411  exint desti = 1;
412  for (exint i = 1, n = hit_info.size(); i < n; ++i)
413  {
414  float t = hit_info[i].myT;
415  if (t-prev_t < duplicate_tolerance)
416  continue;
417  if (desti != i)
418  hit_info[desti] = hit_info[i];
419  ++desti;
420  }
421  hit_info.setSize(desti);
422 }
423 
424 template<uint NAXES,typename SUBCLASS>
425 template<bool rm_backface,bool reverse,bool sort,typename HitInfoType>
427  const VectorType &origin,
428  const VectorType &direction,
429  UT_Array<HitInfoType> &hit_info,
430  float default_radius,
431  UT_Array<exint> *nesting_temp_array,
432  float duplicate_tolerance,
433  float outer_tmin,
434  float outer_tmax) const noexcept
435 {
436  if (!myHasCurvesOrPoints || !myRadii.isEmpty() || default_radius == 0)
437  {
438  // Either there are no points/curves, or we have explicit radii.
439  sendRayAll<rm_backface,reverse,sort>(origin, direction, hit_info, nesting_temp_array, duplicate_tolerance, outer_tmin, outer_tmax);
440  return;
441  }
442 
443  UT_ASSERT_MSG(sort || duplicate_tolerance==0, "Can't remove duplicates if we're not sorting!");
444 
446  functor.myTolerance = default_radius;
447  sendRayGeneric<false,rm_backface,reverse>(origin, direction, functor, outer_tmin, outer_tmax);
448 
449  if (!sort || hit_info.size() <= 1)
450  return;
451 
452  // Sort by t, breaking ties by index
453  hit_info.sort([](const HitInfo &a, const HitInfo &b) -> bool {
454  if (a.myT < b.myT)
455  return true;
456  if (a.myT > b.myT)
457  return false;
458  // FIXME: Check nesting array, if non-null!!!
459  return (a.myItemIndex < b.myItemIndex);
460  });
461 
462  if (duplicate_tolerance <= 0)
463  return;
464 
465  float prev_t = hit_info[0].myT;
466  exint desti = 1;
467  for (exint i = 1, n = hit_info.size(); i < n; ++i)
468  {
469  float t = hit_info[i].myT;
470  if (t-prev_t < duplicate_tolerance)
471  continue;
472  if (desti != i)
473  hit_info[desti] = hit_info[i];
474  ++desti;
475  }
476  hit_info.setSize(desti);
477 }
478 
479 template<uint NAXES,typename SUBCLASS>
480 template<bool farthest,bool rm_backface,bool reverse,typename FUNCTOR>
481 void BVHBase<NAXES,SUBCLASS>::sendRayGeneric(VectorType origin, VectorType direction, FUNCTOR &hit_info, float outer_tmin, float outer_tmax) const noexcept
482 {
483  using NodeType = typename UT_BVH<BVH_N>::Node;
484  const NodeType *nodes = myTree.getNodes();
485  const uint nnodes = myTree.getNumNodes();
486  float length = direction.normalize();
487 
488  hit_info.noHit();
489  if (nnodes == 0 || length == 0 || !SYSisFinite(length) || !origin.isFinite())
490  {
491  // Nothing to hit
492  return;
493  }
494 
495  const uint num_points = numPoints();
496 
498  for (int i = 0; i < NAXES; ++i)
499  sign[i] = (direction[i] < 0);
500 
501  VectorType inverse_direction;
502  for (int i = 0; i < NAXES; ++i)
503  {
504  // This is deliberately different from SYSsafediv - since for plane
505  // intersection, we need to generate a large result when dividing by 0.
506  inverse_direction[i] = (direction[i] == 0) ? std::numeric_limits<float>::max() : 1/direction[i];
507  }
508 
509  // For intersecting quads, we'll cache a coordinate frame.
510  int max_dir = -1;
511  VectorType N0;
512  VectorType N1;
513 
514  struct StackEntry
515  {
516  uint myNode;
517  float myTMin;
518 
519  SYS_FORCE_INLINE StackEntry() noexcept {}
520  SYS_FORCE_INLINE StackEntry(uint node, float tmin) noexcept
521  : myNode(node)
522  , myTMin(tmin)
523  {}
524  };
525 
526 #if GEO_BVH_INTERLEAVED
528  for (uint axis = 0; axis < NAXES; ++axis)
529  {
530  vorigin[axis] = v4uf(origin[axis]);
531  }
532  UT_FixedVector<v4uf,NAXES> vinverse_direction;
533  for (uint axis = 0; axis < NAXES; ++axis)
534  {
535  vinverse_direction[axis] = v4uf(inverse_direction[axis]);
536  }
537  v4uf vtolerance;
538  if (hit_info.theUseTolerance)
539  vtolerance = v4uf(hit_info.myTolerance);
540 #else
541  const BoxType &box = myNodeBoxes[0];
542  box.intersect(outer_tmin, outer_tmax, sign, origin, inverse_direction);
543 
544  if (outer_tmin > outer_tmax)
545  {
546  // No hits
547  hit_info.noHit();
548  return;
549  }
550 #endif
551 
552  //UT_Vector3 hit_uvw;
553  //exint hit_index = -1;
554 
556 #if GEO_BVH_INTERLEAVED
557  stack.append(StackEntry(NodeType::markInternal(0),(!farthest) ? outer_tmin : outer_tmax));
558 #else
559  stack.append(StackEntry(0,outer_tmin));
560 #endif
561 
562  do
563  {
564  StackEntry entry = stack.last();
565  stack.removeLast();
566 
567  uint next_node = entry.myNode;
568  // When farthest is true, entry.myTMin is actually a tmax.
569  if ((!farthest) ? (entry.myTMin >= outer_tmax) : (entry.myTMin <= outer_tmin))
570  continue;
571 
572  while (true)
573  {
574 #if GEO_BVH_INTERLEAVED
575  if (NodeType::isInternal(next_node))
576  {
577  UT_ASSERT_MSG_P(next_node != NodeType::EMPTY, "How did a ray hit an empty box?");
578 
579  next_node = NodeType::getInternalNum(next_node);
580  const BoxType &box = myNodeBoxes[next_node];
581  v4uf tmin(outer_tmin); v4uf tmax(outer_tmax);
582  if (!hit_info.theUseTolerance)
583  box.intersect(tmin, tmax, sign, vorigin, vinverse_direction);
584  else
585  box.intersectTol(tmin, tmax, sign, vorigin, vinverse_direction, vtolerance);
586 #if 0
587  {
588  uint axis_sign = sign[0];
589  v4uf t1 = (box.vals[0][axis_sign] - vorigin[0]) * vinverse_direction[0];
590  tmin = SYSmax(t1, tmin);
591  v4uf t2 = (box.vals[0][axis_sign^1] - vorigin[0]) * vinverse_direction[0];
592  tmax = SYSmin(t2, tmax);
593  }
594  {
595  uint axis_sign = sign[1];
596  v4uf t1 = (box.vals[1][axis_sign] - vorigin[1]) * vinverse_direction[1];
597  tmin = SYSmax(t1, tmin);
598  v4uf t2 = (box.vals[1][axis_sign^1] - vorigin[1]) * vinverse_direction[1];
599  tmax = SYSmin(t2, tmax);
600  }
601  {
602  uint axis_sign = sign[2];
603  v4uf t1 = (box.vals[2][axis_sign] - vorigin[2]) * vinverse_direction[2];
604  tmin = SYSmax(t1, tmin);
605  v4uf t2 = (box.vals[2][axis_sign^1] - vorigin[2]) * vinverse_direction[2];
606  tmax = SYSmin(t2, tmax);
607  }
608 #endif
609  // NOTE: DO NOT change this to <, else axis-aligned polygons could be missed.
610  v4uu hit_mask = (tmin <= tmax);
611  const uint hit_bits = _mm_movemask_ps(V4SF(hit_mask.vector));
612  if (hit_bits == 0)
613  break;
614  const NodeType &node = nodes[next_node];
615  if (!(hit_bits & (hit_bits-1)))
616  {
617  // Only 1 bit set
618  uint local_index = SYSfirstBitSet(hit_bits);
619 #if 1
620  next_node = node.child[local_index];
621 #else
622  float local_tmin = tmins[local_index];
623  uint child_index = node.child[local_index];
624  if (!stack_size || ((!farthest) ? (stack_last->myTMin >= local_tmin) : (stack_last->myTMin <= local_tmin)))
625  next_node = child_index;
626  else
627  {
628  next_node = stack_last->myNode;
629  stack_last->myNode = child_index;
630  stack_last->myTMin = local_tmin;
631  }
632 #endif
633  continue;
634  }
635 
636  exint stack_size = stack.size();
637  StackEntry *stack_last = stack.data()+stack_size-1;
638 
639  // If we're going to be adding to the stack, we might as
640  // well prune anything from the end of the stack that's
641  // too far, to possibly reduce reallocations.
642  // That said, this probably won't happen often, since
643  // it requires hitting 2 child boxes in the current node
644  // when the next node in the stack must be farther than an
645  // existing hit.
646  // When farthest is true, stack_last->myTMin is actually a tmax.
647  while (stack_size != 0 && ((!farthest) ? (stack_last->myTMin >= outer_tmax) : (stack_last->myTMin <= outer_tmin)))
648  {
649  --stack_size;
650  --stack_last;
651  stack.removeLast();
652  }
653  static constexpr uint two_bit_indices[16][2] = {
654  {4, 4}, {4, 4}, {4, 4}, {0, 1},
655  {4, 4}, {0, 2}, {1, 2}, {0, 1},
656  {4, 4}, {0, 3}, {1, 3}, {0, 1},
657  {2, 3}, {0, 2}, {1, 2}, {0, 1}
658  };
659  static constexpr uint third_bit_index[16] = {
660  4, 4, 4, 4,
661  4, 4, 4, 2,
662  4, 4, 4, 3,
663  4, 3, 3, 2
664  };
665  // When farthest is true, these are tmax's.
666  union { v4sf tminv; float tmins[4]; };
667  tminv = (!farthest) ? tmin.vector : tmax.vector;
668  uint local_index0 = two_bit_indices[hit_bits][0];
669  uint local_index1 = two_bit_indices[hit_bits][1];
670  if (third_bit_index[hit_bits] == 4)
671  {
672  // Only 2 bits set
673  float t0 = tmins[local_index0];
674  float t1 = tmins[local_index1];
675  uint child0 = node.child[local_index0];
676  uint child1 = node.child[local_index1];
677  if ((!farthest) ? (t0 > t1) : (t0 < t1))
678  {
679  uint childtmp = child0;
680  child0 = child1;
681  child1 = childtmp;
682  float tmp = t0;
683  t0 = t1;
684  t1 = tmp;
685  }
686 
687  // When farthest is true, stack_last->myTMin is actually a tmax.
688  if (!stack_size || ((!farthest) ? (stack_last->myTMin >= t0) : (stack_last->myTMin <= t0)))
689  {
690  next_node = child0;
691 
692  // Inserting t1
693  // Check end of stack first, since it's most likely that the box will go near the end.
694  if (!stack_size || ((!farthest) ? (stack_last->myTMin >= t1) : (stack_last->myTMin <= t1)))
695  {
696  stack.append(StackEntry(child1, t1));
697  }
698  else
699  {
700  // Insert in sorted order, but go back at most a constant
701  // number of entries, to avoid n^2 behaviour.
702  exint i;
703  exint limiti = SYSmax(0, stack_size-64);
704  for (i = stack_size-2; i >= limiti; --i)
705  {
706  if ((!farthest) ? (stack[i].myTMin >= t1) : (stack[i].myTMin <= t1))
707  {
708  stack.insert(StackEntry(child1, t1), i+1);
709  break;
710  }
711  }
712  if (i < limiti)
713  {
714  stack.insert(StackEntry(child1, t1), i+1);
715  }
716  }
717  }
718  else
719  {
720  next_node = stack_last->myNode;
721  stack_last->myNode = child1;
722  stack_last->myTMin = t1;
723  stack.append(StackEntry(child0, t0));
724  }
725  continue;
726  }
727 
728  // 3-4 bits set
729  uint nhit = (hit_bits == 0xF) ? 4 : 3;
730  uint local_index2 = third_bit_index[hit_bits];
731  uint children[BVH_N] = {
732  node.child[local_index0],
733  node.child[local_index1],
734  node.child[local_index2],
735  node.child[3]
736  };
737  tmins[0] = tmins[local_index0];
738  tmins[1] = tmins[local_index1];
739  tmins[2] = tmins[local_index2];
740  //tmins[3] = tmins[3];
741 
742  float new_tmin;
743  if (!stack_size || ((!farthest) ? (stack_last->myTMin >= tmins[0]) : (stack_last->myTMin <= tmins[0])))
744  {
745  new_tmin = tmins[0];
746  next_node = children[0];
747  }
748  else
749  {
750  new_tmin = stack_last->myTMin;
751  next_node = stack_last->myNode;
752  stack_last->myTMin = tmins[0];
753  stack_last->myNode = children[0];
754  }
755  for (uint hit = 1; hit < nhit; ++hit)
756  {
757  float t = tmins[hit];
758  uint child = children[hit];
759  if ((!farthest) ? (t < new_tmin) : (t > new_tmin))
760  {
761  float tmpt = new_tmin;
762  uint tmpchild = next_node;
763  new_tmin = t;
764  next_node = child;
765  t = tmpt;
766  child = tmpchild;
767  }
768 
769  // Check end of stack first, since it's most likely that the box will go near the end.
770  if (!stack_size || ((!farthest) ? (stack_last->myTMin >= t) : (stack_last->myTMin <= t)))
771  {
772  stack.append(StackEntry(child, t));
773  }
774  else
775  {
776  // Insert in sorted order, but go back at most a constant
777  // number of entries, to avoid n^2 behaviour.
778  exint i;
779  exint limiti = SYSmax(0, stack_size-64);
780  for (i = stack_size-2; i >= limiti; --i)
781  {
782  if ((!farthest) ? (stack[i].myTMin >= t) : (stack[i].myTMin <= t))
783  {
784  stack.insert(StackEntry(child, t), i+1);
785  break;
786  }
787  }
788  if (i < limiti)
789  {
790  stack.insert(StackEntry(child, t), i+1);
791  }
792  }
793  stack_last = stack.data()+stack_size;
794  ++stack_size;
795  }
796  continue;
797  }
798  uint index = next_node;//myIndices[next_node];
799 #else
800  const NodeType &node = nodes[next_node];
801  uint children[BVH_N];
802  float tmins[BVH_N];
803  uint nnodehits = 0;
804  for (uint i = 0; i < BVH_N; ++i)
805  {
806  const uint itemi = node.child[i];
807  if (NodeType::isInternal(itemi))
808  {
809  if (itemi == NodeType::EMPTY)
810  continue;
811 
812  // Internal node: intersect against box
813  const uint childi = NodeType::getInternalNum(itemi);
814  const BoxType &box = myNodeBoxes[childi];
815  float tmin = outer_tmin; float tmax = outer_tmax;
816  box.intersect(tmin, tmax, sign, origin, inverse_direction);
817  // NOTE: DO NOT change this to >=, else axis-aligned polygons could be missed.
818  if (tmin > tmax)
819  continue;
820 
821  children[nnodehits] = childi;
822  tmins[nnodehits] = tmin;
823  ++nnodehits;
824  }
825  else
826  {
827  // Leaf item: intersect against item
828  uint index = itemi;//myIndices[itemi];
829 #endif
830  if (!SUBCLASS::theHasPrimitives || index < num_points)
831  {
832  // Points as spheres
833  //if (myRadii.isValid())
834  if (!myRadii.isEmpty() || myRadAttrib.isValid() || hit_info.theUseTolerance)
835  {
836  // The point tree subclass reorders myPositions and myRadii
837  // to match the indices in the tree, so we don't need to remap them.
838  exint ptarrayindex = (SUBCLASS::theReordersPositions) ? exint(index) : exint(myPoints(index));
839  const bool use_pos_array = !myPositions.isEmpty();
840  const VectorType pos = use_pos_array ? myPositions[ptarrayindex] : myPosAttrib.get(GA_Offset(ptarrayindex));
841  float radius;
842  if (hit_info.theUseTolerance)
843  radius = hit_info.myTolerance;
844  else if (myRadii.isEmpty())
845  radius = myRadAttrib.get(GA_Offset(ptarrayindex));
846  else
847  radius = ((myRadii.size() == 1) ? myRadii[0] : myRadii[ptarrayindex]);
848  // We already checked for zero radius if theUseTolerance is true
849  if (hit_info.theUseTolerance || radius != 0)
850  {
851  float t0; float t1;
852  const VectorType rel_origin = origin - pos;
853  bool ishit = geoIntersectSphere(rel_origin, direction, radius, t0, t1);
854  if (!ishit)
855 #if GEO_BVH_INTERLEAVED
856  break;
857 #else
858  continue;
859 #endif
860 
861  const float invradius = 1.0f/radius;
862  if ((t0 <= outer_tmax) && (t0 >= outer_tmin))
863  {
864  VectorType p = rel_origin + t0*direction;
865  p *= invradius;
866  // NOTE: p is the normal
867  if (!rm_backface || (dot(p,direction) <= 0) != reverse)
868  {
869  hit_info.insertHit(
870  UT_Vector3(p[0], p[1], (NAXES==3) ? p[2] : 0),
871  t0, index,
872  (!farthest) ? outer_tmax : outer_tmin);
873  if (hit_info.theNeedsNormal)
874  hit_info.setNormal(p);
875  }
876  }
877 
878  if ((t1 <= outer_tmax) && (t1 >= outer_tmin))
879  {
880  VectorType p = rel_origin + t1*direction;
881  p *= invradius;
882  // NOTE: p is the normal
883  if (!rm_backface || (dot(p,direction) <= 0) != reverse)
884  {
885  hit_info.insertHit(
886  UT_Vector3(p[0], p[1], (NAXES==3) ? p[2] : 0),
887  t1, index,
888  (!farthest) ? outer_tmax : outer_tmin);
889  if (hit_info.theNeedsNormal)
890  hit_info.setNormal(p);
891  }
892  }
893  }
894  }
895  }
896  else
897  {
898 #if !GEO_BVH_INTERLEAVED
899  bool ishit =
900 #endif
901  subclass()->template intersectPrim<farthest,rm_backface,reverse>(
902  index, origin, direction, inverse_direction, max_dir, N0, N1,
903  outer_tmax, outer_tmin, hit_info);
904 #if !GEO_BVH_INTERLEAVED
905  if (!ishit)
906  continue;
907 #endif
908  }
909 #if GEO_BVH_INTERLEAVED
910  break;
911 #endif
912 #if !GEO_BVH_INTERLEAVED
913  }
914  }
915  if (nnodehits == 0)
916  break;
917  exint stack_size = stack.size();
918  StackEntry *stack_last = stack.data()+stack_size-1;
919  if (nnodehits == 1)
920  {
921  uint child_index = children[0];
922  if (!stack_size || stack_last->myTMin >= tmins[0])
923  next_node = child_index;
924  else
925  {
926  next_node = stack_last->myNode;
927  stack_last->myNode = child_index;
928  stack_last->myTMin = tmins[0];
929  }
930  }
931  else if (BVH_N == 2 || nnodehits == 2)
932  {
933  const uint local_index = (tmins[0] >= tmins[1]);
934  next_node = children[local_index];
935  const uint insert_node = children[!local_index];
936  const float insert_tmin = tmins[!local_index];
937  // Check end of stack first, since it's most likely that the box will go near the end.
938  if (!stack_size || stack_last->myTMin <= insert_tmin)
939  {
940  stack.append(StackEntry(insert_node, insert_tmin));
941  }
942  else
943  {
944  // Insert in sorted order, but go back at most a constant
945  // number of entries, to avoid n^2 behaviour.
946  exint i;
947  exint limiti = SYSmax(0, stack_size-64);
948  for (i = stack_size-2; i >= limiti; --i)
949  {
950  if (stack[i].myTMin <= insert_tmin)
951  {
952  stack.insert(StackEntry(insert_node, insert_tmin), i+1);
953  break;
954  }
955  }
956  if (i < limiti)
957  {
958  stack.insert(StackEntry(insert_node, insert_tmin), i+1);
959  }
960  }
961  }
962  else
963  {
964  // Sort/insert and keep closest
965  SYS_STATIC_ASSERT_MSG(BVH_N==2, "FIXME: Implement case of BVH_N>2!!!");
966 
967  }
968 #endif
969  }
970  } while (!stack.isEmpty());
971 
972 #if 0
973  if (hit_index >= 0)
974  {
975  hit_info.myItemIndex = hit_index;
976  hit_info.myUVW = hit_uvw;
977  hit_info.myT = (!farthest) ? outer_tmax : outer_tmin;
978  }
979  else
980  {
981  hit_info.myItemIndex = -1;
982  hit_info.myUVW.assign(0,0,0);
983  hit_info.myT = -1.0f;
984  }
985 #endif
986 }
987 
988 template<uint NAXES,typename SUBCLASS>
989 template<bool farthest,typename QUERY_POINT>
991  const QUERY_POINT &query_point,
992  UT::BVHOrderedStack &stack,
993  UT::BVHOrderedStack &output_queue,
994  exint max_points,
995  float max_dist_squared) const noexcept
996 {
997  const v4uu* node_nitems_v = (const v4uu*)myNodeNItems.get();
998 
999  const bool use_pos_array = !myPositions.isEmpty();
1000  if (use_pos_array)
1001  {
1002  if (myRadii.size() == 0)
1003  {
1004  if (myRadAttrib.isValid())
1005  {
1006  UT::findClosestPoints<farthest,true,true>(myTree, myNodeBoxes.get(), node_nitems_v,
1007  myPoints.getArray(), myPositions, query_point, stack, output_queue,
1008  myRadAttrib, max_points, max_dist_squared);
1009  }
1010  else
1011  {
1012  UT::findClosestPoints<farthest,true,true>(myTree, myNodeBoxes.get(), node_nitems_v,
1013  myPoints.getArray(), myPositions, query_point, stack, output_queue,
1014  UT::ZeroRadiiWrapper{}, max_points, max_dist_squared);
1015  }
1016  }
1017  else if (myRadii.size() == 1)
1018  {
1019  UT::findClosestPoints<farthest,true,true>(myTree, myNodeBoxes.get(), node_nitems_v,
1020  myPoints.getArray(), myPositions, query_point, stack, output_queue,
1021  UT::SingleRadiusWrapper{myRadii[0]}, max_points, max_dist_squared);
1022  }
1023  else
1024  {
1025  UT::findClosestPoints<farthest,true,true>(myTree, myNodeBoxes.get(), node_nitems_v,
1026  myPoints.getArray(), myPositions, query_point, stack, output_queue,
1027  myRadii, max_points, max_dist_squared);
1028  }
1029  }
1030  else
1031  {
1032  if (myRadii.size() == 0)
1033  {
1034  if (myRadAttrib.isValid())
1035  {
1036  UT::findClosestPoints<farthest,true,true>(myTree, myNodeBoxes.get(), node_nitems_v,
1037  myPoints.getArray(), myPosAttrib, query_point, stack, output_queue,
1038  myRadAttrib, max_points, max_dist_squared);
1039  }
1040  else
1041  {
1042  UT::findClosestPoints<farthest,true,true>(myTree, myNodeBoxes.get(), node_nitems_v,
1043  myPoints.getArray(), myPosAttrib, query_point, stack, output_queue,
1044  UT::ZeroRadiiWrapper{}, max_points, max_dist_squared);
1045  }
1046  }
1047  else if (myRadii.size() == 1)
1048  {
1049  UT::findClosestPoints<farthest,true,true>(myTree, myNodeBoxes.get(), node_nitems_v,
1050  myPoints.getArray(), myPosAttrib, query_point, stack, output_queue,
1051  UT::SingleRadiusWrapper{myRadii[0]}, max_points, max_dist_squared);
1052  }
1053  else
1054  {
1055  UT::findClosestPoints<farthest,true,true>(myTree, myNodeBoxes.get(), node_nitems_v,
1056  myPoints.getArray(), myPosAttrib, query_point, stack, output_queue,
1057  myRadii, max_points, max_dist_squared);
1058  }
1059  }
1060 }
1061 
1062 template<uint NAXES,typename SUBCLASS>
1064  VectorType origin, VectorType direction,
1065  const exint max_points, const float max_dist_squared,
1066  UT::BVHOrderedStack& output_queue) const noexcept
1067 {
1068  using PositionArrayType = UT_Array<VectorType>;
1069 
1070  SYS_STATIC_ASSERT(sizeof(myNodeNItems[0]) == sizeof(v4uu) && BVH_N == 4);
1071  UT::BVHOrderedStack stack;
1072  const UT::BVHQueryInfLine<NAXES> query_point{origin, direction};
1073  findMaximalPointsCommon<false>(
1074  query_point,
1075  stack,
1076  output_queue,
1077  max_points,
1078  max_dist_squared);
1079 }
1080 
1081 template<uint NAXES,typename SUBCLASS>
1083  VectorType p0, VectorType p1,
1084  const exint max_points, const float max_dist_squared,
1085  UT::BVHOrderedStack& output_queue) const noexcept
1086 {
1087  using PositionArrayType = UT_Array<VectorType>;
1088 
1089  SYS_STATIC_ASSERT(sizeof(myNodeNItems[0]) == sizeof(v4uu) && BVH_N == 4);
1090  UT::BVHOrderedStack stack;
1091  const UT::BVHQuerySegment<NAXES> query_point{p0, p1};
1092  findMaximalPointsCommon<false>(
1093  query_point,
1094  stack,
1095  output_queue,
1096  max_points,
1097  max_dist_squared);
1098 }
1099 
1100 template<uint NAXES,typename SUBCLASS>
1102  VectorType direction, const float angle, const exint max_points,
1103  const float max_dist_squared, UT::BVHOrderedStack& output_queue) const noexcept
1104 {
1105  using PositionArrayType = UT_Array<VectorType>;
1106 
1107  SYS_STATIC_ASSERT(sizeof(myNodeNItems[0]) == sizeof(v4uu) && BVH_N == 4);
1108  const v4uu* node_nitems_v = (const v4uu*)myNodeNItems.get();
1109  const bool use_pos_array = !myPositions.isEmpty();
1110  UT::BVHOrderedStack stack;
1111  if (myRadii.size() == 0 && !myRadAttrib.isValid())
1112  {
1113  const UT::ZeroRadiiWrapper radii{};
1114  if (use_pos_array)
1115  {
1117  query_point{origin, direction, angle, myPositions, radii};
1118  UT::findClosestPoints<false,true,true>(myTree, myNodeBoxes.get(), node_nitems_v,
1119  myPoints.getArray(), myPositions, query_point, stack, output_queue,
1120  radii, max_points, max_dist_squared);
1121  }
1122  else
1123  {
1125  query_point{origin, direction, angle, myPosAttrib, radii};
1126  UT::findClosestPoints<false,true,true>(myTree, myNodeBoxes.get(), node_nitems_v,
1127  myPoints.getArray(), myPosAttrib, query_point, stack, output_queue,
1128  radii, max_points, max_dist_squared);
1129  }
1130  }
1131  else if (myRadii.size() == 1)
1132  {
1133  const UT::SingleRadiusWrapper radii{myRadii[0]};
1134  if (use_pos_array)
1135  {
1137  query_point{origin, direction, angle, myPositions, radii};
1138  UT::findClosestPoints<false,true,true>(myTree, myNodeBoxes.get(), node_nitems_v,
1139  myPoints.getArray(), myPositions, query_point, stack, output_queue,
1140  radii, max_points, max_dist_squared);
1141  }
1142  else
1143  {
1145  query_point{origin, direction, angle, myPosAttrib, radii};
1146  UT::findClosestPoints<false,true,true>(myTree, myNodeBoxes.get(), node_nitems_v,
1147  myPoints.getArray(), myPosAttrib, query_point, stack, output_queue,
1148  radii, max_points, max_dist_squared);
1149  }
1150  }
1151  else if (myRadii.size() > 1)
1152  {
1153  if (use_pos_array)
1154  {
1156  query_point{origin, direction, angle, myPositions, myRadii};
1157  UT::findClosestPoints<false,true,true>(myTree, myNodeBoxes.get(), node_nitems_v,
1158  myPoints.getArray(), myPositions, query_point, stack, output_queue,
1159  myRadii, max_points, max_dist_squared);
1160  }
1161  else
1162  {
1164  query_point{origin, direction, angle, myPosAttrib, myRadii};
1165  UT::findClosestPoints<false,true,true>(myTree, myNodeBoxes.get(), node_nitems_v,
1166  myPoints.getArray(), myPosAttrib, query_point, stack, output_queue,
1167  myRadii, max_points, max_dist_squared);
1168  }
1169  }
1170  else
1171  {
1172  if (use_pos_array)
1173  {
1175  query_point{origin, direction, angle, myPositions, myRadAttrib};
1176  UT::findClosestPoints<false,true,true>(myTree, myNodeBoxes.get(), node_nitems_v,
1177  myPoints.getArray(), myPositions, query_point, stack, output_queue,
1178  myRadAttrib, max_points, max_dist_squared);
1179  }
1180  else
1181  {
1183  query_point{origin, direction, angle, myPosAttrib, myRadAttrib};
1184  UT::findClosestPoints<false,true,true>(myTree, myNodeBoxes.get(), node_nitems_v,
1185  myPoints.getArray(), myPosAttrib, query_point, stack, output_queue,
1186  myRadAttrib, max_points, max_dist_squared);
1187  }
1188  }
1189 }
1190 
1191 template<uint NAXES,typename SUBCLASS>
1192 template<bool farthest>
1193 void BVHBase<NAXES,SUBCLASS>::findClosest(VectorType origin, MinInfo &hit_info, float max_dist_squared) const noexcept
1194 {
1195  using NodeType = typename UT_BVH<BVH_N>::Node;
1196  const NodeType *nodes = myTree.getNodes();
1197  const uint nnodes = myTree.getNumNodes();
1198 
1199  if (nnodes == 0 || !origin.isFinite())
1200  {
1201  // Nothing to hit
1202  hit_info.myItemIndex = -1;
1203  hit_info.myUVW.assign(0,0,0);
1204  hit_info.myDistSquared = -1.0f;
1205  hit_info.myP = VectorType(typename VectorType::value_type(0));
1206  return;
1207  }
1208 
1209  UT_Array<exint> *nesting_array = hit_info.myNestedItemIndices;
1210  exint nesting_array_base = nesting_array ? nesting_array->size() : 0;
1211 
1212  const uint num_points = numPoints();
1213 
1214  struct StackEntry
1215  {
1216  uint myNode;
1217  float myDistSquared;
1218 
1219  SYS_FORCE_INLINE StackEntry() noexcept {}
1220  SYS_FORCE_INLINE StackEntry(uint node, float d2) noexcept
1221  : myNode(node)
1222  , myDistSquared(d2)
1223  {}
1224  };
1225 
1226 #if GEO_BVH_INTERLEAVED
1228  for (uint axis = 0; axis < NAXES; ++axis)
1229  {
1230  vorigin[axis] = v4uf(origin[axis]);
1231  }
1232 #else
1233  const BoxType &box = myNodeBoxes[0];
1234  float dist2 = (!farthest) ? box.minDistance2(origin) : box.maxDistance2(origin);
1235 
1236  // NOTE: When farthest is true, max_dist_squared is actually a minimum distance squared.
1237  if ((!farthest) ? (dist2 > max_dist_squared) : (dist2 < max_dist_squared))
1238  {
1239  // No hits
1240  hit_info.myItemIndex = -1;
1241  hit_info.myUVW.assign(0,0,0);
1242  hit_info.myDistSquared = -1.0f;
1243  hit_info.myP = VectorType(typename VectorType::value_type(0));
1244  return;
1245  }
1246 #endif
1247 
1248  UT_Vector3 hit_uvw;
1249  exint hit_index = -1;
1250  VectorType hit_position;
1251 
1252  // Be careful, because this is a fairly big buffer on the stack,
1253  // and there's the potential to recurse into packed primitives.
1254  // If we have deeply nested packed primitives, that could be an issue.
1256 #if GEO_BVH_INTERLEAVED
1257  stack.append(StackEntry(NodeType::markInternal(0),(!farthest) ? 0 : std::numeric_limits<float>::max()));
1258 #else
1259  stack.append(StackEntry(0,dist2));
1260 #endif
1261 
1262  do
1263  {
1264  StackEntry entry = stack.last();
1265  stack.removeLast();
1266 
1267  uint next_node = entry.myNode;
1268  // When farthest is true, max_dist_squared is actually a minimum distance squared.
1269  if ((!farthest) ? (entry.myDistSquared > max_dist_squared) : (entry.myDistSquared < max_dist_squared))
1270  continue;
1271 
1272  while (true)
1273  {
1274 #if GEO_BVH_INTERLEAVED
1275  if (NodeType::isInternal(next_node))
1276  {
1277  if (next_node == NodeType::EMPTY)
1278  break;
1279 
1280  next_node = NodeType::getInternalNum(next_node);
1281  const BoxType &box = myNodeBoxes[next_node];
1282  v4uf dist2 = (!farthest) ? box.minDistance2(vorigin) : box.maxDistance2(vorigin);
1283  v4uu hit_mask = (!farthest) ? (dist2 <= max_dist_squared) : (dist2 >= max_dist_squared);
1284  const uint hit_bits = _mm_movemask_ps(V4SF(hit_mask.vector));
1285  if (hit_bits == 0)
1286  break;
1287  const NodeType &node = nodes[next_node];
1288  if (!(hit_bits & (hit_bits-1)))
1289  {
1290  // Only 1 bit set
1291  uint local_index = SYSfirstBitSet(hit_bits);
1292 #if 1
1293  next_node = node.child[local_index];
1294 #else
1295  float local_d2 = d2s[local_index];
1296  uint child_index = node.child[local_index];
1297  if (!stack_size || ((!farthest) ? (stack_last->myDistSquared >= local_d2) : (stack_last->myDistSquared <= local_d2)))
1298  next_node = child_index;
1299  else
1300  {
1301  next_node = stack_last->myNode;
1302  stack_last->myNode = child_index;
1303  stack_last->myDistSquared = local_d2;
1304  }
1305 #endif
1306  continue;
1307  }
1308 
1309  exint stack_size = stack.size();
1310  StackEntry *stack_last = stack.data()+stack_size-1;
1311 
1312  // If we're going to be adding to the stack, we might as
1313  // well prune anything from the end of the stack that's
1314  // too far, to possibly reduce reallocations.
1315  // That said, this probably won't happen often, since
1316  // it requires hitting 2 child boxes in the current node
1317  // when the next node in the stack must be farther than an
1318  // existing hit.
1319  // When farthest is true, max_dist_squared is actually a minimum distance squared.
1320  while (stack_size != 0 && ((!farthest) ? (stack_last->myDistSquared > max_dist_squared) : (stack_last->myDistSquared < max_dist_squared)))
1321  {
1322  --stack_size;
1323  --stack_last;
1324  stack.removeLast();
1325  }
1326  static constexpr uint two_bit_indices[16][2] = {
1327  {4, 4}, {4, 4}, {4, 4}, {0, 1},
1328  {4, 4}, {0, 2}, {1, 2}, {0, 1},
1329  {4, 4}, {0, 3}, {1, 3}, {0, 1},
1330  {2, 3}, {0, 2}, {1, 2}, {0, 1}
1331  };
1332  static constexpr uint third_bit_index[16] = {
1333  4, 4, 4, 4,
1334  4, 4, 4, 2,
1335  4, 4, 4, 3,
1336  4, 3, 3, 2
1337  };
1338  // When farthest is true, these are tmax's.
1339  union { v4sf d2v; float d2s[4]; };
1340  d2v = dist2.vector;
1341  uint local_index0 = two_bit_indices[hit_bits][0];
1342  uint local_index1 = two_bit_indices[hit_bits][1];
1343  if (third_bit_index[hit_bits] == 4)
1344  {
1345  // Only 2 bits set
1346  float d20 = d2s[local_index0];
1347  float d21 = d2s[local_index1];
1348  uint child0 = node.child[local_index0];
1349  uint child1 = node.child[local_index1];
1350  if ((!farthest) ? (d20 > d21) : (d20 < d21))
1351  {
1352  uint childtmp = child0;
1353  child0 = child1;
1354  child1 = childtmp;
1355  float tmp = d20;
1356  d20 = d21;
1357  d21 = tmp;
1358  }
1359 
1360  if (!stack_size || ((!farthest) ? (stack_last->myDistSquared >= d20) : (stack_last->myDistSquared <= d20)))
1361  {
1362  next_node = child0;
1363 
1364  // Inserting d21
1365  // Check end of stack first, since it's most likely that the box will go near the end.
1366  if (!stack_size || ((!farthest) ? (stack_last->myDistSquared >= d21) : (stack_last->myDistSquared <= d21)))
1367  {
1368  stack.append(StackEntry(child1, d21));
1369  }
1370  else
1371  {
1372  // Insert in sorted order, but go back at most a constant
1373  // number of entries, to avoid n^2 behaviour.
1374  exint i;
1375  exint limiti = SYSmax(0, stack_size-64);
1376  for (i = stack_size-2; i >= limiti; --i)
1377  {
1378  if ((!farthest) ? (stack[i].myDistSquared >= d21) : (stack[i].myDistSquared <= d21))
1379  {
1380  stack.insert(StackEntry(child1, d21), i+1);
1381  break;
1382  }
1383  }
1384  if (i < limiti)
1385  {
1386  stack.insert(StackEntry(child1, d21), i+1);
1387  }
1388  }
1389  }
1390  else
1391  {
1392  next_node = stack_last->myNode;
1393  stack_last->myNode = child1;
1394  stack_last->myDistSquared = d21;
1395  stack.append(StackEntry(child0, d20));
1396  }
1397  continue;
1398  }
1399 
1400  // 3-4 bits set
1401  uint nhit = (hit_bits == 0xF) ? 4 : 3;
1402  uint local_index2 = third_bit_index[hit_bits];
1403  uint children[BVH_N] = {
1404  node.child[local_index0],
1405  node.child[local_index1],
1406  node.child[local_index2],
1407  node.child[3]
1408  };
1409  d2s[0] = d2s[local_index0];
1410  d2s[1] = d2s[local_index1];
1411  d2s[2] = d2s[local_index2];
1412  //d2s[3] = d2s[3];
1413 
1414  float new_d2;
1415  if (!stack_size || ((!farthest) ? (stack_last->myDistSquared >= d2s[0]) : (stack_last->myDistSquared <= d2s[0])))
1416  {
1417  new_d2 = d2s[0];
1418  next_node = children[0];
1419  }
1420  else
1421  {
1422  new_d2 = stack_last->myDistSquared;
1423  next_node = stack_last->myNode;
1424  stack_last->myDistSquared = d2s[0];
1425  stack_last->myNode = children[0];
1426  }
1427  for (uint hit = 1; hit < nhit; ++hit)
1428  {
1429  float d2 = d2s[hit];
1430  uint child = children[hit];
1431  if ((!farthest) ? (d2 < new_d2) : (d2 > new_d2))
1432  {
1433  float tmpd2 = new_d2;
1434  uint tmpchild = next_node;
1435  new_d2 = d2;
1436  next_node = child;
1437  d2 = tmpd2;
1438  child = tmpchild;
1439  }
1440 
1441  // Check end of stack first, since it's most likely that the box will go near the end.
1442  if (!stack_size || ((!farthest) ? (stack_last->myDistSquared >= d2) : (stack_last->myDistSquared <= d2)))
1443  {
1444  stack.append(StackEntry(child, d2));
1445  }
1446  else
1447  {
1448  // Insert in sorted order, but go back at most a constant
1449  // number of entries, to avoid n^2 behaviour.
1450  exint i;
1451  exint limiti = SYSmax(0, stack_size-64);
1452  for (i = stack_size-2; i >= limiti; --i)
1453  {
1454  if ((!farthest) ? (stack[i].myDistSquared >= d2) : (stack[i].myDistSquared <= d2))
1455  {
1456  stack.insert(StackEntry(child, d2), i+1);
1457  break;
1458  }
1459  }
1460  if (i < limiti)
1461  {
1462  stack.insert(StackEntry(child, d2), i+1);
1463  }
1464  }
1465  stack_last = stack.data()+stack_size;
1466  ++stack_size;
1467  }
1468  continue;
1469  }
1470  uint index = next_node;//myIndices[next_node];
1471 #else
1472  const NodeType &node = nodes[next_node];
1473  uint children[BVH_N];
1474  float d2s[BVH_N];
1475  uint nnodehits = 0;
1476  for (uint i = 0; i < BVH_N; ++i)
1477  {
1478  const uint itemi = node.child[i];
1479  if (NodeType::isInternal(itemi))
1480  {
1481  if (itemi == NodeType::EMPTY)
1482  continue;
1483 
1484  // Internal node: intersect against box
1485  const uint childi = NodeType::getInternalNum(itemi);
1486  const BoxType &box = myNodeBoxes[childi];
1487  float dist2 = (!farthest) ? box.minDistance2(origin) : box.maxDistance2(origin);
1488  if ((!farthest) ? (dist2 > min_dist_squared) : (dist2 < min_dist_squared))
1489  continue;
1490 
1491  children[nnodehits] = childi;
1492  d2s[nnodehits] = dist2;
1493  ++nnodehits;
1494  }
1495  else
1496  {
1497  // Leaf item: intersect against item
1498  uint index = itemi;//myIndices[itemi];
1499 #endif
1500  if (!SUBCLASS::theHasPrimitives || index < num_points)
1501  {
1502  // Points as spheres
1503  // The point tree subclass reorders myPositions and myRadii
1504  // to match the indices in the tree, so we don't need to remap them.
1505  exint ptarrayindex = (SUBCLASS::theReordersPositions) ? exint(index) : exint(myPoints(index));
1506  const bool use_pos_array = !myPositions.isEmpty();
1507  const VectorType pos = use_pos_array ? myPositions[ptarrayindex] : myPosAttrib.get(GA_Offset(ptarrayindex));
1508  //if (myRadii.isValid())
1509  float radius;
1510  if (myRadii.isEmpty())
1511  radius = myRadAttrib.isValid() ? myRadAttrib.get(GA_Offset(ptarrayindex)) : 0.0f;
1512  else
1513  radius = ((myRadii.size() == 1) ? myRadii[0] : myRadii[ptarrayindex]);
1514  VectorType displacement = origin-pos;
1515  float d2 = displacement.length2();
1516  if (radius == 0)
1517  {
1518  // Zero radius
1519  // When farthest is true, max_dist_squared is actually a minimum distance squared.
1520  if ((!farthest) ? (d2 < max_dist_squared) : (d2 > max_dist_squared))
1521  {
1522  max_dist_squared = d2;
1523  hit_index = index;
1524  hit_uvw.assign(0,0,0);
1525  hit_position = pos;
1526  }
1527  }
1528  else
1529  {
1530  float distance = SYSsqrt(d2) - SYSabs(radius);
1531  d2 = distance*distance;
1532  if ((!farthest) ? (d2 < max_dist_squared) : (d2 > max_dist_squared))
1533  {
1534  max_dist_squared = d2;
1535  hit_index = index;
1536  VectorType normal = displacement;
1537  normal.normalize();
1538  // Real normal is opposite the displacement if radius is negative.
1539  VectorType real_normal = (((radius > 0) != farthest) ? normal : -normal);
1540  hit_uvw[0] = real_normal[0];
1541  hit_uvw[1] = real_normal[1];
1542  hit_uvw[2] = (NAXES==3) ? real_normal[2] : 0;
1543 
1544  // hit_position needs to use normal in the direction of displacement.
1545  hit_position = pos;
1546  if (!farthest)
1547  hit_position -= radius*normal;
1548  else
1549  hit_position += radius*normal;
1550  }
1551  }
1552  }
1553  else
1554  {
1555  subclass()->template closestPrim<farthest>(
1556  index, origin, max_dist_squared,
1557  hit_index, hit_uvw, hit_position,
1558  vorigin, nesting_array, nesting_array_base);
1559  }
1560 #if GEO_BVH_INTERLEAVED
1561  break;
1562 #else
1563  }
1564  }
1565  if (nnodehits == 0)
1566  break;
1567  exint stack_size = stack.size();
1568  StackEntry *stack_last = stack.data()+stack_size-1;
1569  if (nnodehits == 1)
1570  {
1571  uint child_index = children[0];
1572  if (!stack_size || stack_last->myTMin >= tmins[0])
1573  next_node = child_index;
1574  else
1575  {
1576  next_node = stack_last->myNode;
1577  stack_last->myNode = child_index;
1578  stack_last->myTMin = tmins[0];
1579  }
1580  }
1581  else if (BVH_N == 2 || nnodehits == 2)
1582  {
1583  const uint local_index = (tmins[0] >= tmins[1]);
1584  next_node = children[local_index];
1585  const uint insert_node = children[!local_index];
1586  const float insert_tmin = tmins[!local_index];
1587  // Check end of stack first, since it's most likely that the box will go near the end.
1588  if (!stack_size || stack_last->myTMin <= insert_tmin)
1589  {
1590  stack.append(StackEntry(insert_node, insert_tmin));
1591  }
1592  else
1593  {
1594  // Insert in sorted order, but go back at most a constant
1595  // number of entries, to avoid n^2 behaviour.
1596  exint i;
1597  exint limiti = SYSmax(0, stack_size-64);
1598  for (i = stack_size-2; i >= limiti; --i)
1599  {
1600  if (stack[i].myTMin <= insert_tmin)
1601  {
1602  stack.insert(StackEntry(insert_node, insert_tmin), i+1);
1603  break;
1604  }
1605  }
1606  if (i < limiti)
1607  {
1608  stack.insert(StackEntry(insert_node, insert_tmin), i+1);
1609  }
1610  }
1611  }
1612  else
1613  {
1614  // Sort/insert and keep closest
1615  SYS_STATIC_ASSERT_MSG(BVH_N==2, "FIXME: Implement case of BVH_N>2!!!");
1616 
1617  }
1618 #endif
1619  }
1620  } while (!stack.isEmpty());
1621 
1622  if (hit_index >= 0)
1623  {
1624  hit_info.myItemIndex = hit_index;
1625  hit_info.myUVW = hit_uvw;
1626  // When farthest is true, max_dist_squared is actually a minimum distance squared.
1627  hit_info.myDistSquared = max_dist_squared;
1628  hit_info.myP = hit_position;
1629  }
1630  else
1631  {
1632  hit_info.myItemIndex = -1;
1633  hit_info.myUVW.assign(0,0,0);
1634  hit_info.myDistSquared = -1.0f;
1635  hit_info.myP = VectorType(typename VectorType::value_type(0));
1636  }
1637 }
1638 
1639 template<uint NAXES,typename SUBCLASS>
1640 void BVHBase<NAXES,SUBCLASS>::getIntersectingBoxes(const SingleBoxType &query_box, UT_Array<exint> &box_indices) const noexcept
1641 {
1643  UT::getIntersectingBoxes(myTree, myNodeBoxes.get(), query_box, box_indices, stack);
1644 }
1645 
1646 template<uint NAXES,typename SUBCLASS>
1647 template<bool normalize>
1649 {
1650  if (!SUBCLASS::theHasPrimitives || hit_info.myItemIndex < numPoints())
1651  {
1652  // NOTE: We don't need to negate if the radius is negative, because
1653  // that was automatically done in sendRay by multiplying by invradius.
1654  return VectorType(hit_info.myUVW);
1655  }
1656  return subclass()->template primGeometricNormal<normalize>(hit_info);
1657 }
1658 
1659 template<uint NAXES,typename SUBCLASS>
1660 void BVHBase<NAXES,SUBCLASS>::getDerivs(const CommonHitInfo &hit_info, VectorType &dP_du, VectorType &dP_dv) const noexcept
1661 {
1662  if (!SUBCLASS::theHasPrimitives || hit_info.myItemIndex < numPoints())
1663  {
1664  // NOTE: We don't need to negate nml if the radius is negative, because
1665  // that was automatically done in sendRay by multiplying by invradius.
1666  // TODO: However, do we need to negate dP_du or dP_dv?
1667  VectorType nml;
1668  nml[0] = hit_info.myUVW[0];
1669  nml[1] = hit_info.myUVW[1];
1670  if (NAXES == 3)
1671  {
1672  nml[2] = hit_info.myUVW[1];
1673  UT_Vector2 nmlxy(nml[0], nml[1]);
1674  float lengthxy = nmlxy.normalize();
1675 
1676  dP_dv[0] = -nml[2]*nmlxy[0];
1677  dP_dv[1] = -nml[2]*nmlxy[1];
1678  dP_dv[2] = lengthxy;
1679  dP_dv *= M_PI;
1680 
1681  dP_du[0] = -nml[1]*(2*M_PI);
1682  dP_du[1] = nml[0]*(2*M_PI);
1683  dP_du[2] = 0;
1684  }
1685  else
1686  {
1687  UT_ASSERT(NAXES==2);
1688  // FIXME: Verify that the sign is correct on this!
1689  dP_du[0] = -nml[1]*(2*M_PI);
1690  dP_du[1] = nml[0]*(2*M_PI);
1691  dP_dv[0] = 0;
1692  dP_dv[1] = 0;
1693  }
1694  return;
1695  }
1696  subclass()->primDerivs(hit_info, dP_du, dP_dv);
1697 }
1698 
1699 template<uint NAXES,typename SUBCLASS>
1701 {
1702  float u = SYSatan(uvw[1], uvw[0]) / (float)(2*M_PI);
1703  if (u < 0)
1704  u += 1;
1705  if (NAXES == 3)
1706  {
1707  float v = SYSacos(uvw[2]) / (float)M_PI;
1708  uvw[0] = u;
1709  uvw[1] = v;
1710  uvw[2] = 0;
1711  }
1712  else
1713  {
1714  UT_ASSERT(NAXES==2);
1715  uvw[0] = u;
1716  uvw[1] = 0;
1717  }
1718 }
1719 
1720 template<uint NAXES,typename SUBCLASS>
1721 template<GA_AttributeOwner owner,typename T,typename DEST_T>
1722 bool BVHBase<NAXES,SUBCLASS>::getAttribute(const CommonHitInfo &hit_info, const GA_ROHandleT<T> &attrib, const GEO_Detail &detail, DEST_T &value) const noexcept
1723 {
1724  UT_ASSERT(owner == attrib->getOwner());
1725 
1726  if (owner == GA_ATTRIB_DETAIL)
1727  {
1728  value = attrib.get(GA_DETAIL_OFFSET);
1729  return true;
1730  }
1731 
1732  exint index = hit_info.myItemIndex;
1733  if (!SUBCLASS::theHasPrimitives || index < numPoints())
1734  {
1735  if (owner != GA_ATTRIB_POINT)
1736  return false;
1737 
1738  GA_Offset ptoff = myPoints(index);
1739  value = attrib.get(ptoff);
1740  return true;
1741  }
1742  return subclass()->template primAttribute<owner,T,DEST_T>(hit_info, attrib, detail, value);
1743 }
1744 
1745 } // GEO namespace
1746 
1747 #undef GEO_BVH_INTERLEAVED
#define SYSmax(a, b)
Definition: SYS_Math.h:1538
T & last()
Definition: UT_Array.h:796
SYS_FORCE_INLINE void setNestingArrayInto(HitInfo &hit_info) noexcept
Definition: GEO_BVHImpl.h:107
SYS_FORCE_INLINE void insertHit(const UT_Vector3 &hit_uvw, const float t, const uint index, float &limit_t) noexcept
Definition: GEO_BVHImpl.h:153
SYS_FORCE_INLINE UT_Vector3 & lastUVW() noexcept
Definition: GEO_BVHImpl.h:125
#define SYS_STATIC_ASSERT(expr)
SYS_FORCE_INLINE void insertHit(const UT_Vector3 &hit_uvw, const float t, const uint index, float &limit_t) noexcept
Definition: GEO_BVHImpl.h:283
void sendRay(const VectorType &origin, const VectorType &direction, HitInfoType &hit_info, float tmin=0, float tmax=std::numeric_limits< float >::max()) const noexcept
Definition: GEO_BVHImpl.h:346
SYS_FORCE_INLINE UT_Array< exint > * nestingArray() noexcept
Definition: GEO_BVHImpl.h:171
SYS_FORCE_INLINE UT_Array< HitInfo > * getHitArray() noexcept
Definition: GEO_BVHImpl.h:123
SIM_API const UT_StringHolder angle
#define SYS_STATIC_ASSERT_MSG(expr, msg)
void getDerivs(const CommonHitInfo &hit_info, VectorType &dP_du, VectorType &dP_dv) const noexcept
Fills in the values of dP/du and dP/dv for the hit surface.
Definition: GEO_BVHImpl.h:1660
Definition: UT_BVH.h:37
void findClosest(VectorType origin, MinInfo &min_info, float max_dist_squared=std::numeric_limits< float >::max()) const noexcept
Definition: GEO_BVHImpl.h:1193
SYS_FORCE_INLINE void removeLast()
Definition: UT_Array.h:379
VectorType getGeometricNormal(const CommonHitInfo &hit_info) const noexcept
const GLdouble * v
Definition: glcorearb.h:837
SYS_FORCE_INLINE exint nestingArrayBase() noexcept
Definition: GEO_BVHImpl.h:115
#define M_PI
Definition: fmath.h:90
IMF_EXPORT IMATH_NAMESPACE::V3f direction(const IMATH_NAMESPACE::Box2i &dataWindow, const IMATH_NAMESPACE::V2f &pixelPosition)
SYS_FORCE_INLINE UT_Array< HitInfoAndNormal > * getHitArray() noexcept
Definition: GEO_BVHImpl.h:185
SYS_FORCE_INLINE void noHit() noexcept
Definition: GEO_BVHImpl.h:147
SYS_FORCE_INLINE void setNestingArrayInto(HitInfoAndNormal &hit_info) noexcept
Definition: GEO_BVHImpl.h:313
GLsizei const GLfloat * value
Definition: glcorearb.h:824
bool SYSisFinite(fpreal64 f)
Definition: SYS_Math.h:198
void setSizeNoInit(exint newsize)
Definition: UT_Array.h:695
UT_Array< exint > *const myNestingTempArray
Definition: GEO_BVHImpl.h:265
SYS_FORCE_INLINE VectorType getNormal(const HitInfoAndNormal &hit_info) const noexcept
Definition: GEO_BVHImpl.h:318
UT_Vector3T< float > UT_Vector3
int64 exint
Definition: SYS_Types.h:125
SYS_FORCE_INLINE exint nestingArrayBase() const noexcept
Definition: GEO_BVHImpl.h:124
SYS_FORCE_INLINE void setNormal(const VectorType &nml) noexcept
Definition: GEO_BVHImpl.h:121
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1222
void reverse(I begin, I end)
Definition: pugixml.cpp:7190
#define SYSabs(a)
Definition: SYS_Math.h:1540
GLuint GLsizei GLsizei * length
Definition: glcorearb.h:795
SYS_FORCE_INLINE void setNormal(const VectorType &nml) noexcept
Definition: GEO_BVHImpl.h:320
void findClosestInCone(VectorType origin, VectorType direction, const float angle, const exint max_points, const float max_dist_squared, UT::BVHOrderedStack &output_queue) const noexcept
Definition: GEO_BVHImpl.h:1101
#define UT_ASSERT_MSG_P(ZZ,...)
Definition: UT_Assert.h:158
void findClosestToSegment(VectorType p0, VectorType p1, const exint max_points, const float max_dist_squared, UT::BVHOrderedStack &output_queue) const noexcept
Finds the closest points to the line segment with endpoints p0 and p1.
Definition: GEO_BVHImpl.h:1082
SYS_FORCE_INLINE const VectorType & getNormal(const HitInfoAndNormal &hit_info) const noexcept
Definition: GEO_BVHImpl.h:175
SYS_FORCE_INLINE void setNormal(const VectorType &nml) noexcept
Definition: GEO_BVHImpl.h:177
SYS_FORCE_INLINE UT_Array< exint > * nestingArray() noexcept
Definition: GEO_BVHImpl.h:314
exint size() const
Definition: UT_Array.h:646
uint64 value_type
Definition: GA_PrimCompat.h:29
SYS_FORCE_INLINE void setNormal(HitInfoAndNormal &hit_info, const VectorType &nml) const noexcept
Definition: GEO_BVHImpl.h:181
UT_Array< HitInfoAndNormal > & myHitInfo
Definition: GEO_BVHImpl.h:339
GEO::BVHBase< NAXES, SUBCLASS > BVHBase
Definition: GU_BVH.h:31
SYS_FORCE_INLINE T minDistance2(const UT_FixedVector< T, NAXES > &p) const noexcept
Definition: UT_BVH.h:312
#define UT_ASSERT_MSG(ZZ,...)
Definition: UT_Assert.h:159
GA_Size GA_Offset
Definition: GA_Types.h:641
SYS_FORCE_INLINE AllHitsAndNormalsFunctor(UT_Array< HitInfoAndNormal > &hit_info, UT_Array< exint > *nesting_temp_array) noexcept
Definition: GEO_BVHImpl.h:273
SYS_FORCE_INLINE void setNormal(HitInfo &hit_info, const VectorType &nml) const noexcept
Definition: GEO_BVHImpl.h:122
GLdouble n
Definition: glcorearb.h:2008
bool getAttribute(const CommonHitInfo &hit_info, const GA_ROHandleT< T > &attrib, const GEO_Detail &detail, DEST_T &value) const noexcept
Definition: GEO_BVHImpl.h:1722
void findClosestToLine(VectorType origin, VectorType direction, const exint max_points, const float max_dist_squared, UT::BVHOrderedStack &output_queue) const noexcept
Finds the closest points to the infinite line containing origin with direction direction.
Definition: GEO_BVHImpl.h:1063
SYS_FORCE_INLINE UT_Array< HitInfo > * getHitArray() noexcept
Definition: GEO_BVHImpl.h:253
SYS_FORCE_INLINE UT_Array< exint > * nestingArray() noexcept
Definition: GEO_BVHImpl.h:111
SYS_FORCE_INLINE UT_Array< HitInfoAndNormal > * getHitArray() noexcept
Definition: GEO_BVHImpl.h:328
SYS_FORCE_INLINE UT_Vector3 & lastUVW() noexcept
Definition: GEO_BVHImpl.h:187
SYS_FORCE_INLINE VectorType getNormal(const HitInfo &hit_info) const noexcept
Definition: GEO_BVHImpl.h:119
void getIntersectingBoxes(const SingleBoxType &query_box, UT_Array< exint > &box_indices) const noexcept
Definition: GEO_BVHImpl.h:1640
SYS_FORCE_INLINE T maxDistance2(const UT_FixedVector< T, NAXES > &p) const noexcept
Definition: UT_BVH.h:325
Definition: VM_SIMD.h:48
fpreal64 dot(const CE_VectorT< T > &a, const CE_VectorT< T > &b)
Definition: CE_Vector.h:130
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
SYS_FORCE_INLINE void noHit() noexcept
Definition: GEO_BVHImpl.h:210
Definition: VM_SIMD.h:188
void clear() noexcept
Definition: GEO_BVHImpl.h:34
typename SYS_SelectType< UT_FixedVector< uint, 2 >, UT_FixedVector< uint, 3 >, NAXES==3 >::type UintVectorType
Definition: GEO_BVH.h:40
static void pointUVWToPolar(VectorType &uvw) noexcept
Definition: GEO_BVHImpl.h:1700
SYS_FORCE_INLINE void insertHit(const UT_Vector3 &hit_uvw, const float t, const uint index, float &limit_t) noexcept
Definition: GEO_BVHImpl.h:214
void sendRayAllRad(const VectorType &origin, const VectorType &direction, UT_Array< HitInfoType > &hit_info, float default_radius, UT_Array< exint > *nesting_temp_array=nullptr, float duplicate_tolerance=0, float tmin=0, float tmax=std::numeric_limits< float >::max()) const noexcept
Definition: GEO_BVHImpl.h:426
SYS_FORCE_INLINE exint nestingArrayBase() const noexcept
Definition: GEO_BVHImpl.h:329
IMATH_HOSTDEVICE constexpr int sign(T a) IMATH_NOEXCEPT
Definition: ImathFun.h:33
SYS_FORCE_INLINE exint nestingArrayBase() const noexcept
Definition: GEO_BVHImpl.h:186
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1222
T vals[NAXES][2]
Definition: UT_BVH.h:38
exint append()
Definition: UT_Array.h:142
GLdouble t
Definition: glad.h:2397
SYS_FORCE_INLINE void setNestingArrayInto(HitInfoAndNormal &hit_info) noexcept
Definition: GEO_BVHImpl.h:167
SYS_FORCE_INLINE VectorType getNormal(const HitInfo &hit_info) const noexcept
Definition: GEO_BVHImpl.h:249
void sendRayGeneric(VectorType origin, VectorType direction, FUNCTOR &hit_info, float tmin=0, float tmax=std::numeric_limits< float >::max()) const noexcept
Definition: GEO_BVHImpl.h:481
SYS_FORCE_INLINE void setNormal(HitInfoAndNormal &hit_info, const VectorType &nml) const noexcept
Definition: GEO_BVHImpl.h:324
void assign(T xx=0.0f, T yy=0.0f, T zz=0.0f)
Set the values of the vector components.
Definition: UT_Vector3.h:694
SYS_FORCE_INLINE void intersectTol(T &box_tmin, T &box_tmax, const UT_FixedVector< uint, NAXES > &signs, const UT_FixedVector< T, NAXES > &origin, const UT_FixedVector< T, NAXES > &inverse_direction, T tolerance) const noexcept
Intersect the box expanded by the specified tolerance in all axes.
Definition: UT_BVH.h:283
SYS_FORCE_INLINE void setNormal(HitInfo &hit_info, const VectorType &nml) const noexcept
Definition: GEO_BVHImpl.h:252
T * data()
Definition: UT_Array.h:822
typename SYS_SelectType< UT_Vector2, UT_Vector3, NAXES==3 >::type VectorType
Definition: GEO_BVH.h:39
v4si vector
Definition: VM_SIMD.h:185
GLuint index
Definition: glcorearb.h:786
ImageBuf OIIO_API max(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
SYS_FORCE_INLINE UT_Array< exint > * nestingArray() noexcept
Definition: GEO_BVHImpl.h:245
if(num_boxed_items<=0)
Definition: UT_RTreeImpl.h:697
SYS_FORCE_INLINE void intersect(T &box_tmin, T &box_tmax, const UT_FixedVector< uint, NAXES > &signs, const UT_FixedVector< T, NAXES > &origin, const UT_FixedVector< T, NAXES > &inverse_direction) const noexcept
Definition: UT_BVH.h:266
void findMaximalPointsCommon(const QUERY_POINT &query_point, UT::BVHOrderedStack &stack, UT::BVHOrderedStack &output_queue, exint max_points, float max_dist_squared) const noexcept
Definition: GEO_BVHImpl.h:990
SYS_FORCE_INLINE AllHitsFunctor(UT_Array< HitInfo > &hit_info, UT_Array< exint > *nesting_temp_array) noexcept
Definition: GEO_BVHImpl.h:204
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:156
Definition: core.h:1131
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
#define V4SF(A)
Definition: VM_BasicFunc.h:68
SYS_FORCE_INLINE SingleHitFunctor(HitInfo &hit_info) noexcept
Definition: GEO_BVHImpl.h:82
#define const
Definition: zconf.h:214
#define GA_DETAIL_OFFSET
Definition: GA_Types.h:682
SIM_API const UT_StringHolder distance
void sendRayAll(const VectorType &origin, const VectorType &direction, UT_Array< HitInfoType > &hit_info, UT_Array< exint > *nesting_temp_array=nullptr, float duplicate_tolerance=0, float tmin=0, float tmax=std::numeric_limits< float >::max()) const noexcept
Definition: GEO_BVHImpl.h:380
SYS_FORCE_INLINE SingleHitAndNormalFunctor(HitInfoAndNormal &hit_info) noexcept
Definition: GEO_BVHImpl.h:142
#define SYSmin(a, b)
Definition: SYS_Math.h:1539
SYS_FORCE_INLINE UT_Vector3 & lastUVW() noexcept
Definition: GEO_BVHImpl.h:255
type
Definition: core.h:1059
SYS_FORCE_INLINE UT_StorageMathFloat_t< T > normalize() noexcept
Definition: UT_Vector2.h:309
unsigned int uint
Definition: SYS_Types.h:45
void sort(I begin, I end, const Pred &pred)
Definition: pugixml.cpp:7334
SYS_FORCE_INLINE void insertHit(const UT_Vector3 &hit_uvw, const float t, const uint index, float &limit_t) noexcept
Definition: GEO_BVHImpl.h:93
void sendRayRad(const VectorType &origin, const VectorType &direction, HitInfoType &hit_info, float default_radius, float tmin=0, float tmax=std::numeric_limits< float >::max()) const noexcept
Definition: GEO_BVHImpl.h:359
SYS_FORCE_INLINE exint nestingArrayBase() const noexcept
Definition: GEO_BVHImpl.h:254
UT_Array< exint > * myNestedItemIndices
This can be used for packed primitive hits.
Definition: GEO_BVH.h:68
SYS_FORCE_INLINE void noHit() noexcept
Definition: GEO_BVHImpl.h:279
v4sf vector
Definition: VM_SIMD.h:348
exint insert(exint index)
Definition: UT_ArrayImpl.h:721
SYS_FORCE_INLINE void noHit() noexcept
Definition: GEO_BVHImpl.h:87
UT_Array< HitInfo > & myHitInfo
Definition: GEO_BVHImpl.h:264
SYS_FORCE_INLINE void setNormal(const VectorType &nml) noexcept
Definition: GEO_BVHImpl.h:251
SYS_FORCE_INLINE UT_Vector3 & lastUVW() noexcept
Definition: GEO_BVHImpl.h:330
SYS_FORCE_INLINE void setNestingArrayInto(HitInfo &hit_info) noexcept
Definition: GEO_BVHImpl.h:244
UT_Array< exint > *const myNestingTempArray
Definition: GEO_BVHImpl.h:340
bool isEmpty() const
Returns true iff there are no occupied elements in the array.
Definition: UT_Array.h:650