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  GA_DataId topologyId() const { return myTopologyDataId; }
274  GA_DataId primlistId() const { return myPrimitiveListDataId; }
275 
276  struct Options
277  {
279  {
282  ALL_POINTS
283  };
284 
285  PointStyle points = NO_POINTS;
286 
287  const GA_Range *point_range = nullptr;
288  const GA_Range *prim_range = nullptr;
289  bool just_edges = false;
290 
291  /// If true, only triangles on the unshared surface of tetrahedra will
292  /// be added, not the solid tetrahedra themselves. findClosest will
293  /// find the closest surface point, and sendRay will only intersect the
294  /// surface.
295  ///
296  /// If false, only the solid tetrahedra will be added. findClosest will
297  /// find the current point if it's inside a tetrahedron, else the
298  /// closest surface point, and sendRay will intersect the current point
299  /// if it's inside a tetrahedron, else the first surface intersected.
300  bool tet_surface = false;
301  };
302 
303  /// NOTE: If options is different from what it was before, you must set
304  /// force_rebalance to true.
305  /// NOTE: With this signature, radscale scales the pscale attribute
306  /// if it's a valid attribute, else it's the point radius.
307  void init(const GEO_Detail &detail,
308  const GA_ROHandleT<VectorType> &P,
309  const Options &options,
310  const GA_ROHandleF &pscale,
311  const float radscale = 1.0f,
312  const bool force_rebalance=false,
313  SecondaryTreeMap *secondary_trees=nullptr,
314  SecondaryDetailMap *secondary_details=nullptr,
315  UT_Lock *secondary_lock=nullptr) noexcept;
316 
317  /// NOTE: With this signature, radius is the point radius.
318  void init(const GEO_Detail &detail,
320  const Options &options,
321  const float radius = 0.0f,
322  const bool force_rebalance=false) noexcept
323  {
324  init(detail, P, options, GA_ROHandleF(), radius, force_rebalance);
325  }
326 
327  SYS_FORCE_INLINE bool
328  isNGon(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_NGON_TRI || type == OTHERPRIM_NGON_QUAD;
335  }
336 
337  /// The UVWs returned for n-gons are for the sub-polygons,
338  /// so we need to compute the true UVWs from the positions.
339  UT_Vector3 findNGonUVW(exint index, const UT_Vector3 &position, const GEO_Detail &detail) const noexcept;
340 
341  SYS_FORCE_INLINE bool
342  isPacked(exint index) const noexcept
343  {
344  if (index < myOtherPrimStart)
345  return false;
346  exint prim_index = index - myTriStart;
347  OtherPrimType type = myPrimData[prim_index].myOtherType;
348  return type == OTHERPRIM_BVHUNIFORM || type == OTHERPRIM_BVHXLATESCALE || type == OTHERPRIM_BVHFULLXFORM;
349  }
350 
351 protected:
352  /// These are just used in the init function to change the decision about
353  /// clearing after some things have been initialized.
354  /// @{
355  void clearPrimDataAllocations() noexcept;
356  void clearSecondary() noexcept;
357  /// @}
358 
359  template<bool farthest,bool rm_backface,bool reverse,typename FUNCTOR>
360  bool intersectPrim(
361  uint index, const VectorType &origin, const VectorType &direction,
362  const VectorType &inverse_direction,
363  int &max_dir, VectorType &N0, VectorType &N1,
364  float &outer_tmax, float &outer_tmin, FUNCTOR &hit_info) const noexcept;
365  template<bool farthest>
366  void closestPrim(
367  uint index, const VectorType &origin, float &max_dist_squared,
368  exint &hit_index, UT_Vector3 &hit_uvw, VectorType &hit_position,
369  const UT_FixedVector<v4uf,NAXES> &vorigin,
370  UT_Array<exint> *nesting_array,
371  exint nesting_array_base) const noexcept;
372  template<bool normalize>
373  VectorType primGeometricNormal(const CommonHitInfo &hit_info) const noexcept;
374  SYS_FORCE_INLINE void primDerivs(const CommonHitInfo &hit_info, VectorType &dP_du, VectorType &dP_dv) const noexcept;
375  template<GA_AttributeOwner owner,typename T,typename DEST_T>
376  SYS_FORCE_INLINE bool primAttribute(const CommonHitInfo &hit_info, const GA_ROHandleT<T> &attrib, const GEO_Detail &detail, DEST_T &value) const noexcept;
377 
378  template<bool farthest,bool rm_backface,bool reverse,bool bidirectional=false,typename FUNCTOR>
379  static SYS_FORCE_INLINE bool intersectQuad(
380  const UT_Vector3 &origin,
381  const UT_Vector3 &inverse_direction,
382  const UT_Vector3 pos[4],
383  const int max_dir,
384  const UT_Vector3 &N0,
385  const UT_Vector3 &N1,
386  const PrimData &prim_data,
387  float &outer_tmin,
388  float &outer_tmax,
389  const uint index,
390  FUNCTOR &hit_info);
391 
392  template<bool farthest,bool rm_backface,bool reverse,bool bidirectional=false,typename FUNCTOR>
393  static SYS_FORCE_INLINE bool intersectTet(
394  const UT_Vector3 &origin,
395  const UT_Vector3 &inverse_direction,
396  const UT_Vector3 pos[4],
397  const PrimData &prim_data,
398  float &outer_tmin,
399  float &outer_tmax,
400  const uint index,
401  FUNCTOR &hit_info);
402 
403  template<bool farthest>
404  static SYS_FORCE_INLINE bool triClosestPoint(
405  uint index,
406  const VectorType &origin,
407  const VectorType pos[3],
408  const PrimData &prim_data,
409  const UT_Vector3 &normal,
410  float &max_dist_squared,
411  exint &hit_index,
412  UT_Vector3 &hit_uvw,
413  UT_Vector3 &hit_position);
414  template<bool farthest>
415  static SYS_FORCE_INLINE bool quadClosestPoint(
416  uint index,
417  const VectorType &origin,
418  const UT_FixedVector<v4uf,3> &vorigin,
419  const VectorType pos[4],
420  const PrimData &prim_data,
421  float &max_dist_squared,
422  exint &hit_index,
423  UT_Vector3 &hit_uvw,
424  UT_Vector3 &hit_position);
425 
426  template<typename V3_ARRAY>
427  SYS_FORCE_INLINE static void addTriangleData(
428  GA_Offset *&tri_points,
429  const V3_ARRAY &positions,
430  const GA_ROHandleT<VectorType> &posattrib,
431  PrimData *primdata,
432  SingleBoxType *prim_box_start,
433  exint &tri_primnum,
434  GA_Offset primoff,
435  int data_int = -1,
436  float data_float = 0) noexcept;
437 
438  template<typename V3_ARRAY>
439  SYS_FORCE_INLINE static void addQuadData(
440  GA_Offset *&quad_points,
441  const V3_ARRAY &positions,
442  const GA_ROHandleT<VectorType> &posattrib,
443  PrimData *primdata,
444  SingleBoxType *prim_box_start,
445  exint &quad_primnum,
446  GA_Offset primoff,
447  int data_int = -1,
448  float data_float = 0) noexcept;
449 
450  SYS_FORCE_INLINE static void addRayPrimInfo(
451  PrimData &primdata,
452  GA_Offset primoff,
453  SingleBoxType &primbox,
454  GU_RayPrimInfo *rayprim,
455  exint &other_primnum,
456  const GEO_Detail &detail,
457  float w = 0) noexcept;
458 
459 public:
460  // NOTE: These are only public to work around a compile error.
461  using BVHBase::SingleHitAndNormalFunctor;
462  using BVHBase::AllHitsAndNormalsFunctor;
463 
464  template<bool farthest,bool rm_backface,bool reverse,bool bidirectional,typename FUNCTOR>
466 protected:
467 
468  // We must specify that this is at global scope because we're inside a
469  // namepspace here.
470  friend class ::GU_RayHeightFieldInfo;
471 };
472 
473 #if 0
474 class GU_API BVH_2D : public BVHBase<2, BVH_2D>
475 {
476  using Base = BVHBase<2, BVH_2D>;
477  friend class Base;
478  static constexpr uint NAXES = 2;
479 
480  static constexpr bool theHasPrimitives = true;
481 
482  struct PrimData
483  {
484  GA_Offset myPrimOff;
485  union {
486  void *myDataPtr;
487  uint myDataInts[2];
488  };
489  VectorType myN;
490  float myF;
491  };
492 
493  /// Point offsets for segments
494  UT_UniquePtr<GA_Offset[]> mySegmentPoints;
495 
496  GA_Size myOtherPrimStart;
497 
498  /// Additional data for primitives.
499  UT_UniquePtr<PrimData[]> myPrimData;
500 
501 public:
502  SYS_FORCE_INLINE BVH_2D() noexcept
503  : Base()
504  , mySegmentPoints(nullptr)
505  {}
506 
507  SYS_FORCE_INLINE GA_Offset primitiveOffset(exint prim_index) const noexcept
508  {
509  return myPrimData[prim_index].myPrimOff;
510  }
511 
512  SYS_FORCE_INLINE void clear() noexcept
513  {
514  Base::clear();
515  mySegmentPoints.reset();
516  myPrimData.reset();
517  }
518 
519  struct Options
520  {
521  enum PointStyle
522  {
523  NO_POINTS,
524  DISCONNECTED_POINTS,
525  ALL_POINTS
526  };
527 
528  PointStyle points = NO_POINTS;
529 
530  const GA_Range *point_range = nullptr;
531  const GA_Range *prim_range = nullptr;
532  bool just_edges = false;
533  };
534 
535  void init(const GA_Detail &detail,
536  const GA_ROHandleT<VectorType> &P,
537  const Options &options,
539  const bool force_rebalance=false) noexcept;
540 
541 protected:
542  template<bool farthest,bool rm_backface,bool reverse>
543  SYS_FORCE_INLINE bool intersectPrim(
544  uint index, const VectorType &origin, const VectorType &direction,
545  const VectorType &inverse_direction,
546  int &max_dir, VectorType &N0, VectorType &N1,
547  float &outer_tmax, float &outer_tmin, exint &hit_index, UT_Vector3 &hit_uvw) const noexcept;
548  template<bool farthest>
549  SYS_FORCE_INLINE void closestPrim(
550  uint index, const VectorType &origin, float &max_dist_squared,
551  exint &hit_index, UT_Vector3 &hit_uvw, VectorType &hit_position,
552  const UT_FixedVector<v4uf,NAXES> &vorigin,
553  UT_Array<exint> *nesting_array,
554  exint nesting_array_base) const noexcept;
555  template<bool normalize>
556  SYS_FORCE_INLINE VectorType primGeometricNormal(const CommonHitInfo &hit_info) const noexcept;
557  SYS_FORCE_INLINE void primDerivs(const CommonHitInfo &hit_info, VectorType &dP_du, VectorType &dP_dv) const noexcept;
558  template<GA_AttributeOwner owner,typename T,typename DEST_T>
559  SYS_FORCE_INLINE bool primAttribute(const CommonHitInfo &hit_info, const GA_ROHandleT<T> &attrib, const GEO_Detail &detail, DEST_T &value) const noexcept;
560 };
561 #endif
562 
563 } // GU namespace
564 
565 using GU_BVH = GU::BVH;
566 
*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:685
GA_DataId topologyId() const
Definition: GU_BVH.h:273
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
int64 exint
Definition: SYS_Types.h:125
Definition: GU_BVH.h:33
void reverse(I begin, I end)
Definition: pugixml.cpp:7190
#define GA_INVALID_DATAID
Definition: GA_Types.h:686
exint GA_Size
Defines the bit width for index and offset types in GA.
Definition: GA_Types.h:233
SYS_FORCE_INLINE bool isPacked(exint index) const noexcept
Definition: GU_BVH.h:342
SYS_FORCE_INLINE bool isNGon(exint index) const noexcept
Definition: GU_BVH.h:328
A range of elements in an index-map.
Definition: GA_Range.h:42
std::unique_ptr< T, Deleter > UT_UniquePtr
A smart pointer for unique ownership of dynamically allocated objects.
Definition: UT_UniquePtr.h:33
GA_Size GA_Offset
Definition: GA_Types.h:639
GLclampf f
Definition: glew.h:3499
#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:1268
Definition: VM_SIMD.h:186
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
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
GA_DataId primlistId() const
Definition: GU_BVH.h:274
#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
unsigned int uint
Definition: SYS_Types.h:45
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:187