HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
GEO_BVH.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: GEO_BVH.h (GEO Library, C++)
7  *
8  * COMMENTS: Bounding Volume Hierarchy (BVH) implementation for GEO_Detail.
9  */
10 
11 #pragma once
12 
13 #include "GEO_API.h"
14 #include <GA/GA_Handle.h>
15 #include <GA/GA_Types.h>
16 #include <UT/UT_BVH.h>
17 #include <UT/UT_UniquePtr.h>
18 #include <UT/UT_Vector3.h>
19 #include <limits>
20 
21 #define GEO_BVH_INTERLEAVED 1
22 #if GEO_BVH_INTERLEAVED
23 #include <VM/VM_SIMD.h>
24 #endif
25 
26 class GEO_Detail;
27 
28 namespace GEO {
29 
30 template<uint NAXES,typename SUBCLASS>
32 {
33 public:
34  BVHBase() noexcept
35  : myHasCurvesOrPoints(false)
36  {}
37  ~BVHBase() noexcept {}
38 
42 #if !GEO_BVH_INTERLEAVED
44 #else
46 #endif
47 
48 protected:
49  void clear() noexcept;
50 public:
51 
52  SYS_FORCE_INLINE bool isEmpty() const noexcept
53  {
54  return myTree.getNumNodes() == 0;
55  }
56 
57  struct ItemHitInfo
58  {
59  exint myItemIndex = -1;
61  };
62  struct CommonHitInfo : public ItemHitInfo
63  {
64  using ItemHitInfo::myItemIndex;
65  using ItemHitInfo::myUVW;
66 
67  /// This can be used for packed primitive hits.
68  UT_Array<exint> *myNestedItemIndices = nullptr;
69 
70  SYS_FORCE_INLINE bool isHit() const noexcept
71  {
72  return (myItemIndex >= 0);
73  }
74  };
75  struct HitInfo : public CommonHitInfo
76  {
77  float myT = -1;
78  };
79  struct HitInfoAndNormal : public HitInfo
80  {
82  };
83 
84  /// Sends a ray from the specified origin in the specified direction and
85  /// finds the closest (or farthest) intersection.
86  /// Potential hits less than tmin or greater than tmax from the origin are
87  /// treated as not having been hit, regardless of whether farthest is true.
88  /// If rm_backface is true, backface hits will be treated as no hit,
89  /// and if reverse is also true, frontface hits will be treated as no hit.
90  /// NOTE: If the hit_info.myNestedItemIndices is non-null,
91  /// it will be filled with the hit path,
92  /// ignoring the outermost index, which is in hit_info.myItemIndex.
93  template<bool farthest=false,bool rm_backface=false,bool reverse=false,typename HitInfoType>
94  void sendRay(const VectorType &origin, const VectorType &direction, HitInfoType &hit_info,
95  float tmin = 0, float tmax = std::numeric_limits<float>::max()) const noexcept;
96 
97  /// Like sendRay, except with a radius (tolerance) for curve and point hits,
98  /// in case myRadii is empty.
99  template<bool farthest=false,bool rm_backface=false,bool reverse=false,typename HitInfoType>
100  void sendRayRad(const VectorType &origin, const VectorType &direction, HitInfoType &hit_info,
101  float default_radius,
102  float tmin = 0, float tmax = std::numeric_limits<float>::max()) const noexcept;
103 
104  /// Sends a ray from the specified origin in the specified direction and
105  /// finds all intersections, removing all but one that are within
106  /// duplicate_tolerance of another hit.
107  /// Potential hits less than tmin or greater than tmax from the origin are
108  /// treated as not having been hit, regardless of whether farthest is true.
109  /// If rm_backface is true, backface hits will be treated as no hit,
110  /// and if reverse is also true, frontface hits will be treated as no hit.
111  /// NOTE: If nesting_temp_array is non-null, this function will allocate
112  /// nesting arrays for any applicable entries in hit_info, so the
113  /// caller is responsible for deleting myNestedItemIndices arrays in
114  /// hit_info. nesting_temp_array itself is just used for temporary
115  /// storage to reduce the number of allocations.
116  template<bool rm_backface=false,bool reverse=false,bool sort=true,typename HitInfoType>
117  void sendRayAll(const VectorType &origin, const VectorType &direction, UT_Array<HitInfoType> &hit_info,
118  UT_Array<exint> *nesting_temp_array=nullptr,
119  float duplicate_tolerance = 0,float tmin = 0, float tmax = std::numeric_limits<float>::max()) const noexcept;
120 
121  /// Like sendRayAll, except with a radius (tolerance) for curve and point hits,
122  /// in case myRadii is empty.
123  template<bool rm_backface=false,bool reverse=false,bool sort=true,typename HitInfoType>
124  void sendRayAllRad(const VectorType &origin, const VectorType &direction, UT_Array<HitInfoType> &hit_info,
125  float default_radius, UT_Array<exint> *nesting_temp_array=nullptr,
126  float duplicate_tolerance = 0,float tmin = 0, float tmax = std::numeric_limits<float>::max()) const noexcept;
127 
128 protected:
129  template<bool USE_TOLERANCE>
131  template<bool USE_TOLERANCE>
133  template<bool USE_TOLERANCE>
135  template<bool USE_TOLERANCE>
137 public:
138 
139  template<bool farthest,bool rm_backface,bool reverse,typename FUNCTOR>
140  void sendRayGeneric(VectorType origin, VectorType direction, FUNCTOR &hit_info,
141  float tmin = 0, float tmax = std::numeric_limits<float>::max()) const noexcept;
142 
143  struct MinInfo : public CommonHitInfo
144  {
145  float myDistSquared = -1;
147  };
148 
149  /// Finds the closest points to the infinite line containing `origin` with direction `direction`.
150  void findClosestToLine(VectorType origin, VectorType direction, const exint max_points, const float max_dist_squared,
151  UT::BVHOrderedStack& output_queue) const noexcept;
152 
153  /// Finds the closest points to the line segment with endpoints `p0` and `p1`.
154  void findClosestToSegment(VectorType p0, VectorType p1, const exint max_points, const float max_dist_squared,
155  UT::BVHOrderedStack& output_queue) const noexcept;
156 
157  /// Finds the closest points from the origin to any surface within max_dist_squared, within the cone containing
158  /// all points at most `angle` away from `direction`.
159  void findClosestInCone(VectorType origin, VectorType direction, const float angle, const exint max_points,
160  const float max_dist_squared, UT::BVHOrderedStack& output_queue) const noexcept;
161 
162  /// Finds the closest (or farthest) position to origin on any surface, as long as it's within max_dist_squared.
163  /// NOTE: If farthest is true, max_dist_squared is actually the *minimum* distance squared from the origin,
164  /// so you will need to specify a value.
165  template<bool farthest>
166  void findClosest(VectorType origin, MinInfo &min_info, float max_dist_squared = std::numeric_limits<float>::max()) const noexcept;
167 
168  /// Fills box_indices array with the indices of all boxes intersecting query_box.
169  /// NOTE: This does not clear out previous contents of indices, so that you
170  /// can easily query intersection with multiple boxes.
171  /// WARNING: DO NOT depend on the order of box_indices. If you need a consistent order, sort it.
172  void getIntersectingBoxes(const SingleBoxType &query_box, UT_Array<exint> &box_indices) const noexcept;
173 
174  SYS_FORCE_INLINE exint numPoints() const noexcept
175  {
176  return myPoints.size();
177  }
178  SYS_FORCE_INLINE GA_Offset pointOffset(exint item_index) const noexcept
179  {
180  UT_ASSERT_P(item_index < numPoints());
181  return myPoints(item_index);
182  }
183 
184  /// Returns the geometric normal (not based on the N attribute) for the hit surface,
185  /// optionally normalized, since apparently Mantra doesn't need it normalized.
186  template<bool normalize=true>
187  VectorType getGeometricNormal(const CommonHitInfo &hit_info) const noexcept;
188 
189  /// Fills in the values of dP/du and dP/dv for the hit surface.
190  void getDerivs(const CommonHitInfo &hit_info, VectorType &dP_du, VectorType &dP_dv) const noexcept;
191 
192  /// For points, this converts the uvw from ItemHitInfo to polar form.
193  /// The original is effectively a normal.
194  static void pointUVWToPolar(VectorType &uvw) noexcept;
195 
196  /// Returns true on success, false on failure. The function can fail if the hit is on a point
197  /// and the attribute is a vertex or primitive attribute.
198  template<GA_AttributeOwner owner,typename T,typename DEST_T>
199  bool getAttribute(const CommonHitInfo &hit_info, const GA_ROHandleT<T> &attrib, const GEO_Detail &detail, DEST_T &value) const noexcept;
200 
202  {
203  SingleBoxType bbox;
204  if (isEmpty())
205  {
206  bbox.initBounds();
207  return bbox;
208  }
209 
210  BoxType &root_boxes = myNodeBoxes[0];
211  for (uint axis = 0; axis < NAXES; ++axis) {
212  SYS_STATIC_ASSERT(sizeof(root_boxes[axis][0]) == 4*sizeof(float));
213  float *vmin = (float*)&root_boxes[axis][0];
214  bbox[axis][0] = SYSmin(vmin[0],vmin[1],vmin[2],vmin[3]);
215  float *vmax = (float*)&root_boxes[axis][1];
216  bbox[axis][1] = SYSmax(vmax[0],vmax[1],vmax[2],vmax[3]);
217  }
218  return bbox;
219  }
220 
221 #ifdef GA_STRICT_TYPES
222  class PosAttribType : public GA_ROHandleT<VectorType>
223  {
224  using Parent = GA_ROHandleT<VectorType>;
225  public:
226  using Parent::Parent;
227  using Parent::operator[];
228  using Parent::operator=;
229 
230  SYS_FORCE_INLINE VectorType operator[](exint offset) const
231  {
232  return Parent::get(GA_Offset(offset));
233  }
234  };
235  class RadAttribType : public GA_ROHandleF
236  {
237  using Parent = GA_ROHandleF;
238  public:
239  using Parent::Parent;
240  using Parent::operator[];
241  using Parent::operator=;
242 
243  SYS_FORCE_INLINE float operator[](exint offset) const
244  {
245  return Parent::get(GA_Offset(offset));
246  }
247  };
248 #else
251 #endif
252 
253 protected:
254  SYS_FORCE_INLINE SUBCLASS *subclass() noexcept { return static_cast<SUBCLASS*>(this); }
255  SYS_FORCE_INLINE const SUBCLASS *subclass() const noexcept { return static_cast<const SUBCLASS*>(this); }
256 
257  template<bool farthest,typename QUERY_POINT>
258  void findMaximalPointsCommon(
259  const QUERY_POINT &query_point,
260  UT::BVHOrderedStack &stack,
261  UT::BVHOrderedStack &output_queue,
262  exint max_points,
263  float max_dist_squared) const noexcept;
264 
265  using NodeData = BoxType;
266 
267 #if !GEO_BVH_INTERLEAVED
268  static constexpr uint BVH_N = 2;
269 #else
270  static constexpr uint BVH_N = 4;
271 #endif
274  //UT_UniquePtr<uint[]> myIndices;
276 
277  /// Positions for points
279 
280  /// Radii for disconnected points
282 
283  /// Attribute for positions, to avoid having to copy all positions into
284  /// myPositions if only a small subset of points are needed.
286 
287  /// Attribute for radii, to avoid having to copy all radii into
288  /// myRadii if only a small subset of points are needed.
290 
291  /// Disconnected points
293 
294  /// Data IDs for myPositions and myRadii
295  /// @{
298  /// @}
299 
301 };
302 
303 #if 0
304 template<uint NAXES>
305 struct QueryPtWrapper {
306  template<bool INSTANTIATED>
308  : q(p), vq(p)
309  {}
310 
311  /// This is used for findClosest.
312  /// It can optionally return an underestimate, but NOT an overestimate.
313  /// @{
314  SYS_FORCE_INLINE float boxMinDist2(const UT::Box<float,NAXES> &box) const
315  { return box.minDistance2(q); }
316  SYS_FORCE_INLINE v4uf boxMinDist2(const UT::Box<v4uf,NAXES> &box) const
317  { return box.minDistance2(vq); }
318  /// @}
319 
320  /// This is used for findFarthest.
321  /// It can optionally return an overestimate, but NOT an underestimate.
322  /// @{
323  SYS_FORCE_INLINE float boxMaxDist2(const UT::Box<float,NAXES> &box) const
324  { return box.maxDistance2(q); }
325  SYS_FORCE_INLINE v4uf boxMaxDist2(const UT::Box<v4uf,NAXES> &box) const
326  { return box.maxDistance2(vq); }
327  /// @}
328 
329  /// This should be exact
330  template<bool INSTANTIATED>
332  { return q.distance2(p); }
333 
334  /// These are for culling the query space
335  /// @{
336  SYS_FORCE_INLINE constexpr bool isValid(const UT::Box<float,NAXES> &box) const
337  { return true; }
338  static constexpr bool theHasBoxValidCheck = false;
339  SYS_FORCE_INLINE constexpr v4uu isValid(const UT::Box<v4uf,NAXES> &box) const
340  { return v4uu(1); }
341  template<typename INT_TYPE>
342  SYS_FORCE_INLINE constexpr bool isValid(INT_TYPE index) const
343  { return true; }
344  template<bool INSTANTIATED>
345  SYS_FORCE_INLINE constexpr bool isValid(const UT_FixedVector<float,NAXES,INSTANTIATED> &p) const
346  { return true; }
347  /// @}
348 
349 private:
352 };
353 
354 template<uint NAXES,bool INSTANTIATED>
355 SYS_FORCE_INLINE QueryPtWrapper<NAXES> QueryPoint(const UT_FixedVector<float,NAXES,INSTANTIATED> &p)
356 { return QueryPtWrapper<NAXES>(p); }
357 #endif
358 
359 template<uint NAXES>
360 class PointBVHT : public BVHBase<NAXES,PointBVHT<NAXES>>
361 {
362 public:
364  using typename Parent::VectorType;
365  using typename Parent::UintVectorType;
366  using typename Parent::SingleBoxType;
367  using typename Parent::BoxType;
368 
371 
372  /// NOTE: With this signature, radius is the point radius.
374  void init(const GA_Detail &detail,
375  const GA_ROHandleT<VectorType> &P,
376  const float radius = 0.0f,
377  const GA_Range *point_range=nullptr,
378  const bool force_rebalance=false) noexcept
379  {
380  init(detail, P, GA_ROHandleF(), radius, point_range, force_rebalance);
381  }
382 
383  /// NOTE: With this signature, P can have a tuple size other than 3,
384  /// though if tuple size is more than 3, only the first 3 components
385  /// will be used, and if tuple size is less than 3, the remaining
386  /// components will be treated as having value 0.0.
387  /// NOTE: With this signature, radius is the point radius.
389  void init(const GA_Detail &detail,
390  const GA_ROHandleF &P,
391  const float radius = 0.0f,
392  const GA_Range *point_range=nullptr,
393  const bool force_rebalance=false) noexcept
394  {
395  init(detail, P, GA_ROHandleF(), radius, point_range, force_rebalance);
396  }
397 
398  /// NOTE: With this signature, radscale scales the pscale attribute
399  /// if it's a valid attribute, else it's the point radius.
401  void init(const GA_Detail &detail,
402  const GA_ROHandleT<VectorType> &P,
403  const GA_ROHandleF &pscale,
404  const float radscale = 1.0f,
405  const GA_Range *point_range=nullptr,
406  const bool force_rebalance=false) noexcept
407  {
408  initAttribCommon(detail, P, pscale, radscale, point_range, force_rebalance);
409  }
410 
411  /// NOTE: With this signature, P can have a tuple size other than 3,
412  /// though if tuple size is more than 3, only the first 3 components
413  /// will be used, and if tuple size is less than 3, the remaining
414  /// components will be treated as having value 0.0.
415  /// NOTE: With this signature, radscale scales the pscale attribute
416  /// if it's a valid attribute, else it's the point radius.
418  void init(const GA_Detail &detail,
419  const GA_ROHandleF &P,
420  const GA_ROHandleF &pscale,
421  const float radscale = 1.0f,
422  const GA_Range *point_range=nullptr,
423  const bool force_rebalance=false) noexcept
424  {
425  // Check for tuple size match.
426  if (P.isValid() && P->getTupleSize() == NAXES)
427  initAttribCommon(detail, GA_ROHandleT<VectorType>(P.getAttribute()), pscale, radscale, point_range, force_rebalance);
428  else
429  initAttribCommon(detail, P, pscale, radscale, point_range, force_rebalance);
430  }
431 
432  /// NOTE: With this signature, radius is the point radius.
434  void init(const exint n,
435  const VectorType *P,
436  const float radius = 0.0f,
437  const bool rebalance=true) noexcept
438  {
439  init(n, P, nullptr, radius, rebalance);
440  }
441 
442  /// NOTE: With this signature, radscale scales the pscale values
443  /// if it's non-null, else it's the point radius.
444  GEO_API void init(const exint n,
445  const VectorType *P,
446  const float *pscale,
447  const float radscale = 1.0f,
448  const bool rebalance=true) noexcept;
449 
450 #if 0
451  /// Find the closest point to the position specified. This method
452  /// returns -1 if no point is found.
453  /// NOTE THAT max_distance_squared IS SQUARED DISTANCE.
454  template<bool farthest,typename QueryPointType>
456  const QueryPointType &pt,
457  QueueType &queue,
458  exint max_points = std::numeric_limits<exint>::max(),
459  IntArrayType *list = nullptr,
460  float max_distance_squared = std::numeric_limits<float>::max()) const noexcept;
461 #endif
462 
463  using typename Parent::ItemHitInfo;
464  using typename Parent::CommonHitInfo;
465  using typename Parent::HitInfo;
466  using typename Parent::MinInfo;
467  using Parent::numPoints;
468  using Parent::isEmpty;
469  using Parent::clear;
470 
471  /// Finds the closest points (up to max_points of them)
472  /// within sqrt(max_distance_squared) of query_pt
475  const VectorType &query_pt,
476  UT::BVHOrderedStack &stack,
477  UT::BVHOrderedStack &output_queue,
478  exint max_points = std::numeric_limits<uint>::max(),
479  float max_distance_squared = std::numeric_limits<float>::max()) const noexcept
480  {
481  findMaximalPoints<false>(query_pt, stack,
482  output_queue, max_points, max_distance_squared);
483  }
484 
485  /// Finds the farthest points (up to max_points of them)
486  /// at least sqrt(min_distance_squared) away from query_pt
489  const VectorType &query_pt,
490  UT::BVHOrderedStack &stack,
491  UT::BVHOrderedStack &output_queue,
492  exint max_points = std::numeric_limits<uint>::max(),
493  float min_distance_squared = 0.0f) const noexcept
494  {
495  findMaximalPoints<true>(query_pt, stack,
496  output_queue, max_points, min_distance_squared);
497  }
498 
499  /// Sorts results from findClosestPoints or findFarthestPoints by distance
500  /// squared, and, in the case of ties, by the point offsets.
501  /// If farthest is true, it puts farther distances first, and breaks
502  /// ties with larger offsets first.
503  template<bool farthest>
504  GEO_API void sortResults(UT::BVHOrderedStack &closepts) const noexcept;
505 
506  template<bool farthest>
508  const VectorType &query_pt,
509  UT::BVHOrderedStack &stack,
510  UT::BVHOrderedStack &output_queue,
511  exint max_points,
512  float max_distance_squared) const noexcept;
513 
514  /// Don't call this unless you really need to. It might have to change in the future.
515  /// The array is owned by myPoints.
516  GEO_API const exint *getPointsArray() const noexcept;
517 
518 protected:
519  static constexpr bool theHasPrimitives = false;
520  static constexpr bool theReordersPositions = true;
521 
522  using Parent::myTree;
523  using Parent::myNodeBoxes;
524  using Parent::myNodeNItems;
525  using Parent::myPositions;
526  using Parent::myRadii;
527  using Parent::myPosAttrib;
528  using Parent::myRadAttrib;
529  using Parent::myPoints;
530  using Parent::myPositionsDataId;
531  using Parent::myRadiiDataId;
533  using Parent::BVH_N;
534 
537  const GA_Range *point_range,
538  const bool topology_changed,
539  const GA_Size npoints) noexcept;
541  const GA_ROHandleF &P,
542  const GA_Range *point_range,
543  const bool topology_changed,
544  const GA_Size npoints) noexcept;
545 
546  /// This is instantiated for VectorType and float.
547  template<typename T>
549  const GA_Detail &detail,
550  const GA_ROHandleT<T> &P,
551  const GA_ROHandleF &pscale,
552  const float radscale,
553  const GA_Range *point_range,
554  const bool force_rebalance) noexcept;
555 
556  GEO_API void initCommon(bool topology_changed,
557  const VectorType *orig_order_positions,
558  const float *orig_order_radii) noexcept;
559 
560  template<bool farthest,bool rm_backface,bool reverse,typename FUNCTOR>
562  uint index, const VectorType &origin, const VectorType &direction,
563  const VectorType &inverse_direction,
564  int &max_dir, VectorType &N0, VectorType &N1,
565  float &outer_tmax, float &outer_tmin, FUNCTOR &hit_info) const noexcept
566  {
567  UT_ASSERT_MSG(0, "Base class should deal with intersecting points");
568  return false;
569  }
570  template<bool farthest>
572  uint index, const VectorType &origin, float &max_dist_squared,
573  exint &hit_index, UT_Vector3 &hit_uvw, VectorType &hit_position,
574  const UT_FixedVector<v4uf,NAXES> &vorigin,
575  UT_Array<exint> *nesting_array,
576  exint nesting_array_base) const noexcept
577  {
578  UT_ASSERT_MSG(0, "Base class should deal with findign closest points");
579  }
580  template<bool normalize>
581  SYS_FORCE_INLINE VectorType primGeometricNormal(const CommonHitInfo &hit_info) const noexcept
582  {
583  UT_ASSERT_MSG(0, "Base class should deal with normals for points");
584  return VectorType(float(0));
585  }
586  SYS_FORCE_INLINE void primDerivs(const CommonHitInfo &hit_info, VectorType &dP_du, VectorType &dP_dv) const noexcept
587  {
588  UT_ASSERT_MSG(0, "Base class should deal with derivatives for points");
589  }
590  template<GA_AttributeOwner owner,typename T,typename DEST_T>
591  SYS_FORCE_INLINE bool primAttribute(const CommonHitInfo &hit_info, const GA_ROHandleT<T> &attrib, const GEO_Detail &detail, DEST_T &value) const noexcept
592  {
593  UT_ASSERT_MSG(0, "Base class should deal with attributes for points");
594  return false;
595  }
596 
597 private:
598  friend Parent;
599 };
600 
603 
604 } // GEO namespace
605 
608 
609 #undef GEO_BVH_INTERLEAVED
#define SYSmax(a, b)
Definition: SYS_Math.h:1521
SYS_FORCE_INLINE void primDerivs(const CommonHitInfo &hit_info, VectorType &dP_du, VectorType &dP_dv) const noexcept
Definition: GEO_BVH.h:586
vint4 max(const vint4 &a, const vint4 &b)
Definition: simd.h:4703
SYS_FORCE_INLINE VectorType primGeometricNormal(const CommonHitInfo &hit_info) const noexcept
Definition: GEO_BVH.h:581
static constexpr bool theReordersPositions
Definition: GEO_BVH.h:520
#define SYS_STATIC_ASSERT(expr)
GA_DataId myRadiiDataId
Definition: GEO_BVH.h:297
SYS_FORCE_INLINE bool primAttribute(const CommonHitInfo &hit_info, const GA_ROHandleT< T > &attrib, const GEO_Detail &detail, DEST_T &value) const noexcept
Definition: GEO_BVH.h:591
bool myHasCurvesOrPoints
Definition: GEO_BVH.h:300
RadAttribType myRadAttrib
Definition: GEO_BVH.h:289
SYS_FORCE_INLINE void init(const GA_Detail &detail, const GA_ROHandleF &P, const float radius=0.0f, const GA_Range *point_range=nullptr, const bool force_rebalance=false) noexcept
Definition: GEO_BVH.h:389
Definition: UT_BVH.h:37
void findClosest(VectorType origin, MinInfo &min_info, float max_dist_squared=std::numeric_limits< float >::max()) const noexcept
GLuint index
Definition: glew.h:1814
int64 GA_DataId
Definition: GA_Types.h:685
IMF_EXPORT IMATH_NAMESPACE::V3f direction(const IMATH_NAMESPACE::Box2i &dataWindow, const IMATH_NAMESPACE::V2f &pixelPosition)
UT_Array< float > myRadii
Radii for disconnected points.
Definition: GEO_BVH.h:281
GEO_API void findMaximalPoints(const VectorType &query_pt, UT::BVHOrderedStack &stack, UT::BVHOrderedStack &output_queue, exint max_points, float max_distance_squared) const noexcept
int getTupleSize() const
UT_UniquePtr< BoxType[]> myNodeBoxes
Definition: GEO_BVH.h:273
UT_Array< VectorType > myPositions
Positions for points.
Definition: GEO_BVH.h:278
SYS_FORCE_INLINE T minDistance2(const UT_FixedVector< T, NAXES, INSTANTIATED > &p) const noexcept
Definition: UT_BVH.h:286
fpreal64 distance2(const UT_VectorD &v1, const UT_VectorD &v2)
Distance squared (L2) aka quadrance.
Definition: UT_Vector.h:399
int64 exint
Definition: SYS_Types.h:125
SYS_FORCE_INLINE GA_Offset pointOffset(exint item_index) const noexcept
Definition: GEO_BVH.h:178
void reverse(I begin, I end)
Definition: pugixml.cpp:7190
static constexpr bool theHasPrimitives
Definition: GEO_BVH.h:519
SYS_FORCE_INLINE void initBounds() noexcept
Definition: UT_BVH.h:81
GLdouble angle
Definition: glew.h:9135
SYS_FORCE_INLINE void init(const GA_Detail &detail, const GA_ROHandleT< VectorType > &P, const float radius=0.0f, const GA_Range *point_range=nullptr, const bool force_rebalance=false) noexcept
NOTE: With this signature, radius is the point radius.
Definition: GEO_BVH.h:374
SYS_FORCE_INLINE exint numPoints() const noexcept
Definition: GEO_BVH.h:174
exint GA_Size
Defines the bit width for index and offset types in GA.
Definition: GA_Types.h:233
SYS_FORCE_INLINE void init(const exint n, const VectorType *P, const float radius=0.0f, const bool rebalance=true) noexcept
NOTE: With this signature, radius is the point radius.
Definition: GEO_BVH.h:434
PointBVHT< 2 > PointBVH_2D
Definition: GEO_BVH.h:602
A range of elements in an index-map.
Definition: GA_Range.h:42
SingleBoxType getBBox() const noexcept
Definition: GEO_BVH.h:201
std::unique_ptr< T, Deleter > UT_UniquePtr
A smart pointer for unique ownership of dynamically allocated objects.
Definition: UT_UniquePtr.h:33
SYS_FORCE_INLINE void closestPrim(uint index, const VectorType &origin, float &max_dist_squared, exint &hit_index, UT_Vector3 &hit_uvw, VectorType &hit_position, const UT_FixedVector< v4uf, NAXES > &vorigin, UT_Array< exint > *nesting_array, exint nesting_array_base) const noexcept
Definition: GEO_BVH.h:571
#define UT_ASSERT_MSG(ZZ,...)
Definition: UT_Assert.h:138
const GA_ATINumeric * getAttribute() const
Definition: GA_Handle.h:163
PointBVHT< 3 > PointBVH
Definition: GEO_BVH.h:601
GA_Size GA_Offset
Definition: GA_Types.h:639
GLdouble GLdouble GLdouble GLdouble q
Definition: glew.h:1414
SYS_FORCE_INLINE void findClosestPoints(const VectorType &query_pt, UT::BVHOrderedStack &stack, UT::BVHOrderedStack &output_queue, exint max_points=std::numeric_limits< uint >::max(), float max_distance_squared=std::numeric_limits< float >::max()) const noexcept
Definition: GEO_BVH.h:474
SYS_FORCE_INLINE PointBVHT() noexcept
Definition: GEO_BVH.h:369
GLclampf f
Definition: glew.h:3499
SYS_FORCE_INLINE ~PointBVHT() noexcept
Definition: GEO_BVH.h:370
UT_BVH< BVH_N > myTree
Definition: GEO_BVH.h:272
Definition: VM_SIMD.h:46
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:134
UT::Box< v4uf, NAXES > BoxType
Definition: GEO_BVH.h:45
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
GA_ROHandleT< fpreal32 > GA_ROHandleF
Definition: GA_Handle.h:1268
Definition: VM_SIMD.h:186
GLsizei n
Definition: glew.h:4040
#define GEO_API
Definition: GEO_API.h:14
SYS_FORCE_INLINE void findFarthestPoints(const VectorType &query_pt, UT::BVHOrderedStack &stack, UT::BVHOrderedStack &output_queue, exint max_points=std::numeric_limits< uint >::max(), float min_distance_squared=0.0f) const noexcept
Definition: GEO_BVH.h:488
void clear() noexcept
Definition: GEO_BVHImpl.h:34
*get result *(waiting if necessary)*A common idiom is to fire a bunch of sub tasks at the queue
Definition: thread.h:643
typename SYS_SelectType< UT_Vector2, UT_Vector3, NAXES==3 >::type VectorType
Definition: GEO_BVH.h:39
typename SYS_SelectType< UT_FixedVector< uint, 2 >, UT_FixedVector< uint, 3 >, NAXES==3 >::type UintVectorType
Definition: GEO_BVH.h:40
BVHBase< NAXES, PointBVHT< NAXES >> Parent
Definition: GEO_BVH.h:363
BVHBase() noexcept
Definition: GEO_BVH.h:34
GEO_API const exint * getPointsArray() const noexcept
~BVHBase() noexcept
Definition: GEO_BVH.h:37
SYS_FORCE_INLINE bool isEmpty() const noexcept
Definition: GEO_BVH.h:52
SYS_FORCE_INLINE bool isValid() const
Definition: GA_Handle.h:184
GLfloat GLfloat p
Definition: glew.h:16321
GEO_API void fillPositionArray(const GA_ROHandleT< VectorType > &P, const GA_Range *point_range, const bool topology_changed, const GA_Size npoints) noexcept
SYS_FORCE_INLINE const SUBCLASS * subclass() const noexcept
Definition: GEO_BVH.h:255
typename SYS_SelectType< UT_Vector2, UT_Vector3, NAXES==3 >::type VectorType
Definition: GEO_BVH.h:39
UT_UniquePtr< UT_FixedVector< int32, BVH_N >[]> myNodeNItems
Definition: GEO_BVH.h:275
GA_API const UT_StringHolder pscale
GEO_API void initCommon(bool topology_changed, const VectorType *orig_order_positions, const float *orig_order_radii) noexcept
SYS_FORCE_INLINE void init(const GA_Detail &detail, const GA_ROHandleT< VectorType > &P, const GA_ROHandleF &pscale, const float radscale=1.0f, const GA_Range *point_range=nullptr, const bool force_rebalance=false) noexcept
Definition: GEO_BVH.h:401
Container class for all geometry.
Definition: GA_Detail.h:95
GA_OffsetList myPoints
Disconnected points.
Definition: GEO_BVH.h:292
SYS_FORCE_INLINE T maxDistance2(const UT_FixedVector< T, NAXES, INSTANTIATED > &p) const noexcept
Definition: UT_BVH.h:299
void getIntersectingBoxes(const UT::BVH< 4 > &bvh, const UT::Box< v4uf, NAXES > *node_boxes, const UT::Box< float, NAXES > &query_box, UT_Array< INT_TYPE > &box_indices, BVHUnorderedStack &stack) noexcept
Definition: UT_BVHImpl.h:2444
#define const
Definition: zconf.h:214
SYS_FORCE_INLINE SUBCLASS * subclass() noexcept
Definition: GEO_BVH.h:254
SYS_FORCE_INLINE bool isHit() const noexcept
Definition: GEO_BVH.h:70
PosAttribType myPosAttrib
Definition: GEO_BVH.h:285
#define SYSmin(a, b)
Definition: SYS_Math.h:1522
GA_DataId myPositionsDataId
Definition: GEO_BVH.h:296
GEO_API void sortResults(UT::BVHOrderedStack &closepts) const noexcept
GLsizei const GLfloat * value
Definition: glew.h:1849
unsigned int uint
Definition: SYS_Types.h:45
void sort(I begin, I end, const Pred &pred)
Definition: pugixml.cpp:7334
SYS_FORCE_INLINE bool intersectPrim(uint index, const VectorType &origin, const VectorType &direction, const VectorType &inverse_direction, int &max_dir, VectorType &N0, VectorType &N1, float &outer_tmax, float &outer_tmin, FUNCTOR &hit_info) const noexcept
Definition: GEO_BVH.h:561
#define GEO_API_TMPL
Definition: GEO_API.h:15
GEO_API void initAttribCommon(const GA_Detail &detail, const GA_ROHandleT< T > &P, const GA_ROHandleF &pscale, const float radscale, const GA_Range *point_range, const bool force_rebalance) noexcept
This is instantiated for VectorType and float.
UT::Box< float, NAXES > SingleBoxType
Definition: GEO_BVH.h:41
SYS_FORCE_INLINE void init(const GA_Detail &detail, const GA_ROHandleF &P, const GA_ROHandleF &pscale, const float radscale=1.0f, const GA_Range *point_range=nullptr, const bool force_rebalance=false) noexcept
Definition: GEO_BVH.h:418
type
Definition: core.h:528
GLintptr offset
Definition: glew.h:1682
VectorType myP
Definition: GEO_BVH.h:146