HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
SIM_ColliderBFA.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  */
7 
8 #ifndef __SIM_ColliderBFA_h__
9 #define __SIM_ColliderBFA_h__
10 
11 #include "SIM_API.h"
12 
13 #include "SIM_Collider.h"
14 #include "SIM_BVTree.h"
15 #include "SIM_Names.h"
16 #include "SIM_Isect.h"
17 #include "SIM_Utils.h"
18 
19 #include <GU/GU_DetailHandle.h>
20 
21 #include <UT/UT_IntArray.h>
22 #include <UT/UT_Vector3.h>
23 #include <UT/UT_Vector3Array.h>
24 
25 class SIM_BVTree;
27 class BV_LeafIterator;
28 class SIM_Geometry;
29 class simBVCallback;
30 
31 
32 // TODO: these structures have a lot of overlap with the new SIM_ISect
33 // structure. They should probably be eliminated in favour of SIM_ISect at
34 // some stage.
35 
36 
38 {
40  { }
41  sim4PointEvent(const SIM_Time &time, const UT_Vector3 &normal,
43  : myTime(time),
44  myNormal(normal),
45  myDistance(distance)
46  { }
47 
49  /// In a Face-Vertex event, the normal is from the face to the vertex.
50  /// Points on the face should move in -normal direction and the
51  /// vertex should move in the +normal direction to prevent collision.
52  /// In a Edge-Edge/Tri-Tri event, the normal points from prim0 to
53  /// prim1. Prim0 should move -normal and prim1 should move +normal
54  /// to prevent collision.
57 };
58 
60 {
62  { }
63  // Normals for this event point from the face to the vertex
64  simFaceVertexEvent(const SIM_Time &time, const UT_Vector3 &normal,
66  bool firstIsFace, int vid,
67  fpreal bary0, fpreal bary1)
68  : sim4PointEvent(time, normal, distance),
69  myFirstIsFace(firstIsFace),
70  myVid(vid)
71  {
72  myBary[0] = bary0;
73  myBary[1] = bary1;
74  }
75 
76  /// Retrieve a barycentric vector for the face's primitive
78  {
79  return UT_Vector3(myBary[0], myBary[1], 1-myBary[0]-myBary[1]);
80  }
81 
82  /// The face that's the "face" in this event is the first of the
83  /// two primitives in this event.
85  /// Vertex id
86  int myVid;
87  /// Barycentric position within the face
89 };
90 
92 {
94  { }
95  // Normals for this event point from edge0 to edge1
96  simEdgeEdgeEvent(const SIM_Time &time, const UT_Vector3 &normal,
98  int eid0, int eid1,
99  fpreal bary0, fpreal bary1)
100  : sim4PointEvent(time, normal, distance)
101  {
102  myEid[0] = eid0;
103  myEid[1] = eid1;
104  myBary[0] = bary0;
105  myBary[1] = bary1;
106  }
107 
108  /// id of edge within primitive. Vertices are eid and (eid+1)%nvertices
109  int myEid[2];
110  /// Parameter showing where point is within edge. 0 corresponds to vertex
111  /// e, and 1 corresponds to vertex (eid+1)%nvertices.
113 };
114 
115 
116 /// This class implements a cloth-cloth collider based on Bridson's
117 /// 2002 paper (BriFedAnd02). We use it for several types of deformable
118 /// collisions: cloth-cloth, cloth-hair and hair-hair. We also use it for
119 /// thin plate rigid body collisions.
120 /// This class can only be used for collision detection. The cloth subclass
121 /// does the Bridson/Fedkiw/Anderson collision response.
122 ///
123 /// For deformable objects, the input objects should be updated to the
124 /// end-of-step positions and velocities. This collider will proposes
125 /// changes to that end-of-step velocity which can then be used to obtain a
126 /// new end-of-step position. The start-of-step position is calculated by
127 /// assuming that explicit integration was used - i.e., by computing x - dt*v.
128 ///
129 /// This class does both self-collision and object/object collision. It
130 /// supports "point fusing," where two points in the same object (or one
131 /// point in each of the two objects) are fused together into a single
132 /// virtual point. (Typically, the user sets that up using a hard DOPs
133 /// constraint.) For collision purposes, those points are treated as a
134 /// single point - so, if two edges collide, but they share a virtual
135 /// point as an endpoint, the collision will be ignored.
136 ///
137 //
138 // TODO: handle non-manifold collisions. I'm not even sure what would
139 // happen if we tried to do them here. Some non-manifold structures are
140 // obviously impossible to do, but others are quite legitimate, like a
141 // T-shirt pocket.
143 {
144 public:
145  class simDetail;
146  class simPrimPairEvent;
147 
148  /// Collision detection for deformable bodies. These bodies:
149  /// 1) define velocity via a point attribute
150  /// 2) need their bounding volume trees updated every step.
152  SIM_IsectArray &collisions,
153  SIM_Object &object, SIM_Object &affector,
154  fpreal tolerance,
155  const SIM_Time &startTime,
156  const SIM_Time &endTime,
157  bool doRepulsion) const
158  {
159  getCollisions(collisions, object, affector,
160  tolerance, startTime, endTime,
161  true, doRepulsion,
162  NULL, NULL, NULL, NULL);
163  }
164 
165  /// Collision detection for rigid bodies. These bodies:
166  /// 1) define velocity via start/end transforms
167  /// 2) never need to update their bounding volume trees.
168  /// 3) need proxy triangulated geometry, since the source geometry may
169  /// not be triangles.
171  SIM_IsectArray &collisions,
172  SIM_Object &object, SIM_Object &affector,
173  fpreal tolerance,
174  const SIM_Time &startTime,
175  const SIM_Time &endTime,
176  const UT_DMatrix4 &startXformA,
177  const UT_DMatrix4 &startXformB,
178  const UT_DMatrix4 &endXformA,
179  const UT_DMatrix4 &endXformB) const
180  {
181  getCollisions(collisions, object, affector,
182  tolerance, startTime, endTime,
183  false, false,
184  &startXformA, &startXformB,
185  &endXformA, &endXformB);
186  }
187 
188 protected:
189  explicit SIM_ColliderBFA(const SIM_DataFactory *factory);
190  virtual ~SIM_ColliderBFA();
191 
193  getBVTreeType() const;
194 
195  /// This method should create a BV_LeafIterator class. This class will
196  /// iterate over the individual geometric entities to be used for OBB
197  /// intersection - in most cases, each leaf will contain a single
198  /// primitive from the geometry.
199  /// The time used to retrieve the geometry is determined by the
200  /// startPosOnly flag:
201  /// true: return the position at the start of the timestep - i.e.,
202  /// position at object - vel*timestep
203  /// false: return the positions at both the start and end of the
204  /// timestep.
205  /// The leaf iterator should return points in simulation (world) space,
206  /// not local object space.
207  virtual BV_LeafIterator
208  *createLeafIt(const SIM_Object &object,
209  const SIM_Time &timestep,
210  bool startPosOnly) const = 0;
211 
212  /// Given a leaf iterator and the id of a leaf, convert the leaf id to
213  /// a primitive id and (optionally) an edge id.
214  virtual void convertLeafToPrim(
215  const BV_LeafIterator &leafIt,
216  int leafId,
217  int &outPrimId, int &outEdgeId) const = 0;
218 
219  /// This method returns a radius to expand the leaf's geometry for
220  /// collision detection. For example, if the leaf's geometry is a
221  /// line segment, the expanded geometry used for collision detection
222  /// will be a cylinder with hemisphere caps.
223  virtual fpreal getLeafRadius(
224  const BV_LeafIterator &leafIt,
225  int leafId) const = 0;
226 
227  /// Test if this class generates events located at the *centre* of the
228  /// triangles/edges or at the *surface*. This choice usually depends on
229  /// the model of collision response.
230  virtual bool getEventsAtSurface() const;
231 
232  void retrieveGeometry(const SIM_Object &object,
233  GU_ConstDetailHandle &outGdh,
234  const GU_Detail *&outGdp,
235  UT_DMatrix4 *outEndTransform,
236  const SIM_TriangulatedGeometry **tgeo) const;
237 
238  /// Return true if a face and point share a point.
239  /// If the "fuse mapping" point attribute is present on both
240  /// GU_Details, it is used to determine if two points are fused;
241  /// If absent, sharing is only possible if the face and point belong to
242  /// the same GU_Detail - i.e., self-collision.
243  bool testFaceSharesPoint(const simDetail &sdpF,
244  int pidF0, int pidF1, int pidF2,
245  const simDetail &sdpV,
246  int pidV) const;
247  /// Return true if the two edges (defined by their endpoint ids) share
248  /// an endpoint.
249  /// If the "fuse mapping" point attribute is present on both
250  /// GU_Details, it is used to determine if two points are fused;
251  /// If absent, sharing is only possible if the face and point belong to
252  /// the same GU_Detail - i.e., self-collision.
253  bool testEdgesSharePoint(const simDetail &sdpA,
254  int pidA0, int pidA1,
255  const simDetail&sdpB,
256  int pidB0, int pidB1) const;
257  /// returns true iff tangling triangles should not be processed for
258  /// collision detection
259  /// The RBD collision detection uses this to allow objects that are
260  /// tangled at the start of the timestep to untangle without the
261  /// attempt to disentangle triggering a collision.
262  virtual bool doCheckTangle() const
263  { return false; }
264 
265  virtual void intersectPrims(simPrimPairEvent &event,
266  simDetail &sdpA, simDetail &sdpB,
267  fpreal tolerance, bool doRepulsion,
268  bool selfCollision) const;
269 private:
270 
271  /// The heart of this class. It does the actual collision detection.
272  void getCollisions(
273  SIM_IsectArray &collisions,
274  SIM_Object &object, SIM_Object &affector,
275  fpreal tolerance,
276  const SIM_Time &startTime,
277  const SIM_Time &endTime,
278  bool isDeformable,
279  bool doRepulsion,
280  const UT_DMatrix4 *startXformA,
281  const UT_DMatrix4 *startXformB,
282  const UT_DMatrix4 *endXformA,
283  const UT_DMatrix4 *endXformB) const;
284 
285  /// Test for intersection between a face and a point, and add events to
286  /// the given event parameter. The face and point are drawn from
287  // Face: firstIsFace ? sdp0 primitive event.myPrimId[0]
288  // : sdp1 primitive event.myPrimId[1]
289  // Vertex: firstIsFace ? sdp1 primitive event.myPrimId[1] vertex vid
290  // : sdp0 primitive event.myPrimId[0] vertex vid
291  /// If the searchInTimestep flag is set, the algorithm will search for
292  /// any events between the start and end time; otherwise, only the
293  /// positions at the start time will be considered.
294  int intersectFaceVertex(simPrimPairEvent &event,
295  simDetail &sdp0, simDetail &sdp1,
296  bool firstIsFace, int vid,
297  bool searchInTimestep,
298  fpreal tol) const;
299 
300  /// Test for intersection between two edges, and add events to the
301  /// given event parameter. The edges are drawn from:
302  /// A: sdp0 primitive event.myPrimId[0], edge eid0.
303  /// B: sdp1 primitive event.myPrimId[1], edge eid1.
304  /// If the searchInTimestep flag is set, the algorithm will search for
305  /// any events between the start and end time; otherwise, only the
306  /// positions at the start time will be considered.
307  int intersectEdgeEdge(simPrimPairEvent &event,
308  int eid0, simDetail &sdp0,
309  int eid1, simDetail &sdp1,
310  bool searchInTimestep,
311  fpreal tol) const;
312 
313  /// Test for intersection of two *static* triangles at the beginning
314  /// of the timestep (tangle), and add events to the given event parameters.
315  /// Returns true if no dynamic collision
316  /// detection/response (Edge/Edge,Face/Vertex) is to be performed.
317  bool intersectTriTri(simPrimPairEvent &event,
318  const simDetail &sdp0,
319  const simDetail &sdp1,
320  bool &searchInTimestep,
321  fpreal tol) const;
322 
323  /// Retrieve a BV tree from the given object, either creating it or
324  /// updating its extents using the given timestep.
325  /// If the "startPosOnly" flag is not set, the BV tree will include
326  /// leaf positions from both the start and end of the timestep;
327  /// otherwise, it will include only the start of the timestep.
328  SIM_BVTree *getBVTree(BV_LeafIterator* &leafIt,
329  SIM_Object &object,
330  const SIM_Time &timestep,
331  bool startPosOnly,
332  bool isDeformable) const;
333 
336 
337  friend class simBVCallback;
338 };
339 
340 class SIM_API SIM_ColliderBFA::simDetail
341 {
342 public:
343  /// The difference between rigid/deformable is the presence/absence of
344  /// tgeo data.
345  simDetail(int objectId,
346  const GU_Detail &gdp,
347  const SIM_TriangulatedGeometry *tgeo,
348  const UT_DMatrix4 &startXform,
349  const UT_DMatrix4 &endXform,
350  const SIM_Time &startTime,
351  const SIM_Time &endTime);
352 
353  int getObjectId() const
354  { return myObjectId; }
355  const GU_Detail &getGdp() const
356  { return myGdp; }
357  bool operator==(const simDetail &rhs) const
358  { return &myGdp == &rhs.myGdp; }
359 
360  const SIM_Time &getStartTime() const
361  { return myStartTime; }
362  const SIM_Time &getEndTime() const
363  { return myEndTime; }
364  const
366  { return myEndTime - myStartTime; }
367 
368  /// Get point id of vertex on a given face. Optimized for triangles.
369  int getTriPointId(int fid, int vid) const
370  {
371  UT_ASSERT_P(fid >= 0);
372  UT_ASSERT_P(vid >= 0 && vid < 3);
373  return myTriPointIds(fid*3 + vid);
374  }
375  /// Unoptimized version of getTriPointId for arbitrary primitives.
376  int getPrimPointId(int fid, int vid) const;
377  bool hasTriEdgeIds() const
378  {
379  return myTriEdgeIds.entries() > 0;
380  }
381  int getTriEdgeId(int fid, int vid) const
382  {
383  UT_ASSERT_P(fid >= 0);
384  UT_ASSERT_P(vid >= 0 && vid < 3);
385  return myTriEdgeIds(fid*3 + vid);
386  }
387  /// Retrieve the "simulation" point id (or "equation number")
388  /// associated with the given point. This allows for testing if points
389  /// from two different gdps are "fused" into a single point within the
390  /// simulation. It is stored as an attribute on the GU_Detail.
391  /// Collisions between fused points are ignored.
392  /// If the attribute is absent, fusing is disabled.
393  int getFusePointId(int pid) const
394  {
395  return myFusePointIds(pid);
396  }
397  bool hasFusePointIds() const
398  {
399  return myFusePointIds.entries() > 0;
400  }
401 
402  UT_Vector3 getDetailPointPos(int pid) const;
403 
404  const UT_Vector3&getPointVel(int pid) const
405  { return myVel(pid); }
406  float getPointMass(int pid) const;
407  const UT_Vector3&getPointStartPos(int pid) const
408  { return myStartPos(pid); }
409  const UT_Vector3&getPointEndPos(int pid) const
410  { return myEndPos(pid); }
411  UT_Vector3 getPointPos(int pid, const SIM_Time &time) const;
412  UT_Vector3 getTriBaryPos(int primId,
413  const UT_Vector3 &baryV3,
414  const SIM_Time &time) const;
415  UT_Vector3 getTriBaryVel(int primId,
416  const UT_Vector3 &baryV3) const;
417  fpreal getTriBaryMass(int primId,
418  const UT_Vector3 &baryV3) const;
419  /// Get a position of a point somewhere on the edge of a triangle.
420  UT_Vector3 getTriEdgePos(int primId, int eid, fpreal bary,
421  const SIM_Time &time) const;
422  /// Optimized variant of getTriEdgePos for non-triangular primitives.
423  UT_Vector3 getPrimEdgePos(int primId, int eid, fpreal bary,
424  const SIM_Time &time) const;
425  UT_Vector3 getTriStartBaryCenter(int primId) const;
426 
427  /// Flag that point pidB of sdpB has been tested against primIdA from
428  /// this simDetail. Returns true if it had already been tested before.
429  bool setPointChecked(int primIdA, const simDetail &sdpB,
430  int pidB);
431  /// Flag that edge (pidA0,pidA1) of this detail has been tested against
432  /// edge (pidB0,pidB1) of sdpB. Returns true if it had already been
433  /// tested before.
434  bool setEdgeChecked(int eidA, const simDetail &sdpB, int eidB);
435 
436 protected:
437  /// If mass attribute is missing (e.g., solid object), infinity is assumed.
438  /// TODO: change this?
440 
441 private:
442  int myObjectId;
443  const GU_Detail &myGdp;
444  SIM_EdgeData myEdgeData;
445  /// This array contains a lookup for the edge ids (in myEdgeData) for a
446  /// given primitive.
447  /// eid = myTriEdgeIds[primId*3 + i]
448  /// defines the index into myEdgeData for edge i of primitive primId.
449  UT_IntArray myTriEdgeIds;
450  const SIM_TriangulatedGeometry *myTgeo;
451  UT_DMatrix4 myStartXform, myEndXform;
452  SIM_Time myStartTime;
453  SIM_Time myEndTime;
454 
455  /// We precompute these because they're used repeatedly by different
456  /// primitives+different times within the substep, and they're
457  /// expensive to compute (due to transformation required, etc.)
458  // @{
459  UT_Vector3Array myStartPos;
460  UT_Vector3Array myEndPos;
461  UT_Vector3Array myVel;
462  UT_IntArray myTriPointIds;
463  UT_IntArray myFusePointIds;
464  // @}
465 
466  /// Entry "i" of this array is a list of the point ids that have already
467  /// been collided with primitive #i.
468  UT_Array<UT_IntArray> myPointsChecked;
469 
470  /// Entry "i" of this array is a list of the edges that have already
471  /// been collided with edge #i.
472  UT_Array<UT_IntArray> myEdgesChecked;
473 };
474 
475 /// A single potential-collision event involving a pair of primitives.
476 class SIM_API SIM_ColliderBFA::simPrimPairEvent
477 {
478 public:
479  simPrimPairEvent(int primId0, int primId1,
480  int edgeId0, int edgeId1,
481  fpreal radius0, fpreal radius1,
482  int &adjacent);
483 
484  int myPrimId[2];
485  int myEdgeId[2];
486  fpreal myRadii[2];
487  /// A flag to indicate that the two primitives are adjacent
488  /// (i.e., share one or more vertices)
493 };
494 
495 
496 #endif
UT_Array< simEdgeEdgeEvent > myEdgeEdgeEvents
#define DECLARE_STANDARD_GETCASTTOTYPE()
Definition: SIM_DataUtils.h:45
#define DECLARE_CLASSNAME(DataClass, SuperClass)
Definition: SIM_DataUtils.h:20
bool hasTriEdgeIds() const
simEdgeEdgeEvent(const SIM_Time &time, const UT_Vector3 &normal, fpreal distance, int eid0, int eid1, fpreal bary0, fpreal bary1)
A single potential-collision event involving a pair of primitives.
UT_Vector3T< float > UT_Vector3
void getCollisionsDeformable(SIM_IsectArray &collisions, SIM_Object &object, SIM_Object &affector, fpreal tolerance, const SIM_Time &startTime, const SIM_Time &endTime, bool doRepulsion) const
const UT_Vector3 & getPointStartPos(int pid) const
GA_ROHandleF myAttMass
UT_Vector3 myNormal
const GU_Detail & getGdp() const
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:101
const UT_Vector3 & getPointEndPos(int pid) const
struct _cl_event * event
Definition: glcorearb.h:2960
const UT_Vector3 & getPointVel(int pid) const
int myEid[2]
id of edge within primitive. Vertices are eid and (eid+1)nvertices
int getTriPointId(int fid, int vid) const
Get point id of vertex on a given face. Optimized for triangles.
simFaceVertexEvent(const SIM_Time &time, const UT_Vector3 &normal, fpreal distance, bool firstIsFace, int vid, fpreal bary0, fpreal bary1)
T distance(const UT_Vector4T< T > &v1, const UT_Vector4T< T > &v2)
Definition: UT_Vector4.h:634
const SIM_Time & getStartTime() const
int getObjectId() const
virtual bool doCheckTangle() const
int getFusePointId(int pid) const
const SIM_Time getTimestep() const
bool hasFusePointIds() const
double fpreal
Definition: SYS_Types.h:263
UT_Array< simFaceVertexEvent > myFaceVertexEvents
UT_Vector3 getBaryV3() const
Retrieve a barycentric vector for the face's primitive.
#define SIM_API
Definition: SIM_API.h:10
sim4PointEvent(const SIM_Time &time, const UT_Vector3 &normal, fpreal distance)
const SIM_Time & getEndTime() const
int getTriEdgeId(int fid, int vid) const
UT_Array< SIM_Isect > myTriTriEvents
fpreal myBary[2]
Barycentric position within the face.
bool operator==(const simDetail &rhs) const
int myVid
Vertex id.
void getCollisionsRigid(SIM_IsectArray &collisions, SIM_Object &object, SIM_Object &affector, fpreal tolerance, const SIM_Time &startTime, const SIM_Time &endTime, const UT_DMatrix4 &startXformA, const UT_DMatrix4 &startXformB, const UT_DMatrix4 &endXformA, const UT_DMatrix4 &endXformB) const