HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
GU_RayIntersect.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 library (C++)
7  *
8  * COMMENTS: Ray intersection for GU library (not necessarily as fast as
9  * RAY library)
10  *
11  */
12 
13 #ifndef __GU_RayIntersect_h__
14 #define __GU_RayIntersect_h__
15 
16 #include "GU_API.h"
17 #include <GEO/GEO_PrimitiveP.h>
18 #include <UT/UT_Defines.h>
19 #include <UT/UT_Array.h>
20 #include <UT/UT_UniquePtr.h>
21 #include <UT/UT_ValArray.h>
22 #include <UT/UT_Vector3.h>
24 #include <TS/TS_Expression.h>
25 
26 class GA_PrimitiveGroup;
27 class GA_Range;
28 namespace GU { class BVH; }
29 class GU_Detail;
30 class guRayTree;
31 class GEO_Primitive;
32 class GU_RayPrimInfo;
33 class GU_IsectCurveSet;
34 
36 {
40 };
41 
43 {
44 public:
46  {
47  mySerial = 1;
48  }
49 
51  {
52  }
53 
54  void bumpSerial()
55  {
56  mySerial++;
57  if (mySerial < 0)
58  {
59  // We wrapped, reset.
60  myList.constant(0);
61  mySerial = 1;
62  }
63  }
64 
65  int getSerial() const
66  {
67  return mySerial;
68  }
69 
70  // Tests if the given index has been seen in this pass. If not,
71  // returns true as it is the first time.
72  // In any case, the primitive will now be marked up to date.
73  bool firstTimeWithReset(int idx)
74  {
75  if (myList(idx) == mySerial)
76  return false;
77 
78  myList(idx) = mySerial;
79  return true;
80  }
81  // Returns if this has not been reset on this pass, but does
82  // not affect its state.
83  bool firstTime(int idx) const
84  {
85  if (myList(idx) == mySerial)
86  return false;
87  return true;
88  }
89  // Resets this idx to be marked as seen.
90  void reset(int idx)
91  {
92  myList(idx) = mySerial;
93  }
94 
96  {
97  if (myList.entries() != length)
98  {
99  myList.entries(length);
100  myList.constant(0);
101  }
102  }
103 
104  int64 getMemoryUsage(bool inclusive) const
105  {
106  int64 mem = inclusive ? sizeof(*this) : 0;
107  mem += myList.getMemoryUsage(false);
108  return mem;
109  }
110 
111 private:
112  UT_IntArray myList;
113  int mySerial;
114 };
115 
117 {
118 public:
119  int operator==(const GU_RayInfoHit &x) const
120  {
121  return (t==x.t && u == x.u && v == x.v && w == x.w && d2 == x.d2 && prim == x.prim);
122  }
123  float t, u, v, w, d2; // Intersection point. May add cache here.
125 };
126 
128 {
129 public:
131  {
132  valid = false;
133  priminfo = 0;
134  data = 0;
135  }
136 
138  void *data;
139  bool valid;
140 };
141 
143 {
144 public:
145  GU_RayInfo(float max = 1E18f, float min=0.0f,
146  GU_RayFindType type = GU_FIND_CLOSEST, float tol = 1e-1F)
147  {
148  myHitList = 0;
149  myCurveSet = 0;
150  myTtol = 1E-2f; // Points closer than this in "t" will not
151  // be double counted.
152  myIgnoreTrims = true; // Do we pay attention to trimmed out regions?
153  myUseAlgebraic = false; // Use algebraic pruning where available?
154  myIgnoreMeta = false; // Include metaballs.
155  myExpandPolygon = false;
156  myTValid = false;
157  myDomainTol = 1E-2f;
158  mySteps = 100;
159  myMaxHits = 0;
160  myTimeChange = 0.0F;
161  myUnitTimeOffset = 0.0F;
162  myUnitTimeUpperTol = 0.0F;
163  mySerialList = 0;
164  init(max, min, type, tol);
165  }
166  ~GU_RayInfo();
167 
168  GU_RaySerial *getSerialList() const { return mySerialList; }
169  void setSerialList(GU_RaySerial *seriallist)
170  {
171  mySerialList = seriallist;
172  }
173  bool firstTime(int serialidx) const
174  { return mySerialList->firstTime(serialidx); }
175  bool firstTimeWithReset(int serialidx) const
176  { return mySerialList->firstTimeWithReset(serialidx); }
177  void resetSerial(int serialidx)
178  { mySerialList->reset(serialidx); }
179 
180  void setFindType(GU_RayFindType type);
181  void init(float max = 1E18f, float min=0.0f,
183  float tolerance = 1e-1F, int ignoretrims=1,
184  int usealgebraic = 0);
185 
186  bool testHit(float t)
187  {
188  return (t >= myTmin && t <= myTmax);
189  }
190 
191  bool insertHit(float nt, float nu, float nv, float nw,
192  float nd2, GEO_ConstPrimitiveP prim);
193 
194  void addCurveSet(GU_IsectCurveSet &curveset);
195 
196  void invalidateCache() { myCache.valid = false; }
197  bool isCacheValid() { return( myCache.valid ); }
198 
199  GU_RayFindType getFindType() const { return myFindType; }
200 
201  void reset();
202 
205  float myTmin;
206  float myTmax;
207  float myT;
208  float myU, myV, myW; // Hit position on primitive
209  float myD2; // Squared error.
210  float myTol; // Max error to consider a hit.
211  float myTtol; // min dist on ray between
212  // two points
213  float myDomainTol; // Tolerance in domain
214  int mySteps; // Marching size
215  bool myIgnoreTrims; // Pay attention to trim loops?
216  bool myUseAlgebraic;// Use algebraic pruning?
217  bool myExpandPolygon; // If true, you can have
218  // hits outside of 0,1 on quads.
219  // Prevents leaks with non-planar.
220  bool myIgnoreMeta; // Ignore metaballs.
221  bool myTValid; // Is myT set to a legit hit?
222  int myMaxHits; // Number of hits to stop
223  // searching at, if 0, is
224  // infinite.
225  GU_RayInfoCache myCache; // Last successful hit.
227  GU_IsectCurveSet *myCurveSet; // Set of isect curves.
228 
229  float myTimeChange; //Only for moving collision
230  float myUnitTimeOffset;//Only for moving collision
231  float myUnitTimeUpperTol; //Only for moving collision
232 private:
233  GU_RayFindType myFindType; // Only way to set is thru init
234  GU_RaySerial *mySerialList; // Cache of serial numbers
235 };
236 
237 // This is the version of hitinfo used for minimum finding.
238 // It is similar, but sufficiently different to have its own
239 // structure. In particular, more u/v values are needed and
240 // caching is not.
241 // NB: All distances are actually distance squareds.
242 // As soon as a distance smaller than dmin is found, the minimum
243 // finder will terminate with that value. This allows early
244 // exit with collison detection.
246 {
247 public:
248  GU_MinInfo(float max = 1E18F, float min=1e-14F, int naccurate = 1)
249  {
250  dmin = min;
251  dmax = max;
252  accurate = naccurate;
253  u1 = v1 = w1 = u2 = v2 = w2 = 0.0f;
254  prim = 0;
255  mySerialList = 0;
256  }
257 
258  GU_RaySerial *getSerialList() const { return mySerialList; }
259  void setSerialList(GU_RaySerial *seriallist)
260  {
261  mySerialList = seriallist;
262  }
263  bool firstTime(int serialidx) const
264  { return mySerialList->firstTime(serialidx); }
265  bool firstTimeWithReset(int serialidx) const
266  { return mySerialList->firstTimeWithReset(serialidx); }
267  void resetSerial(int serialidx)
268  { mySerialList->reset(serialidx); }
269 
270  void init(float max = 1E18F, float min=1e-14F)
271  {
272  dmin = min;
273  dmax = max;
274  }
275 
276  bool addMin(float dist)
277  {
278  if (dist >= dmax)
279  return false;
280 
281  // Only closest makes sense with minimum
282  dmax = dist;
283  return true;
284  }
285 
286  void insertMin(float nd2, float nu1, float nv1, float nw1,
287  float nu2, float nv2, float nw2,
289  {
290  d = nd2; // Recall: Distance squared.
291  u1 = nu1;
292  v1 = nv1;
293  w1 = nw1;
294  u2 = nu2;
295  v2 = nv2;
296  w2 = nw2;
297  prim = p;
298  }
299 
300  void swapOrder()
301  {
302  float tmp;
303 
304  tmp = u1;
305  u1 = u2;
306  u2 = tmp;
307 
308  tmp = v1;
309  v1 = v2;
310  v2 = tmp;
311 
312  tmp = w1;
313  w1 = w2;
314  w2 = tmp;
315  }
316 
317  int operator==( const GU_MinInfo &other ) const
318  {
319  return( dmin == other.dmin
320  && dmax == other.dmax
321  && d == other.d
322  && u1 == other.u1
323  && v1 == other.v1
324  && w1 == other.w1
325  && u2 == other.u2
326  && v2 == other.v2
327  && w2 == other.w2
328  && accurate == other.accurate
329  && prim == other.prim );
330  }
331 
332 public:
333  float dmin, dmax; // Minimum & maximum squared distances.
334  float d; // Current squared distance.
335  float u1, v1, w1; // Current minimum on source.
336  float u2, v2, w2; // Current minimum on dest.
337  int accurate; // Do we polish sol'n?
338  GEO_ConstPrimitiveP prim; // What we are close to.
339 
340 private:
341  GU_RaySerial *mySerialList;
342 };
343 
345 {
346 public:
348  virtual ~GU_ProximityHelper() {}
349 
350  virtual float getMaxRadius( int prim_num ) const = 0;
351  virtual float getRadius( int prim_num,
352  float u_real, float v_real ) const = 0;
353 };
354 
356 {
357 public:
358  GU_RayIntersect();
359 
360  // Flag 'picking' should be set to 1. When set to 0, curves and
361  // surfaces will be polygonalized. Polygonalized curves have
362  // a different parameterization than the original curve, so the
363  // u coordinates will no longer be valid if picking == 0.
364  // Flag 'polylines' indicates to build polylines instead of polygons.
365  // Normally, any closed polygon is treated as a surface. If polyline
366  // is set to 1, all polygons are treated as wires.
367  // Flag 'harden' indicates to build hard geometry - ie: the cached values
368  // will not update with those of the GDP. This is usually a good thing,
369  // except it requires more memory.
370  // This also means that NURBs and Bezier surfaces will be changed
371  // into meshes, which may result in a faster intersect.
372  // Flag 'usevisibility' indicates that it will look for a 3d visibility
373  // group. If one is found, primitives will only be used if they
374  // are in that group.
375  // Flag 'solidtet' will create solid tetrahedrons for a better minimum
376  // distance behaviour.
377  GU_RayIntersect(const GU_Detail *gdp, const GA_PrimitiveGroup *group = nullptr,
378  bool picking = false, bool polyline = false, bool harden = false,
379  bool usevisibility = false,
380  bool solidtet = false);
381 
382  // assume picking for a single primitive
383  GU_RayIntersect(const GU_Detail *gdp, const GEO_Primitive *prim,
384  bool polyline = false, bool solidtet=false);
385 
386  // This version of the constructor is used for a special case intersector
387  // against moving geometry. Currently it only supports triangles.
388  // Unlike the standard rays that are cast against the geometry, when
389  // using this version of the intersector, the ray has to have a "speed"
390  // associated with it.
391  GU_RayIntersect(const GU_Detail *gdp0, const GU_Detail *gdp1);
392 
393  // This version of the constructor is like the one that takes a group
394  // except the group is from a different gdp that has the same topology
395  // (ie. prim counts are the sames). Note that if usevisibility is true,
396  // then the visibility from the gdp is used (NOT limit_gdp).
397  GU_RayIntersect(const GU_Detail *gdp,
398  const GU_Detail *limit_gdp,
399  const GA_PrimitiveGroup *vis_group,
400  bool picking = false, bool polyline = false, bool harden = false,
401  bool usevisibility = false);
402 
403  ~GU_RayIntersect();
404 
405  // Returns whether the supplied detail can be used with the deforming
406  // geometry code (i.e. it is all triangles).
407  static bool validForDeformingGeometry(const GU_Detail *gdp0,
408  const GU_Detail *gdp1);
409 
410  void init(const GU_Detail *gdp, const GA_PrimitiveGroup *group = nullptr,
411  bool picking = false, bool polyline = false, bool harden = false,
412  bool usevisibility = false, bool solidtet = false);
413  void init(const GU_Detail *gdp, const GEO_Primitive *prim,
414  bool polyline = false, bool solidtet = false);
415  void init(const GU_Detail *gdp,
416  const GU_Detail *limit_gdp,
417  const GA_PrimitiveGroup *limit_group,
418  bool picking = false, bool polyline = false, bool harden = false,
419  bool usevisibility = false);
420 
421  bool init() const { return myTree != 0; }
422 
423  // Reset to the default constructed state.
424  void clear();
425 
426  // Returns whether this instance is up-to-date for the specified
427  // detail or whether it needs to be rebuilt.
428  bool validForDetail(const GU_Detail *gdp) const;
429 
430  const GU_Detail *
431  detail() const { return myGdp; }
432 
433  // Send a ray into the gdp between tmin & tmax. Returns 0 if miss,
434  // or the number of hits.
435  // If hit, the information for the hit is returned in
436  // the hitinfo.
437  // Returns -1 if intersection was interrupted.
438  int sendRay(const UT_Vector3 &org, const UT_Vector3 &dir,
439  GU_RayInfo &hitinfo) const;
440  // Find minimum distance between point and gdp between tmin and tmax.
441  // Note t = square of distance between point & primitive, so tmin
442  // and tmax should be squares of the distance as desired.
443  int minimumPoint(const UT_Vector3 &p, GU_MinInfo &mininfo,
444  const GEO_Primitive *prim = 0) const;
445  // Find all primitives in the gdp that are within a given radius of the
446  // given point. Returns a list with u,v values sorted by primitive id in
447  // hit_list.
448  // If helper is non-NULL, then instead of using radius, we use it to
449  // determine our radius.
450  int proximityPoint( UT_Array<GU_MinInfo> &hit_list,
451  const UT_Vector3 &p,
452  bool normalize_weights,
453  const GU_ProximityHelper *helper,
454  float radius = 0.0f ) const;
455 
456  // Intersects with a rayprimitive, used internally primarily:
457  // Note it operates in opposite direction of intersectCaches!
458  int intersectPrim(const GEO_Detail &prim_geo,
459  GU_RayPrimInfo &prim, GU_RayInfo &hitinfo);
460 
461  // Intersect two raycaches of primitives. Returns number of hits
462  // found. Only defined for some primitive types (Curves and surfaces)
463  int intersectCaches(GU_RayIntersect &intersect,
464  GU_RayInfo &hitinfo);
465  // Find minimum between two raycaches of primitives. Returns 1 if
466  // minimum found. t value is square of distance between them, as
467  // is d2.
468  int minimumCaches(const GU_RayIntersect &intersect,
469  GU_MinInfo &mininfo) const;
470 
471  int isInside(const UT_Vector3 &pt, bool ignoretrim = true,
472  float tol=0.1) const;
473 
474  int isInsideWinding(const UT_Vector3 &pt, bool ignoretrim = true,
475  float tol = 0.1) const;
476 
477  /// Returns true if there are no primitives to intersect against.
478  bool isEmpty() const;
479 
480  // Gets this thread's serial list.
481  GU_RaySerial *getSerialList() const;
482 
483  /// Report approximate memory usage.
484  int64 getMemoryUsage(bool inclusive) const;
485 
486  // GU_RayIntersect usually returns real coordinates, not unit coordinates.
487  // Usually you want unit coordinates so evaluateInteriorPoint can
488  // be used. This handles the conversion. Usually it is a case
489  // of realToUnitPair, but there are a few exceptions such as open
490  // polylines.
491  static void fixBrokenUVs(const GEO_Primitive *prim, float &u, float &v);
492 
493 protected:
494  void destroyTrees();
495 
496 private:
497  void initDetailTracking(const GU_Detail *gdp);
498  void initMetaExpr(const GU_Detail *gdp,
499  const GA_Range &primrange);
500 
501  int determineState(const UT_Vector3 &pt,
502  GEO_ConstPrimitiveP &prim,
503  int n, uint seed = 1, bool ignoretrim = true,
504  float tol = 0.1) const;
505  int determineStateWinding(const UT_Vector3 &pt,
506  GEO_ConstPrimitiveP &prim,
507  int n, uint seed = 1, bool ignoretrim = true,
508  float tol = 0.1) const;
509 
510 private:
511  const GU_Detail *myGdp;
512 
513  guRayTree *myTree;
514  mutable UT_ThreadSpecificValue<GU_RaySerial *> mySerialList;
515 
516  /// NOTE: We can't have this as a direct member instead of a pointer,
517  /// because including GU_BVH.h without including GEO_BVHImpl.h
518  /// seems to cause compile errors, due to the compiler trying to
519  /// instantiate all of the outlined functions from GEO::BVH,
520  /// even though they aren't called in GU_BVH.h.
521  /// I tried to solve this with "extern template" statements,
522  /// but the compiler seemed to ignore that.
523  UT_UniquePtr<GU::BVH> myBVH;
524 
525  /// This is only used for density() calls.
526  TS_MetaExpressionPtr myMetaExpr;
527 
528  // Keep track of some details about the detail we were initialized
529  // with so users can query whether we're still valid.
530  int myDetailUniqueId;
531  int myDetailCacheCount;
532 };
533 
534 #endif
GA_API const UT_StringHolder dist
void init(float max=1E18F, float min=1e-14F)
bool firstTimeWithReset(int serialidx) const
GU_RayPrimInfo * priminfo
void resetSerial(int serialidx)
int getSerial() const
const GLdouble * v
Definition: glcorearb.h:836
GU_RaySerial * getSerialList() const
bool firstTime(int idx) const
UT_Vector3 myNml
GEO_ConstPrimitiveP myPrim
GEO_ConstPrimitiveP prim
GLfloat GLfloat GLfloat v2
Definition: glcorearb.h:817
void setSerialList(GU_RaySerial *seriallist)
void insertMin(float nd2, float nu1, float nv1, float nw1, float nu2, float nv2, float nw2, GEO_ConstPrimitiveP p)
void reset(int idx)
A range of elements in an index-map.
Definition: GA_Range.h:42
long long int64
Definition: SYS_Types.h:107
GU_IsectCurveSet * myCurveSet
GLdouble n
Definition: glcorearb.h:2007
bool addMin(float dist)
GLfloat f
Definition: glcorearb.h:1925
GU_RayInfo(float max=1E18f, float min=0.0f, GU_RayFindType type=GU_FIND_CLOSEST, float tol=1e-1F)
bool intersect(const Line3< T > &line, const Vec3< T > &v0, const Vec3< T > &v1, const Vec3< T > &v2, Vec3< T > &pt, Vec3< T > &barycentric, bool &front)
float myUnitTimeOffset
GU_RayInfoCache myCache
const std::enable_if<!VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:133
int64 getMemoryUsage(bool inclusive) const
bool isCacheValid()
void swapOrder()
bool firstTime(int serialidx) const
float myUnitTimeUpperTol
GEO_ConstPrimitiveP prim
GU_MinInfo(float max=1E18F, float min=1e-14F, int naccurate=1)
#define GU_API
Definition: GU_API.h:12
GLboolean * data
Definition: glcorearb.h:130
GU_RayFindType
GU_RayFindType getFindType() const
float myTimeChange
bool init() const
unsigned int uint
Definition: SYS_Types.h:40
bool testHit(float t)
GU_RaySerial * getSerialList() const
int operator==(const GU_RayInfoHit &x) const
bool myExpandPolygon
virtual ~GU_ProximityHelper()
bool firstTime(int serialidx) const
void setSerialList(GU_RaySerial *seriallist)
void invalidateCache()
void resetSerial(int serialidx)
GLint GLenum GLint x
Definition: glcorearb.h:408
GLfloat GLfloat v1
Definition: glcorearb.h:816
GLint GLint GLsizei GLint GLenum GLenum type
Definition: glcorearb.h:107
GLubyte GLubyte GLubyte GLubyte w
Definition: glcorearb.h:856
int operator==(const GU_MinInfo &other) const
const GU_Detail * detail() const
const std::enable_if<!VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:129
bool firstTimeWithReset(int serialidx) const
UT_Array< GU_RayInfoHit > * myHitList
bool firstTimeWithReset(int idx)
void ensureListExists(int length)
GLuint GLsizei GLsizei * length
Definition: glcorearb.h:794