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