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.stdsort([](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.stdsort([](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  UT_ASSERT_MSG_P(next_node != NodeType::EMPTY, "How did a ray hit an empty box?");
1278 
1279  next_node = NodeType::getInternalNum(next_node);
1280  const BoxType &box = myNodeBoxes[next_node];
1281  v4uf dist2 = (!farthest) ? box.minDistance2(vorigin) : box.maxDistance2(vorigin);
1282  v4uu hit_mask = (!farthest) ? (dist2 <= max_dist_squared) : (dist2 >= max_dist_squared);
1283  const uint hit_bits = _mm_movemask_ps(V4SF(hit_mask.vector));
1284  if (hit_bits == 0)
1285  break;
1286  const NodeType &node = nodes[next_node];
1287  if (!(hit_bits & (hit_bits-1)))
1288  {
1289  // Only 1 bit set
1290  uint local_index = SYSfirstBitSet(hit_bits);
1291 #if 1
1292  next_node = node.child[local_index];
1293 #else
1294  float local_d2 = d2s[local_index];
1295  uint child_index = node.child[local_index];
1296  if (!stack_size || ((!farthest) ? (stack_last->myDistSquared >= local_d2) : (stack_last->myDistSquared <= local_d2)))
1297  next_node = child_index;
1298  else
1299  {
1300  next_node = stack_last->myNode;
1301  stack_last->myNode = child_index;
1302  stack_last->myDistSquared = local_d2;
1303  }
1304 #endif
1305  continue;
1306  }
1307 
1308  exint stack_size = stack.size();
1309  StackEntry *stack_last = stack.data()+stack_size-1;
1310 
1311  // If we're going to be adding to the stack, we might as
1312  // well prune anything from the end of the stack that's
1313  // too far, to possibly reduce reallocations.
1314  // That said, this probably won't happen often, since
1315  // it requires hitting 2 child boxes in the current node
1316  // when the next node in the stack must be farther than an
1317  // existing hit.
1318  // When farthest is true, max_dist_squared is actually a minimum distance squared.
1319  while (stack_size != 0 && ((!farthest) ? (stack_last->myDistSquared > max_dist_squared) : (stack_last->myDistSquared < max_dist_squared)))
1320  {
1321  --stack_size;
1322  --stack_last;
1323  stack.removeLast();
1324  }
1325  static constexpr uint two_bit_indices[16][2] = {
1326  {4, 4}, {4, 4}, {4, 4}, {0, 1},
1327  {4, 4}, {0, 2}, {1, 2}, {0, 1},
1328  {4, 4}, {0, 3}, {1, 3}, {0, 1},
1329  {2, 3}, {0, 2}, {1, 2}, {0, 1}
1330  };
1331  static constexpr uint third_bit_index[16] = {
1332  4, 4, 4, 4,
1333  4, 4, 4, 2,
1334  4, 4, 4, 3,
1335  4, 3, 3, 2
1336  };
1337  // When farthest is true, these are tmax's.
1338  union { v4sf d2v; float d2s[4]; };
1339  d2v = dist2.vector;
1340  uint local_index0 = two_bit_indices[hit_bits][0];
1341  uint local_index1 = two_bit_indices[hit_bits][1];
1342  if (third_bit_index[hit_bits] == 4)
1343  {
1344  // Only 2 bits set
1345  float d20 = d2s[local_index0];
1346  float d21 = d2s[local_index1];
1347  uint child0 = node.child[local_index0];
1348  uint child1 = node.child[local_index1];
1349  if ((!farthest) ? (d20 > d21) : (d20 < d21))
1350  {
1351  uint childtmp = child0;
1352  child0 = child1;
1353  child1 = childtmp;
1354  float tmp = d20;
1355  d20 = d21;
1356  d21 = tmp;
1357  }
1358 
1359  if (!stack_size || ((!farthest) ? (stack_last->myDistSquared >= d20) : (stack_last->myDistSquared <= d20)))
1360  {
1361  next_node = child0;
1362 
1363  // Inserting d21
1364  // Check end of stack first, since it's most likely that the box will go near the end.
1365  if (!stack_size || ((!farthest) ? (stack_last->myDistSquared >= d21) : (stack_last->myDistSquared <= d21)))
1366  {
1367  stack.append(StackEntry(child1, d21));
1368  }
1369  else
1370  {
1371  // Insert in sorted order, but go back at most a constant
1372  // number of entries, to avoid n^2 behaviour.
1373  exint i;
1374  exint limiti = SYSmax(0, stack_size-64);
1375  for (i = stack_size-2; i >= limiti; --i)
1376  {
1377  if ((!farthest) ? (stack[i].myDistSquared >= d21) : (stack[i].myDistSquared <= d21))
1378  {
1379  stack.insert(StackEntry(child1, d21), i+1);
1380  break;
1381  }
1382  }
1383  if (i < limiti)
1384  {
1385  stack.insert(StackEntry(child1, d21), i+1);
1386  }
1387  }
1388  }
1389  else
1390  {
1391  next_node = stack_last->myNode;
1392  stack_last->myNode = child1;
1393  stack_last->myDistSquared = d21;
1394  stack.append(StackEntry(child0, d20));
1395  }
1396  continue;
1397  }
1398 
1399  // 3-4 bits set
1400  uint nhit = (hit_bits == 0xF) ? 4 : 3;
1401  uint local_index2 = third_bit_index[hit_bits];
1402  uint children[BVH_N] = {
1403  node.child[local_index0],
1404  node.child[local_index1],
1405  node.child[local_index2],
1406  node.child[3]
1407  };
1408  d2s[0] = d2s[local_index0];
1409  d2s[1] = d2s[local_index1];
1410  d2s[2] = d2s[local_index2];
1411  //d2s[3] = d2s[3];
1412 
1413  float new_d2;
1414  if (!stack_size || ((!farthest) ? (stack_last->myDistSquared >= d2s[0]) : (stack_last->myDistSquared <= d2s[0])))
1415  {
1416  new_d2 = d2s[0];
1417  next_node = children[0];
1418  }
1419  else
1420  {
1421  new_d2 = stack_last->myDistSquared;
1422  next_node = stack_last->myNode;
1423  stack_last->myDistSquared = d2s[0];
1424  stack_last->myNode = children[0];
1425  }
1426  for (uint hit = 1; hit < nhit; ++hit)
1427  {
1428  float d2 = d2s[hit];
1429  uint child = children[hit];
1430  if ((!farthest) ? (d2 < new_d2) : (d2 > new_d2))
1431  {
1432  float tmpd2 = new_d2;
1433  uint tmpchild = next_node;
1434  new_d2 = d2;
1435  next_node = child;
1436  d2 = tmpd2;
1437  child = tmpchild;
1438  }
1439 
1440  // Check end of stack first, since it's most likely that the box will go near the end.
1441  if (!stack_size || ((!farthest) ? (stack_last->myDistSquared >= d2) : (stack_last->myDistSquared <= d2)))
1442  {
1443  stack.append(StackEntry(child, d2));
1444  }
1445  else
1446  {
1447  // Insert in sorted order, but go back at most a constant
1448  // number of entries, to avoid n^2 behaviour.
1449  exint i;
1450  exint limiti = SYSmax(0, stack_size-64);
1451  for (i = stack_size-2; i >= limiti; --i)
1452  {
1453  if ((!farthest) ? (stack[i].myDistSquared >= d2) : (stack[i].myDistSquared <= d2))
1454  {
1455  stack.insert(StackEntry(child, d2), i+1);
1456  break;
1457  }
1458  }
1459  if (i < limiti)
1460  {
1461  stack.insert(StackEntry(child, d2), i+1);
1462  }
1463  }
1464  stack_last = stack.data()+stack_size;
1465  ++stack_size;
1466  }
1467  continue;
1468  }
1469  uint index = next_node;//myIndices[next_node];
1470 #else
1471  const NodeType &node = nodes[next_node];
1472  uint children[BVH_N];
1473  float d2s[BVH_N];
1474  uint nnodehits = 0;
1475  for (uint i = 0; i < BVH_N; ++i)
1476  {
1477  const uint itemi = node.child[i];
1478  if (NodeType::isInternal(itemi))
1479  {
1480  if (itemi == NodeType::EMPTY)
1481  continue;
1482 
1483  // Internal node: intersect against box
1484  const uint childi = NodeType::getInternalNum(itemi);
1485  const BoxType &box = myNodeBoxes[childi];
1486  float dist2 = (!farthest) ? box.minDistance2(origin) : box.maxDistance2(origin);
1487  if ((!farthest) ? (dist2 > min_dist_squared) : (dist2 < min_dist_squared))
1488  continue;
1489 
1490  children[nnodehits] = childi;
1491  d2s[nnodehits] = dist2;
1492  ++nnodehits;
1493  }
1494  else
1495  {
1496  // Leaf item: intersect against item
1497  uint index = itemi;//myIndices[itemi];
1498 #endif
1499  if (!SUBCLASS::theHasPrimitives || index < num_points)
1500  {
1501  // Points as spheres
1502  // The point tree subclass reorders myPositions and myRadii
1503  // to match the indices in the tree, so we don't need to remap them.
1504  exint ptarrayindex = (SUBCLASS::theReordersPositions) ? exint(index) : exint(myPoints(index));
1505  const bool use_pos_array = !myPositions.isEmpty();
1506  const VectorType pos = use_pos_array ? myPositions[ptarrayindex] : myPosAttrib.get(GA_Offset(ptarrayindex));
1507  //if (myRadii.isValid())
1508  float radius;
1509  if (myRadii.isEmpty())
1510  radius = myRadAttrib.isValid() ? myRadAttrib.get(GA_Offset(ptarrayindex)) : 0.0f;
1511  else
1512  radius = ((myRadii.size() == 1) ? myRadii[0] : myRadii[ptarrayindex]);
1513  VectorType displacement = origin-pos;
1514  float d2 = displacement.length2();
1515  if (radius == 0)
1516  {
1517  // Zero radius
1518  // When farthest is true, max_dist_squared is actually a minimum distance squared.
1519  if ((!farthest) ? (d2 < max_dist_squared) : (d2 > max_dist_squared))
1520  {
1521  max_dist_squared = d2;
1522  hit_index = index;
1523  hit_uvw.assign(0,0,0);
1524  hit_position = pos;
1525  }
1526  }
1527  else
1528  {
1529  float distance = SYSsqrt(d2) - SYSabs(radius);
1530  d2 = distance*distance;
1531  if ((!farthest) ? (d2 < max_dist_squared) : (d2 > max_dist_squared))
1532  {
1533  max_dist_squared = d2;
1534  hit_index = index;
1535  VectorType normal = displacement;
1536  normal.normalize();
1537  // Real normal is opposite the displacement if radius is negative.
1538  VectorType real_normal = (((radius > 0) != farthest) ? normal : -normal);
1539  hit_uvw[0] = real_normal[0];
1540  hit_uvw[1] = real_normal[1];
1541  hit_uvw[2] = (NAXES==3) ? real_normal[2] : 0;
1542 
1543  // hit_position needs to use normal in the direction of displacement.
1544  hit_position = pos;
1545  if (!farthest)
1546  hit_position -= radius*normal;
1547  else
1548  hit_position += radius*normal;
1549  }
1550  }
1551  }
1552  else
1553  {
1554  subclass()->template closestPrim<farthest>(
1555  index, origin, max_dist_squared,
1556  hit_index, hit_uvw, hit_position,
1557  vorigin, nesting_array, nesting_array_base);
1558  }
1559 #if GEO_BVH_INTERLEAVED
1560  break;
1561 #else
1562  }
1563  }
1564  if (nnodehits == 0)
1565  break;
1566  exint stack_size = stack.size();
1567  StackEntry *stack_last = stack.data()+stack_size-1;
1568  if (nnodehits == 1)
1569  {
1570  uint child_index = children[0];
1571  if (!stack_size || stack_last->myTMin >= tmins[0])
1572  next_node = child_index;
1573  else
1574  {
1575  next_node = stack_last->myNode;
1576  stack_last->myNode = child_index;
1577  stack_last->myTMin = tmins[0];
1578  }
1579  }
1580  else if (BVH_N == 2 || nnodehits == 2)
1581  {
1582  const uint local_index = (tmins[0] >= tmins[1]);
1583  next_node = children[local_index];
1584  const uint insert_node = children[!local_index];
1585  const float insert_tmin = tmins[!local_index];
1586  // Check end of stack first, since it's most likely that the box will go near the end.
1587  if (!stack_size || stack_last->myTMin <= insert_tmin)
1588  {
1589  stack.append(StackEntry(insert_node, insert_tmin));
1590  }
1591  else
1592  {
1593  // Insert in sorted order, but go back at most a constant
1594  // number of entries, to avoid n^2 behaviour.
1595  exint i;
1596  exint limiti = SYSmax(0, stack_size-64);
1597  for (i = stack_size-2; i >= limiti; --i)
1598  {
1599  if (stack[i].myTMin <= insert_tmin)
1600  {
1601  stack.insert(StackEntry(insert_node, insert_tmin), i+1);
1602  break;
1603  }
1604  }
1605  if (i < limiti)
1606  {
1607  stack.insert(StackEntry(insert_node, insert_tmin), i+1);
1608  }
1609  }
1610  }
1611  else
1612  {
1613  // Sort/insert and keep closest
1614  SYS_STATIC_ASSERT_MSG(BVH_N==2, "FIXME: Implement case of BVH_N>2!!!");
1615 
1616  }
1617 #endif
1618  }
1619  } while (!stack.isEmpty());
1620 
1621  if (hit_index >= 0)
1622  {
1623  hit_info.myItemIndex = hit_index;
1624  hit_info.myUVW = hit_uvw;
1625  // When farthest is true, max_dist_squared is actually a minimum distance squared.
1626  hit_info.myDistSquared = max_dist_squared;
1627  hit_info.myP = hit_position;
1628  }
1629  else
1630  {
1631  hit_info.myItemIndex = -1;
1632  hit_info.myUVW.assign(0,0,0);
1633  hit_info.myDistSquared = -1.0f;
1634  hit_info.myP = VectorType(typename VectorType::value_type(0));
1635  }
1636 }
1637 
1638 template<uint NAXES,typename SUBCLASS>
1639 void BVHBase<NAXES,SUBCLASS>::getIntersectingBoxes(const SingleBoxType &query_box, UT_Array<exint> &box_indices) const noexcept
1640 {
1642  UT::getIntersectingBoxes(myTree, myNodeBoxes.get(), query_box, box_indices, stack);
1643 }
1644 
1645 template<uint NAXES,typename SUBCLASS>
1646 template<bool normalize>
1648 {
1649  if (!SUBCLASS::theHasPrimitives || hit_info.myItemIndex < numPoints())
1650  {
1651  // NOTE: We don't need to negate if the radius is negative, because
1652  // that was automatically done in sendRay by multiplying by invradius.
1653  return VectorType(hit_info.myUVW);
1654  }
1655  return subclass()->template primGeometricNormal<normalize>(hit_info);
1656 }
1657 
1658 template<uint NAXES,typename SUBCLASS>
1659 void BVHBase<NAXES,SUBCLASS>::getDerivs(const CommonHitInfo &hit_info, VectorType &dP_du, VectorType &dP_dv) const noexcept
1660 {
1661  if (!SUBCLASS::theHasPrimitives || hit_info.myItemIndex < numPoints())
1662  {
1663  // NOTE: We don't need to negate nml if the radius is negative, because
1664  // that was automatically done in sendRay by multiplying by invradius.
1665  // TODO: However, do we need to negate dP_du or dP_dv?
1666  VectorType nml;
1667  nml[0] = hit_info.myUVW[0];
1668  nml[1] = hit_info.myUVW[1];
1669  if (NAXES == 3)
1670  {
1671  nml[2] = hit_info.myUVW[1];
1672  UT_Vector2 nmlxy(nml[0], nml[1]);
1673  float lengthxy = nmlxy.normalize();
1674 
1675  dP_dv[0] = -nml[2]*nmlxy[0];
1676  dP_dv[1] = -nml[2]*nmlxy[1];
1677  dP_dv[2] = lengthxy;
1678  dP_dv *= M_PI;
1679 
1680  dP_du[0] = -nml[1]*(2*M_PI);
1681  dP_du[1] = nml[0]*(2*M_PI);
1682  dP_du[2] = 0;
1683  }
1684  else
1685  {
1686  UT_ASSERT(NAXES==2);
1687  // FIXME: Verify that the sign is correct on this!
1688  dP_du[0] = -nml[1]*(2*M_PI);
1689  dP_du[1] = nml[0]*(2*M_PI);
1690  dP_dv[0] = 0;
1691  dP_dv[1] = 0;
1692  }
1693  return;
1694  }
1695  subclass()->primDerivs(hit_info, dP_du, dP_dv);
1696 }
1697 
1698 template<uint NAXES,typename SUBCLASS>
1700 {
1701  float u = SYSatan(uvw[1], uvw[0]) / (float)(2*M_PI);
1702  if (u < 0)
1703  u += 1;
1704  if (NAXES == 3)
1705  {
1706  float v = SYSacos(uvw[2]) / (float)M_PI;
1707  uvw[0] = u;
1708  uvw[1] = v;
1709  uvw[2] = 0;
1710  }
1711  else
1712  {
1713  UT_ASSERT(NAXES==2);
1714  uvw[0] = u;
1715  uvw[1] = 0;
1716  }
1717 }
1718 
1719 template<uint NAXES,typename SUBCLASS>
1720 template<GA_AttributeOwner owner,typename T,typename DEST_T>
1721 bool BVHBase<NAXES,SUBCLASS>::getAttribute(const CommonHitInfo &hit_info, const GA_ROHandleT<T> &attrib, const GEO_Detail &detail, DEST_T &value) const noexcept
1722 {
1723  UT_ASSERT(owner == attrib->getOwner());
1724 
1725  if (owner == GA_ATTRIB_DETAIL)
1726  {
1727  value = attrib.get(GA_DETAIL_OFFSET);
1728  return true;
1729  }
1730 
1731  exint index = hit_info.myItemIndex;
1732  if (!SUBCLASS::theHasPrimitives || index < numPoints())
1733  {
1734  if (owner != GA_ATTRIB_POINT)
1735  return false;
1736 
1737  GA_Offset ptoff = myPoints(index);
1738  value = attrib.get(ptoff);
1739  return true;
1740  }
1741  return subclass()->template primAttribute<owner,T,DEST_T>(hit_info, attrib, detail, value);
1742 }
1743 
1744 } // GEO namespace
1745 
1746 #undef GEO_BVH_INTERLEAVED
#define SYSmax(a, b)
Definition: SYS_Math.h:1447
T & last()
Definition: UT_Array.h:599
SYS_FORCE_INLINE void setNestingArrayInto(HitInfo &hit_info) noexcept
Definition: GEO_BVHImpl.h:107
vint4 max(const vint4 &a, const vint4 &b)
Definition: simd.h:4703
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
#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:1659
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:223
VectorType getGeometricNormal(const CommonHitInfo &hit_info) const noexcept
GLuint index
Definition: glew.h:1814
SYS_FORCE_INLINE exint nestingArrayBase() noexcept
Definition: GEO_BVHImpl.h:115
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
void setSizeNoInit(exint newsize)
Definition: UT_Array.h:498
UT_Array< exint > *const myNestingTempArray
Definition: GEO_BVHImpl.h:265
GLboolean GLboolean GLboolean GLboolean a
Definition: glew.h:9477
SYS_FORCE_INLINE VectorType getNormal(const HitInfoAndNormal &hit_info) const noexcept
Definition: GEO_BVHImpl.h:318
SYS_FORCE_INLINE void intersectTol(T &box_tmin, T &box_tmax, const UT_FixedVector< uint, NAXES, INSTANTIATED0 > &signs, const UT_FixedVector< T, NAXES, INSTANTIATED1 > &origin, const UT_FixedVector< T, NAXES, INSTANTIATED1 > &inverse_direction, T tolerance) const noexcept
Intersect the box expanded by the specified tolerance in all axes.
Definition: UT_BVH.h:257
UT_Vector3T< float > UT_Vector3
SYS_FORCE_INLINE T minDistance2(const UT_FixedVector< T, NAXES, INSTANTIATED > &p) const noexcept
Definition: UT_BVH.h:286
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
void reverse(I begin, I end)
Definition: pugixml.cpp:7190
#define SYSabs(a)
Definition: SYS_Math.h:1449
SYS_FORCE_INLINE void setNormal(const VectorType &nml) noexcept
Definition: GEO_BVHImpl.h:320
const GLdouble * v
Definition: glew.h:1391
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:137
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
GLdouble angle
Definition: glew.h:9135
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:451
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
#define M_PI
Definition: ImathPlatform.h:51
UT_Array< HitInfoAndNormal > & myHitInfo
Definition: GEO_BVHImpl.h:339
GEO::BVHBase< NAXES, SUBCLASS > BVHBase
Definition: GU_BVH.h:31
SYS_FORCE_INLINE void intersect(T &box_tmin, T &box_tmax, const UT_FixedVector< uint, NAXES, INSTANTIATED0 > &signs, const UT_FixedVector< T, NAXES, INSTANTIATED1 > &origin, const UT_FixedVector< T, NAXES, INSTANTIATED1 > &inverse_direction) const noexcept
Definition: UT_BVH.h:239
#define UT_ASSERT_MSG(ZZ,...)
Definition: UT_Assert.h:138
GA_Size GA_Offset
Definition: GA_Types.h:637
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
bool getAttribute(const CommonHitInfo &hit_info, const GA_ROHandleT< T > &attrib, const GEO_Detail &detail, DEST_T &value) const noexcept
Definition: GEO_BVHImpl.h:1721
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:1639
int64 exint
Definition: SYS_Types.h:120
Definition: VM_SIMD.h:48
fpreal64 dot(const CE_VectorT< T > &a, const CE_VectorT< T > &b)
Definition: CE_Vector.h:218
#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
GLsizei n
Definition: glew.h:4040
const GLfloat * c
Definition: glew.h:16296
GLuint GLsizei GLsizei * length
Definition: glew.h:1825
GLsizei GLsizei GLfloat distance
Definition: glew.h:13640
#define V4SF(A)
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:1699
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
int sign(T a)
Definition: ImathFun.h:63
SYS_FORCE_INLINE exint nestingArrayBase() const noexcept
Definition: GEO_BVHImpl.h:186
T vals[NAXES][2]
Definition: UT_BVH.h:38
GLuint GLuint GLsizei GLenum type
Definition: glew.h:1253
unsigned int uint
Definition: SYS_Types.h:44
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
GLdouble GLdouble GLdouble b
Definition: glew.h:9122
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:537
GLfloat GLfloat p
Definition: glew.h:16321
SYS_FORCE_INLINE void setNormal(HitInfo &hit_info, const VectorType &nml) const noexcept
Definition: GEO_BVHImpl.h:252
T * data()
Definition: UT_Array.h:625
typename SYS_SelectType< UT_Vector2, UT_Vector3, NAXES==3 >::type VectorType
Definition: GEO_BVH.h:39
v4si vector
Definition: VM_SIMD.h:185
GLuint GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat t1
Definition: glew.h:12681
SYS_FORCE_INLINE UT_Array< exint > * nestingArray() noexcept
Definition: GEO_BVHImpl.h:245
exint append(void)
Definition: UT_Array.h:95
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 Storage::MathFloat normalize()
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:135
if(rank==1) return rank
SYS_FORCE_INLINE T maxDistance2(const UT_FixedVector< T, NAXES, INSTANTIATED > &p) const noexcept
Definition: UT_BVH.h:299
void getIntersectingBoxes(const UT::BVH< 4 > &bvh, const UT::Box< v4uf, NAXES > *node_boxes, const UT::Box< float, NAXES > &query_box, UT_Array< INT_TYPE > &box_indices, BVHUnorderedStack &stack) noexcept
Definition: UT_BVHImpl.h:2440
GLuint GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat t0
Definition: glew.h:12681
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:678
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:1448
SYS_FORCE_INLINE UT_Vector3 & lastUVW() noexcept
Definition: GEO_BVHImpl.h:255
GLsizei const GLfloat * value
Definition: glew.h:1849
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
GLdouble GLdouble t
Definition: glew.h:1398
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:122
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:455
bool SYSisFinite(fpreal16 f)
Definition: SYS_Math.h:201