HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
GU_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: GU_BVH.h (GU Library, C++)
7  *
8  * COMMENTS: Bounding Volume Hierarchy (BVH) implementation for GEO_Detail.
9  */
10 
11 #pragma once
12 
13 #include "GU_API.h"
14 #include <GEO/GEO_BVH.h>
15 #include <GA/GA_Handle.h>
16 #include <GA/GA_Types.h>
17 #include <UT/UT_ArrayMap.h>
18 #include <UT/UT_UniquePtr.h>
19 #include <UT/UT_Vector3.h>
20 #include <VM/VM_SIMD.h>
21 #include <limits>
22 
23 class UT_Lock;
24 class GU_PackedImpl;
25 class GU_RayPrimInfo;
27 
28 namespace GU {
29 
30 template<uint NAXES,typename SUBCLASS>
32 
33 class GU_API BVH : public BVHBase<3, BVH>
34 {
35  using Base = BVHBase<3, BVH>;
36  friend Base;
37  static constexpr uint NAXES = 3;
38 
39  static constexpr bool theHasPrimitives = true;
40  static constexpr bool theReordersPositions = false;
41 
42  enum OtherPrimType : uint
43  {
44  OTHERPRIM_BVHXLATESCALE,
45  OTHERPRIM_BVHUNIFORM,
46  OTHERPRIM_BVHFULLXFORM,
47  OTHERPRIM_RAYPRIMINFO,
48  OTHERPRIM_HEIGHTFIELD,
49  OTHERPRIM_SEGMENT,
50  OTHERPRIM_NGON_TRI,
51  OTHERPRIM_NGON_QUAD
52  };
53 
54  struct TranslateScale
55  {
57  double inverse_scale;
58 
59  SYS_FORCE_INLINE void transformPosition(UT_Vector3D &position) const
60  {
61  position = position/inverse_scale + translate;
62  }
63  SYS_FORCE_INLINE void inverseTransformPosition(UT_Vector3D &position) const
64  {
65  position = (position - translate)*inverse_scale;
66  }
67  SYS_FORCE_INLINE void transformDirection(UT_Vector3D &vector) const
68  {
69  // Nothing to do, since we'd just normalize out the scale anyway
70  }
71  SYS_FORCE_INLINE void inverseTransformDirection(UT_Vector3D &vector) const
72  {
73  // Nothing to do, since we'd just normalize out the scale anyway
74  }
75  SYS_FORCE_INLINE void transformVector(UT_Vector3D &vector) const
76  {
77  vector /= inverse_scale;
78  }
79  SYS_FORCE_INLINE float scaleT(float t) const
80  {
81  return t/inverse_scale;
82  }
83  SYS_FORCE_INLINE float inverseScaleT(float t) const
84  {
85  return t*inverse_scale;
86  }
87  };
88  struct UniformTransform
89  {
90  /// This is scaled by sqrt(inverse_scale), so that if we do
91  /// rotation.conjugate()*P*rotation, without normalizing,
92  /// it'll automatically apply the inverse scale.
95  double scale;
96 
97  SYS_FORCE_INLINE void transformPosition(UT_Vector3D &position) const
98  {
99  // NOTE: UT_QuaternionT::rotate assumes that rotation is normalized.
100  // We're using the fact that it's not, to our advantage,
101  // to automatically apply the scale.
102  position = (rotation*scale).rotate(position) + translate;
103  }
104  SYS_FORCE_INLINE void inverseTransformPosition(UT_Vector3D &position) const
105  {
106  // NOTE: UT_QuaternionT::rotateInverse assumes that rotation is normalized.
107  // We're using the fact that it's not, to our advantage,
108  // to automatically apply the inverse scale.
109  position = rotation.rotateInverse(position - translate);
110  }
111  SYS_FORCE_INLINE void transformDirection(UT_Vector3D &vector) const
112  {
113  vector = rotation.rotate(vector);
114  // NOTE: UT_QuaternionT::rotate assumes that rotation is normalized,
115  // but it's not, so we need to normalize vector.
116  vector.normalize();
117  }
118  SYS_FORCE_INLINE void inverseTransformDirection(UT_Vector3D &vector) const
119  {
120  vector = rotation.rotateInverse(vector);
121  // NOTE: UT_QuaternionT::rotateInverse assumes that rotation is normalized,
122  // but it's not, so we need to normalize vector.
123  vector.normalize();
124  }
125  SYS_FORCE_INLINE void transformVector(UT_Vector3D &vector) const
126  {
127  vector = rotation.rotate(vector);
128  }
129  SYS_FORCE_INLINE float scaleT(float t) const
130  {
131  return t*scale;
132  }
133  SYS_FORCE_INLINE float inverseScaleT(float t) const
134  {
135  return t/scale;
136  }
137  };
138 
139  struct PrimData
140  {
141  GA_Offset myPrimOff;
142  union {
143  const BVH *myBVHPtr;
144  /// NOTE: This might be nullptr if the GU_RayPrimInfo was degenerate,
145  /// even if myOtherType is OTHERPRIM_RAYPRIMINFO.
146  GU_RayPrimInfo *myRayPrimPtr;
147  void *myDataPtr;
148  uint myDataInts[2];
149  /// NOTE: This can't be GA_Offset, since on strict types builds,
150  /// GA_Offset has a non-trivial default constructor.
151  GA_Size myPt0Off;
152  };
153  union {
154  struct {
155  /// Used for triangles
156  float myN[NAXES];
157  /// Used for w component of polygons in polygon soups
158  float myF;
159  };
160  struct {
161  union {
162  /// Used if myOtherType is not OTHERPRIM_RAYPRIMITIVE
163  void *myOtherTransform;
164 
165  /// Used if myOtherType is OTHERPRIM_RAYPRIMITIVE
166  const GEO_Detail *myDetail;
167 
168  /// Used if myOtherType is OTHERPRIM_SEGMENT
169  /// NOTE: This can't be GA_Offset, since on strict types builds,
170  /// GA_Offset has a non-trivial default constructor.
171  GA_Size myPt1Off;
172  };
173  /// Used if in the "other" primitive range
174  OtherPrimType myOtherType;
175 
176  /// Used if myOtherType is OTHERPRIM_SEGMENT
177  uint mySegment;
178  };
179  struct {
180  /// Used for mesh primitives
181  uint myCols;
182  uint myRows;
183  };
184  };
185  };
186 
187  struct NGonTri
188  {
189  UT_Vector3 myN;
190  char myNGonXAxis;
191  char myNGonYAxis;
192  GA_Offset myPtOffs[3];
193  float myNGonCentreX;
194  float myNGonCentreY;
195  };
196  struct NGonQuad
197  {
198  GA_Offset myPtOffs[4];
199  float myNGonCentreX;
200  float myNGonCentreY;
201  char myNGonXAxis;
202  char myNGonYAxis;
203  };
204 
205  /// Point offsets for triangles
206  /// This array actually contains myQuadPoints and myTetPoints, too.
207  UT_UniquePtr<GA_Offset[]> myTriPoints;
208  /// Point offsets for quads
209  /// This is actually a pointer into myTriPoints.
210  GA_Offset *myQuadPoints;
211  /// Point offsets for tets
212  /// This is actually a pointer into myTriPoints.
213  GA_Offset *myTetPoints;
214 
215  GA_Size myTriStart;
216  GA_Size myQuadStart;
217  GA_Size myTetStart;
218  GA_Size myOtherPrimStart;
219  GA_Size myNItems;
220 
221  GA_DataId myTopologyDataId;
222  GA_DataId myPrimitiveListDataId;
223 
224  /// Additional data for primitives, especially primitives that are not
225  /// triangles, quads, or tets.
226  UT_UniquePtr<PrimData[]> myPrimData;
227 
228  /// These are for managing packed primitives.
229  /// We share trees for common details, and we share details for common
230  /// packed primitive implementations that don't directly provide a detail.
231  /// @{
234  SecondaryTreeMap mySecondaryTrees;
235  SecondaryDetailMap mySecondaryDetails;
236  /// @}
237 
238  bool myHasSecondary;
239 
240 public:
242  : Base()
243  , myTriPoints(nullptr)
244  , myQuadPoints(nullptr)
245  , myTetPoints(nullptr)
246  , myTriStart(0)
247  , myQuadStart(0)
248  , myTetStart(0)
249  , myOtherPrimStart(0)
250  , myNItems(0)
251  , myTopologyDataId(GA_INVALID_DATAID)
252  , myPrimitiveListDataId(GA_INVALID_DATAID)
253  , myPrimData(nullptr)
254  , myHasSecondary(false)
255  {}
257  {
258  clear();
259  }
260 
261  SYS_FORCE_INLINE GA_Offset primitiveOffset(exint prim_index) const noexcept
262  {
263  return myPrimData[prim_index].myPrimOff;
264  }
265 
266  void clear() noexcept;
267 
268  SYS_FORCE_INLINE GA_Size numItems() const noexcept
269  {
270  return myNItems;
271  }
272 
273  struct Options
274  {
276  {
279  ALL_POINTS
280  };
281 
282  PointStyle points = NO_POINTS;
283 
284  const GA_Range *point_range = nullptr;
285  const GA_Range *prim_range = nullptr;
286  bool just_edges = false;
287 
288  /// If true, only triangles on the unshared surface of tetrahedra will
289  /// be added, not the solid tetrahedra themselves. findClosest will
290  /// find the closest surface point, and sendRay will only intersect the
291  /// surface.
292  ///
293  /// If false, only the solid tetrahedra will be added. findClosest will
294  /// find the current point if it's inside a tetrahedron, else the
295  /// closest surface point, and sendRay will intersect the current point
296  /// if it's inside a tetrahedron, else the first surface intersected.
297  bool tet_surface = false;
298  };
299 
300  /// NOTE: If options is different from what it was before, you must set
301  /// force_rebalance to true.
302  /// NOTE: With this signature, radscale scales the pscale attribute
303  /// if it's a valid attribute, else it's the point radius.
304  void init(const GEO_Detail &detail,
305  const GA_ROHandleT<VectorType> &P,
306  const Options &options,
307  const GA_ROHandleF &pscale,
308  const float radscale = 1.0f,
309  const bool force_rebalance=false,
310  SecondaryTreeMap *secondary_trees=nullptr,
311  SecondaryDetailMap *secondary_details=nullptr,
312  UT_Lock *secondary_lock=nullptr) noexcept;
313 
314  /// NOTE: With this signature, radius is the point radius.
315  void init(const GEO_Detail &detail,
317  const Options &options,
318  const float radius = 0.0f,
319  const bool force_rebalance=false) noexcept
320  {
321  init(detail, P, options, GA_ROHandleF(), radius, force_rebalance);
322  }
323 
324  SYS_FORCE_INLINE bool
325  isNGon(exint index) const noexcept
326  {
327  if (index < myOtherPrimStart)
328  return false;
329  exint prim_index = index - myTriStart;
330  OtherPrimType type = myPrimData[prim_index].myOtherType;
331  return type == OTHERPRIM_NGON_TRI || type == OTHERPRIM_NGON_QUAD;
332  }
333 
334  /// The UVWs returned for n-gons are for the sub-polygons,
335  /// so we need to compute the true UVWs from the positions.
336  UT_Vector3 findNGonUVW(exint index, const UT_Vector3 &position, const GEO_Detail &detail) const noexcept;
337 
338  SYS_FORCE_INLINE bool
339  isPacked(exint index) const noexcept
340  {
341  if (index < myOtherPrimStart)
342  return false;
343  exint prim_index = index - myTriStart;
344  OtherPrimType type = myPrimData[prim_index].myOtherType;
345  return type == OTHERPRIM_BVHUNIFORM || type == OTHERPRIM_BVHXLATESCALE || type == OTHERPRIM_BVHFULLXFORM;
346  }
347 
348 protected:
349  /// These are just used in the init function to change the decision about
350  /// clearing after some things have been initialized.
351  /// @{
352  void clearPrimDataAllocations() noexcept;
353  void clearSecondary() noexcept;
354  /// @}
355 
356  template<bool farthest,bool rm_backface,bool reverse,typename FUNCTOR>
357  bool intersectPrim(
358  uint index, const VectorType &origin, const VectorType &direction,
359  const VectorType &inverse_direction,
360  int &max_dir, VectorType &N0, VectorType &N1,
361  float &outer_tmax, float &outer_tmin, FUNCTOR &hit_info) const noexcept;
362  template<bool farthest>
363  void closestPrim(
364  uint index, const VectorType &origin, float &max_dist_squared,
365  exint &hit_index, UT_Vector3 &hit_uvw, VectorType &hit_position,
366  const UT_FixedVector<v4uf,NAXES> &vorigin,
367  UT_Array<exint> *nesting_array,
368  exint nesting_array_base) const noexcept;
369  template<bool normalize>
370  VectorType primGeometricNormal(const CommonHitInfo &hit_info) const noexcept;
371  SYS_FORCE_INLINE void primDerivs(const CommonHitInfo &hit_info, VectorType &dP_du, VectorType &dP_dv) const noexcept;
372  template<GA_AttributeOwner owner,typename T,typename DEST_T>
373  SYS_FORCE_INLINE bool primAttribute(const CommonHitInfo &hit_info, const GA_ROHandleT<T> &attrib, const GEO_Detail &detail, DEST_T &value) const noexcept;
374 
375  template<bool farthest,bool rm_backface,bool reverse,bool bidirectional=false,typename FUNCTOR>
376  static SYS_FORCE_INLINE bool intersectQuad(
377  const UT_Vector3 &origin,
378  const UT_Vector3 &inverse_direction,
379  const UT_Vector3 pos[4],
380  const int max_dir,
381  const UT_Vector3 &N0,
382  const UT_Vector3 &N1,
383  const PrimData &prim_data,
384  float &outer_tmin,
385  float &outer_tmax,
386  const uint index,
387  FUNCTOR &hit_info);
388 
389  template<bool farthest,bool rm_backface,bool reverse,bool bidirectional=false,typename FUNCTOR>
390  static SYS_FORCE_INLINE bool intersectTet(
391  const UT_Vector3 &origin,
392  const UT_Vector3 &inverse_direction,
393  const UT_Vector3 pos[4],
394  const PrimData &prim_data,
395  float &outer_tmin,
396  float &outer_tmax,
397  const uint index,
398  FUNCTOR &hit_info);
399 
400  template<bool farthest>
401  static SYS_FORCE_INLINE bool triClosestPoint(
402  uint index,
403  const VectorType &origin,
404  const VectorType pos[3],
405  const PrimData &prim_data,
406  const UT_Vector3 &normal,
407  float &max_dist_squared,
408  exint &hit_index,
409  UT_Vector3 &hit_uvw,
410  UT_Vector3 &hit_position);
411  template<bool farthest>
412  static SYS_FORCE_INLINE bool quadClosestPoint(
413  uint index,
414  const VectorType &origin,
415  const UT_FixedVector<v4uf,3> &vorigin,
416  const VectorType pos[4],
417  const PrimData &prim_data,
418  float &max_dist_squared,
419  exint &hit_index,
420  UT_Vector3 &hit_uvw,
421  UT_Vector3 &hit_position);
422 
423  template<typename V3_ARRAY>
424  SYS_FORCE_INLINE static void addTriangleData(
425  GA_Offset *&tri_points,
426  const V3_ARRAY &positions,
427  const GA_ROHandleT<VectorType> &posattrib,
428  PrimData *primdata,
429  SingleBoxType *prim_box_start,
430  exint &tri_primnum,
431  GA_Offset primoff,
432  int data_int = -1,
433  float data_float = 0) noexcept;
434 
435  template<typename V3_ARRAY>
436  SYS_FORCE_INLINE static void addQuadData(
437  GA_Offset *&quad_points,
438  const V3_ARRAY &positions,
439  const GA_ROHandleT<VectorType> &posattrib,
440  PrimData *primdata,
441  SingleBoxType *prim_box_start,
442  exint &quad_primnum,
443  GA_Offset primoff,
444  int data_int = -1,
445  float data_float = 0) noexcept;
446 
447  SYS_FORCE_INLINE static void addRayPrimInfo(
448  PrimData &primdata,
449  GA_Offset primoff,
450  SingleBoxType &primbox,
451  GU_RayPrimInfo *rayprim,
452  exint &other_primnum,
453  const GEO_Detail &detail,
454  float w = 0) noexcept;
455 
456 public:
457  // NOTE: These are only public to work around a compile error.
458  using BVHBase::SingleHitAndNormalFunctor;
459  using BVHBase::AllHitsAndNormalsFunctor;
460 
461  template<bool farthest,bool rm_backface,bool reverse,bool bidirectional,typename FUNCTOR>
463 protected:
464 
466 };
467 
468 #if 0
469 class GU_API BVH_2D : public BVHBase<2, BVH_2D>
470 {
471  using Base = BVHBase<2, BVH_2D>;
472  friend class Base;
473  static constexpr uint NAXES = 2;
474 
475  static constexpr bool theHasPrimitives = true;
476 
477  struct PrimData
478  {
479  GA_Offset myPrimOff;
480  union {
481  void *myDataPtr;
482  uint myDataInts[2];
483  };
484  VectorType myN;
485  float myF;
486  };
487 
488  /// Point offsets for segments
489  UT_UniquePtr<GA_Offset[]> mySegmentPoints;
490 
491  GA_Size myOtherPrimStart;
492 
493  /// Additional data for primitives.
494  UT_UniquePtr<PrimData[]> myPrimData;
495 
496 public:
497  SYS_FORCE_INLINE BVH_2D() noexcept
498  : Base()
499  , mySegmentPoints(nullptr)
500  {}
501 
502  SYS_FORCE_INLINE GA_Offset primitiveOffset(exint prim_index) const noexcept
503  {
504  return myPrimData[prim_index].myPrimOff;
505  }
506 
507  SYS_FORCE_INLINE void clear() noexcept
508  {
509  Base::clear();
510  mySegmentPoints.reset();
511  myPrimData.reset();
512  }
513 
514  struct Options
515  {
516  enum PointStyle
517  {
518  NO_POINTS,
519  DISCONNECTED_POINTS,
520  ALL_POINTS
521  };
522 
523  PointStyle points = NO_POINTS;
524 
525  const GA_Range *point_range = nullptr;
526  const GA_Range *prim_range = nullptr;
527  bool just_edges = false;
528  };
529 
530  void init(const GA_Detail &detail,
531  const GA_ROHandleT<VectorType> &P,
532  const Options &options,
534  const bool force_rebalance=false) noexcept;
535 
536 protected:
537  template<bool farthest,bool rm_backface,bool reverse>
538  SYS_FORCE_INLINE bool intersectPrim(
539  uint index, const VectorType &origin, const VectorType &direction,
540  const VectorType &inverse_direction,
541  int &max_dir, VectorType &N0, VectorType &N1,
542  float &outer_tmax, float &outer_tmin, exint &hit_index, UT_Vector3 &hit_uvw) const noexcept;
543  template<bool farthest>
544  SYS_FORCE_INLINE void closestPrim(
545  uint index, const VectorType &origin, float &max_dist_squared,
546  exint &hit_index, UT_Vector3 &hit_uvw, VectorType &hit_position,
547  const UT_FixedVector<v4uf,NAXES> &vorigin,
548  UT_Array<exint> *nesting_array,
549  exint nesting_array_base) const noexcept;
550  template<bool normalize>
551  SYS_FORCE_INLINE VectorType primGeometricNormal(const CommonHitInfo &hit_info) const noexcept;
552  SYS_FORCE_INLINE void primDerivs(const CommonHitInfo &hit_info, VectorType &dP_du, VectorType &dP_dv) const noexcept;
553  template<GA_AttributeOwner owner,typename T,typename DEST_T>
554  SYS_FORCE_INLINE bool primAttribute(const CommonHitInfo &hit_info, const GA_ROHandleT<T> &attrib, const GEO_Detail &detail, DEST_T &value) const noexcept;
555 };
556 #endif
557 
558 } // GU namespace
559 
560 using GU_BVH = GU::BVH;
561 
*get result *(waiting if necessary)*A common idiom is to fire a bunch of sub tasks at the and then *wait for them to all complete We provide a helper class
Definition: thread.h:643
GLuint index
Definition: glew.h:1814
int64 GA_DataId
Definition: GA_Types.h:683
IMF_EXPORT IMATH_NAMESPACE::V3f direction(const IMATH_NAMESPACE::Box2i &dataWindow, const IMATH_NAMESPACE::V2f &pixelPosition)
GLenum GLenum GLenum GLenum GLenum scale
Definition: glew.h:13880
Definition: GU_BVH.h:33
void reverse(I begin, I end)
Definition: pugixml.cpp:7190
#define GA_INVALID_DATAID
Definition: GA_Types.h:684
exint GA_Size
Defines the bit width for index and offset types in GA.
Definition: GA_Types.h:231
SYS_FORCE_INLINE bool isPacked(exint index) const noexcept
Definition: GU_BVH.h:339
SYS_FORCE_INLINE bool isNGon(exint index) const noexcept
Definition: GU_BVH.h:325
A range of elements in an index-map.
Definition: GA_Range.h:42
GA_Size GA_Offset
Definition: GA_Types.h:637
GLclampf f
Definition: glew.h:3499
int64 exint
Definition: SYS_Types.h:120
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
GLubyte GLubyte GLubyte GLubyte w
Definition: glew.h:1890
GA_ROHandleT< fpreal32 > GA_ROHandleF
Definition: GA_Handle.h:1244
Definition: VM_SIMD.h:188
SYS_FORCE_INLINE GA_Offset primitiveOffset(exint prim_index) const noexcept
Definition: GU_BVH.h:261
ImageBuf OIIO_API rotate(const ImageBuf &src, float angle, string_view filtername=string_view(), float filterwidth=0.0f, bool recompute_roi=false, ROI roi={}, int nthreads=0)
#define GU_API
Definition: GU_API.h:14
GridType::Ptr normalize(const GridType &grid, bool threaded, InterruptT *interrupt)
Normalize the vectors of the given vector-valued grid.
GLuint GLuint GLsizei GLenum type
Definition: glew.h:1253
unsigned int uint
Definition: SYS_Types.h:44
SYS_FORCE_INLINE ~BVH() noexcept
Definition: GU_BVH.h:256
GA_AttributeOwner
Definition: GA_Types.h:33
typename SYS_SelectType< UT_Vector2, UT_Vector3, NAXES==3 >::type VectorType
Definition: GEO_BVH.h:39
GLuint GLdouble GLdouble GLint GLint const GLdouble * points
Definition: glew.h:3446
SYS_FORCE_INLINE BVH() noexcept
Definition: GU_BVH.h:241
GA_API const UT_StringHolder pscale
SYS_FORCE_INLINE Storage::MathFloat normalize()
Container class for all geometry.
Definition: GA_Detail.h:95
#define const
Definition: zconf.h:214
PUGI__FN char_t * translate(char_t *buffer, const char_t *from, const char_t *to, size_t to_length)
Definition: pugixml.cpp:8352
GLsizei const GLfloat * value
Definition: glew.h:1849
GLdouble GLdouble t
Definition: glew.h:1398
MatType rotation(const Quat< typename MatType::value_type > &q, typename MatType::value_type eps=static_cast< typename MatType::value_type >(1.0e-8))
Return the rotation matrix specified by the given quaternion.
Definition: Mat.h:204