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 inverseTransformDirection(UT_Vector3D &vector) const
68  {
69  // Nothing to do, since we'd just normalize out the scale anyway
70  }
71  SYS_FORCE_INLINE void transformVector(UT_Vector3D &vector) const
72  {
73  vector /= inverse_scale;
74  }
75  SYS_FORCE_INLINE float scaleT(float t) const
76  {
77  return t/inverse_scale;
78  }
79  SYS_FORCE_INLINE float inverseScaleT(float t) const
80  {
81  return t*inverse_scale;
82  }
83  };
84  struct UniformTransform
85  {
86  /// This is scaled by sqrt(inverse_scale), so that if we do
87  /// rotation.conjugate()*P*rotation, without normalizing,
88  /// it'll automatically apply the inverse scale.
91  double scale;
92 
93  SYS_FORCE_INLINE void transformPosition(UT_Vector3D &position) const
94  {
95  // NOTE: UT_QuaternionT::rotate assumes that rotation is normalized.
96  // We're using the fact that it's not, to our advantage,
97  // to automatically apply the scale.
98  position = (rotation*scale).rotate(position) + translate;
99  }
100  SYS_FORCE_INLINE void inverseTransformPosition(UT_Vector3D &position) const
101  {
102  // NOTE: UT_QuaternionT::rotateInverse assumes that rotation is normalized.
103  // We're using the fact that it's not, to our advantage,
104  // to automatically apply the inverse scale.
105  position = rotation.rotateInverse(position - translate);
106  }
107  SYS_FORCE_INLINE void inverseTransformDirection(UT_Vector3D &vector) const
108  {
109  vector = rotation.rotateInverse(vector);
110  // NOTE: UT_QuaternionT::rotateInverse assumes that rotation is normalized,
111  // but it's not, so we need to normalize vector.
112  vector.normalize();
113  }
114  SYS_FORCE_INLINE void transformVector(UT_Vector3D &vector) const
115  {
116  vector = rotation.rotate(vector);
117  }
118  SYS_FORCE_INLINE float scaleT(float t) const
119  {
120  return t*scale;
121  }
122  SYS_FORCE_INLINE float inverseScaleT(float t) const
123  {
124  return t/scale;
125  }
126  };
127 
128  struct PrimData
129  {
130  GA_Offset myPrimOff;
131  union {
132  const BVH *myBVHPtr;
133  /// NOTE: This might be nullptr if the GU_RayPrimInfo was degenerate,
134  /// even if myOtherType is OTHERPRIM_RAYPRIMINFO.
135  GU_RayPrimInfo *myRayPrimPtr;
136  void *myDataPtr;
137  uint myDataInts[2];
138  /// NOTE: This can't be GA_Offset, since on strict types builds,
139  /// GA_Offset has a non-trivial default constructor.
140  GA_Size myPt0Off;
141  };
142  union {
143  struct {
144  /// Used for triangles
145  float myN[NAXES];
146  /// Used for w component of polygons in polygon soups
147  float myF;
148  };
149  struct {
150  union {
151  /// Used if myOtherType is not OTHERPRIM_RAYPRIMITIVE
152  void *myOtherTransform;
153 
154  /// Used if myOtherType is OTHERPRIM_RAYPRIMITIVE
155  const GEO_Detail *myDetail;
156 
157  /// Used if myOtherType is OTHERPRIM_SEGMENT
158  /// NOTE: This can't be GA_Offset, since on strict types builds,
159  /// GA_Offset has a non-trivial default constructor.
160  GA_Size myPt1Off;
161  };
162  /// Used if in the "other" primitive range
163  OtherPrimType myOtherType;
164 
165  /// Used if myOtherType is OTHERPRIM_SEGMENT
166  uint mySegment;
167  };
168  struct {
169  /// Used for mesh primitives
170  uint myCols;
171  uint myRows;
172  };
173  };
174  };
175 
176  struct NGonTri
177  {
178  UT_Vector3 myN;
179  char myNGonXAxis;
180  char myNGonYAxis;
181  GA_Offset myPtOffs[3];
182  float myNGonCentreX;
183  float myNGonCentreY;
184  };
185  struct NGonQuad
186  {
187  GA_Offset myPtOffs[4];
188  float myNGonCentreX;
189  float myNGonCentreY;
190  char myNGonXAxis;
191  char myNGonYAxis;
192  };
193 
194  /// Point offsets for triangles
195  /// This array actually contains myQuadPoints and myTetPoints, too.
196  UT_UniquePtr<GA_Offset[]> myTriPoints;
197  /// Point offsets for quads
198  /// This is actually a pointer into myTriPoints.
199  GA_Offset *myQuadPoints;
200  /// Point offsets for tets
201  /// This is actually a pointer into myTriPoints.
202  GA_Offset *myTetPoints;
203 
204  GA_Size myTriStart;
205  GA_Size myQuadStart;
206  GA_Size myTetStart;
207  GA_Size myOtherPrimStart;
208  GA_Size myNItems;
209 
210  GA_DataId myTopologyDataId;
211  GA_DataId myPrimitiveListDataId;
212 
213  /// Additional data for primitives, especially primitives that are not
214  /// triangles, quads, or tets.
215  UT_UniquePtr<PrimData[]> myPrimData;
216 
217  /// These are for managing packed primitives.
218  /// We share trees for common details, and we share details for common
219  /// packed primitive implementations that don't directly provide a detail.
220  /// @{
223  SecondaryTreeMap mySecondaryTrees;
224  SecondaryDetailMap mySecondaryDetails;
225  /// @}
226 
227  bool myHasSecondary;
228 
229 public:
231  : Base()
232  , myTriPoints(nullptr)
233  , myQuadPoints(nullptr)
234  , myTetPoints(nullptr)
235  , myTriStart(0)
236  , myQuadStart(0)
237  , myTetStart(0)
238  , myOtherPrimStart(0)
239  , myNItems(0)
240  , myTopologyDataId(GA_INVALID_DATAID)
241  , myPrimitiveListDataId(GA_INVALID_DATAID)
242  , myPrimData(nullptr)
243  , myHasSecondary(false)
244  {}
246  {
247  clear();
248  }
249 
250  SYS_FORCE_INLINE GA_Offset primitiveOffset(exint prim_index) const noexcept
251  {
252  return myPrimData[prim_index].myPrimOff;
253  }
254 
255  void clear() noexcept;
256 
257  SYS_FORCE_INLINE GA_Size numItems() const noexcept
258  {
259  return myNItems;
260  }
261 
262  struct Options
263  {
265  {
268  ALL_POINTS
269  };
270 
271  PointStyle points = NO_POINTS;
272 
273  const GA_Range *point_range = nullptr;
274  const GA_Range *prim_range = nullptr;
275  bool just_edges = false;
276 
277  /// If true, only triangles on the unshared surface of tetrahedra will
278  /// be added, not the solid tetrahedra themselves. findClosest will
279  /// find the closest surface point, and sendRay will only intersect the
280  /// surface.
281  ///
282  /// If false, only the solid tetrahedra will be added. findClosest will
283  /// find the current point if it's inside a tetrahedron, else the
284  /// closest surface point, and sendRay will intersect the current point
285  /// if it's inside a tetrahedron, else the first surface intersected.
286  bool tet_surface = false;
287  };
288 
289  /// NOTE: If options is different from what it was before, you must set
290  /// force_rebalance to true.
291  /// NOTE: With this signature, radscale scales the pscale attribute
292  /// if it's a valid attribute, else it's the point radius.
293  void init(const GEO_Detail &detail,
294  const GA_ROHandleT<VectorType> &P,
295  const Options &options,
296  const GA_ROHandleF &pscale,
297  const float radscale = 1.0f,
298  const bool force_rebalance=false,
299  SecondaryTreeMap *secondary_trees=nullptr,
300  SecondaryDetailMap *secondary_details=nullptr,
301  UT_Lock *secondary_lock=nullptr) noexcept;
302 
303  /// NOTE: With this signature, radius is the point radius.
304  void init(const GEO_Detail &detail,
306  const Options &options,
307  const float radius = 0.0f,
308  const bool force_rebalance=false) noexcept
309  {
310  init(detail, P, options, GA_ROHandleF(), radius, force_rebalance);
311  }
312 
313  SYS_FORCE_INLINE bool
314  isNGon(exint index) const noexcept
315  {
316  if (index < myOtherPrimStart)
317  return false;
318  exint prim_index = index - myTriStart;
319  OtherPrimType type = myPrimData[prim_index].myOtherType;
320  return type == OTHERPRIM_NGON_TRI || type == OTHERPRIM_NGON_QUAD;
321  }
322 
323  /// The UVWs returned for n-gons are for the sub-polygons,
324  /// so we need to compute the true UVWs from the positions.
325  UT_Vector3 findNGonUVW(exint index, const UT_Vector3 &position, const GEO_Detail &detail) const noexcept;
326 
327  SYS_FORCE_INLINE bool
328  isPacked(exint index) const noexcept
329  {
330  if (index < myOtherPrimStart)
331  return false;
332  exint prim_index = index - myTriStart;
333  OtherPrimType type = myPrimData[prim_index].myOtherType;
334  return type == OTHERPRIM_BVHUNIFORM || type == OTHERPRIM_BVHXLATESCALE || type == OTHERPRIM_BVHFULLXFORM;
335  }
336 
337 protected:
338  /// These are just used in the init function to change the decision about
339  /// clearing after some things have been initialized.
340  /// @{
341  void clearPrimDataAllocations() noexcept;
342  void clearSecondary() noexcept;
343  /// @}
344 
345  template<bool farthest,bool rm_backface,bool reverse,typename FUNCTOR>
346  bool intersectPrim(
347  uint index, const VectorType &origin, const VectorType &direction,
348  const VectorType &inverse_direction,
349  int &max_dir, VectorType &N0, VectorType &N1,
350  float &outer_tmax, float &outer_tmin, FUNCTOR &hit_info) const noexcept;
351  template<bool farthest>
352  void closestPrim(
353  uint index, const VectorType &origin, float &max_dist_squared,
354  exint &hit_index, UT_Vector3 &hit_uvw, VectorType &hit_position,
355  const UT_FixedVector<v4uf,NAXES> &vorigin,
356  UT_Array<exint> *nesting_array,
357  exint nesting_array_base) const noexcept;
358  template<bool normalize>
359  VectorType primGeometricNormal(const CommonHitInfo &hit_info) const noexcept;
360  SYS_FORCE_INLINE void primDerivs(const CommonHitInfo &hit_info, VectorType &dP_du, VectorType &dP_dv) const noexcept;
361  template<GA_AttributeOwner owner,typename T,typename DEST_T>
362  SYS_FORCE_INLINE bool primAttribute(const CommonHitInfo &hit_info, const GA_ROHandleT<T> &attrib, const GEO_Detail &detail, DEST_T &value) const noexcept;
363 
364  template<bool farthest,bool rm_backface,bool reverse,bool bidirectional=false,typename FUNCTOR>
365  static SYS_FORCE_INLINE bool intersectQuad(
366  const UT_Vector3 &origin,
367  const UT_Vector3 &inverse_direction,
368  const UT_Vector3 pos[4],
369  const int max_dir,
370  const UT_Vector3 &N0,
371  const UT_Vector3 &N1,
372  const PrimData &prim_data,
373  float &outer_tmin,
374  float &outer_tmax,
375  const uint index,
376  FUNCTOR &hit_info);
377 
378  template<bool farthest,bool rm_backface,bool reverse,bool bidirectional=false,typename FUNCTOR>
379  static SYS_FORCE_INLINE bool intersectTet(
380  const UT_Vector3 &origin,
381  const UT_Vector3 &inverse_direction,
382  const UT_Vector3 pos[4],
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>
390  static SYS_FORCE_INLINE bool triClosestPoint(
391  uint index,
392  const VectorType &origin,
393  const VectorType pos[3],
394  const PrimData &prim_data,
395  const UT_Vector3 &normal,
396  float &max_dist_squared,
397  exint &hit_index,
398  UT_Vector3 &hit_uvw,
399  UT_Vector3 &hit_position);
400  template<bool farthest>
401  static SYS_FORCE_INLINE bool quadClosestPoint(
402  uint index,
403  const VectorType &origin,
404  const UT_FixedVector<v4uf,3> &vorigin,
405  const VectorType pos[4],
406  const PrimData &prim_data,
407  float &max_dist_squared,
408  exint &hit_index,
409  UT_Vector3 &hit_uvw,
410  UT_Vector3 &hit_position);
411 
412  template<typename V3_ARRAY>
413  SYS_FORCE_INLINE static void addTriangleData(
414  GA_Offset *&tri_points,
415  const V3_ARRAY &positions,
416  const GA_ROHandleT<VectorType> &posattrib,
417  PrimData *primdata,
418  SingleBoxType *prim_box_start,
419  exint &tri_primnum,
420  GA_Offset primoff,
421  int data_int = -1,
422  float data_float = 0) noexcept;
423 
424  template<typename V3_ARRAY>
425  SYS_FORCE_INLINE static void addQuadData(
426  GA_Offset *&quad_points,
427  const V3_ARRAY &positions,
428  const GA_ROHandleT<VectorType> &posattrib,
429  PrimData *primdata,
430  SingleBoxType *prim_box_start,
431  exint &quad_primnum,
432  GA_Offset primoff,
433  int data_int = -1,
434  float data_float = 0) noexcept;
435 
436  SYS_FORCE_INLINE static void addRayPrimInfo(
437  PrimData &primdata,
438  GA_Offset primoff,
439  SingleBoxType &primbox,
440  GU_RayPrimInfo *rayprim,
441  exint &other_primnum,
442  const GEO_Detail &detail,
443  float w = 0) noexcept;
444 
445 public:
446  // NOTE: These are only public to work around a compile error.
447  using BVHBase::SingleHitAndNormalFunctor;
448  using BVHBase::AllHitsAndNormalsFunctor;
449 
450  template<bool farthest,bool rm_backface,bool reverse,bool bidirectional,typename FUNCTOR>
452 protected:
453 
455 };
456 
457 #if 0
458 class GU_API BVH_2D : public BVHBase<2, BVH_2D>
459 {
460  using Base = BVHBase<2, BVH_2D>;
461  friend class Base;
462  static constexpr uint NAXES = 2;
463 
464  static constexpr bool theHasPrimitives = true;
465 
466  struct PrimData
467  {
468  GA_Offset myPrimOff;
469  union {
470  void *myDataPtr;
471  uint myDataInts[2];
472  };
473  VectorType myN;
474  float myF;
475  };
476 
477  /// Point offsets for segments
478  UT_UniquePtr<GA_Offset[]> mySegmentPoints;
479 
480  GA_Size myOtherPrimStart;
481 
482  /// Additional data for primitives.
483  UT_UniquePtr<PrimData[]> myPrimData;
484 
485 public:
486  SYS_FORCE_INLINE BVH_2D() noexcept
487  : Base()
488  , mySegmentPoints(nullptr)
489  {}
490 
491  SYS_FORCE_INLINE GA_Offset primitiveOffset(exint prim_index) const noexcept
492  {
493  return myPrimData[prim_index].myPrimOff;
494  }
495 
496  SYS_FORCE_INLINE void clear() noexcept
497  {
498  Base::clear();
499  mySegmentPoints.reset();
500  myPrimData.reset();
501  }
502 
503  struct Options
504  {
505  enum PointStyle
506  {
507  NO_POINTS,
508  DISCONNECTED_POINTS,
509  ALL_POINTS
510  };
511 
512  PointStyle points = NO_POINTS;
513 
514  const GA_Range *point_range = nullptr;
515  const GA_Range *prim_range = nullptr;
516  bool just_edges = false;
517  };
518 
519  void init(const GA_Detail &detail,
520  const GA_ROHandleT<VectorType> &P,
521  const Options &options,
523  const bool force_rebalance=false) noexcept;
524 
525 protected:
526  template<bool farthest,bool rm_backface,bool reverse>
527  SYS_FORCE_INLINE bool intersectPrim(
528  uint index, const VectorType &origin, const VectorType &direction,
529  const VectorType &inverse_direction,
530  int &max_dir, VectorType &N0, VectorType &N1,
531  float &outer_tmax, float &outer_tmin, exint &hit_index, UT_Vector3 &hit_uvw) const noexcept;
532  template<bool farthest>
533  SYS_FORCE_INLINE void closestPrim(
534  uint index, const VectorType &origin, float &max_dist_squared,
535  exint &hit_index, UT_Vector3 &hit_uvw, VectorType &hit_position,
536  const UT_FixedVector<v4uf,NAXES> &vorigin,
537  UT_Array<exint> *nesting_array,
538  exint nesting_array_base) const noexcept;
539  template<bool normalize>
540  SYS_FORCE_INLINE VectorType primGeometricNormal(const CommonHitInfo &hit_info) const noexcept;
541  SYS_FORCE_INLINE void primDerivs(const CommonHitInfo &hit_info, VectorType &dP_du, VectorType &dP_dv) const noexcept;
542  template<GA_AttributeOwner owner,typename T,typename DEST_T>
543  SYS_FORCE_INLINE bool primAttribute(const CommonHitInfo &hit_info, const GA_ROHandleT<T> &attrib, const GEO_Detail &detail, DEST_T &value) const noexcept;
544 };
545 #endif
546 
547 } // GU namespace
548 
549 using GU_BVH = GU::BVH;
550 
*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:328
SYS_FORCE_INLINE bool isNGon(exint index) const noexcept
Definition: GU_BVH.h:314
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:250
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:245
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:230
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