1 /********************************************************************************
2 * ReactPhysics3D physics library, http://www.reactphysics3d.com                 *
3 * Copyright (c) 2010-2020 Daniel Chappuis                                       *
4 *********************************************************************************
5 *                                                                               *
6 * This software is provided 'as-is', without any express or implied warranty.   *
7 * In no event will the authors be held liable for any damages arising from the  *
8 * use of this software.                                                         *
9 *                                                                               *
10 * Permission is granted to anyone to use this software for any purpose,         *
11 * including commercial applications, and to alter it and redistribute it        *
12 * freely, subject to the following restrictions:                                *
13 *                                                                               *
14 * 1. The origin of this software must not be misrepresented; you must not claim *
15 *    that you wrote the original software. If you use this software in a        *
16 *    product, an acknowledgment in the product documentation would be           *
17 *    appreciated but is not required.                                           *
18 *                                                                               *
19 * 2. Altered source versions must be plainly marked as such, and must not be    *
20 *    misrepresented as being the original software.                             *
21 *                                                                               *
22 * 3. This notice may not be removed or altered from any source distribution.    *
23 *                                                                               *
24 ********************************************************************************/
25 
26 #ifndef REACTPHYSICS3D_OVERLAPPING_PAIR_H
27 #define	REACTPHYSICS3D_OVERLAPPING_PAIR_H
28 
29 // Libraries
30 #include <reactphysics3d/collision/Collider.h>
31 #include <reactphysics3d/containers/Map.h>
32 #include <reactphysics3d/containers/Pair.h>
33 #include <reactphysics3d/containers/Set.h>
34 #include <reactphysics3d/containers/containers_common.h>
35 #include <reactphysics3d/utils/Profiler.h>
36 #include <reactphysics3d/components/ColliderComponents.h>
37 #include <reactphysics3d/components/CollisionBodyComponents.h>
38 #include <reactphysics3d/components/RigidBodyComponents.h>
39 #include <cstddef>
40 
41 /// ReactPhysics3D namespace
42 namespace reactphysics3d {
43 
44 // Declarations
45 struct NarrowPhaseInfoBatch;
46 enum class NarrowPhaseAlgorithmType;
47 class CollisionShape;
48 class CollisionDispatch;
49 
50 // Structure LastFrameCollisionInfo
51 /**
52  * This structure contains collision info about the last frame.
53  * This is used for temporal coherence between frames.
54  */
55 struct LastFrameCollisionInfo {
56 
57     /// True if we have information about the previous frame
58     bool isValid;
59 
60     /// True if the frame info is obsolete (the collision shape are not overlapping in middle phase)
61     bool isObsolete;
62 
63     /// True if the two shapes were colliding in the previous frame
64     bool wasColliding;
65 
66     /// True if we were using GJK algorithm to check for collision in the previous frame
67     bool wasUsingGJK;
68 
69     /// True if we were using SAT algorithm to check for collision in the previous frame
70     bool wasUsingSAT;
71 
72     // ----- GJK Algorithm -----
73 
74     /// Previous separating axis
75     Vector3 gjkSeparatingAxis;
76 
77     // SAT Algorithm
78     bool satIsAxisFacePolyhedron1;
79     bool satIsAxisFacePolyhedron2;
80     uint satMinAxisFaceIndex;
81     uint satMinEdge1Index;
82     uint satMinEdge2Index;
83 
84     /// Constructor
LastFrameCollisionInfoLastFrameCollisionInfo85     LastFrameCollisionInfo() {
86 
87         isValid = false;
88         isObsolete = false;
89         wasColliding = false;
90         wasUsingSAT = false;
91         wasUsingGJK = false;
92 
93         gjkSeparatingAxis = Vector3(0, 1, 0);
94     }
95 };
96 
97 // Class OverlappingPairs
98 /**
99  * This class contains pairs of two colliders that are overlapping
100  * during the broad-phase collision detection. A pair is created when
101  * the two colliders start to overlap and is destroyed when they do not
102  * overlap anymore. Each contains a contact manifold that
103  * store all the contact points between the two bodies.
104  */
105 class OverlappingPairs {
106 
107     private:
108 
109         // -------------------- Constants -------------------- //
110 
111 
112         /// Number of pairs to allocated at the beginning
113         const uint32 INIT_NB_ALLOCATED_PAIRS = 10;
114 
115         // -------------------- Attributes -------------------- //
116 
117         /// Persistent memory allocator
118         MemoryAllocator& mPersistentAllocator;
119 
120         /// Memory allocator used to allocated memory for the ContactManifoldInfo and ContactPointInfo
121         // TODO : Do we need to keep this ?
122         MemoryAllocator& mTempMemoryAllocator;
123 
124         /// Current number of components
125         uint64 mNbPairs;
126 
127         /// Index in the array of the first convex vs concave pair
128         uint64 mConcavePairsStartIndex;
129 
130         /// Size (in bytes) of a single pair
131         size_t mPairDataSize;
132 
133         /// Number of allocated pairs
134         uint64 mNbAllocatedPairs;
135 
136         /// Allocated memory for all the data of the pairs
137         void* mBuffer;
138 
139         /// Map a pair id to the internal array index
140         Map<uint64, uint64> mMapPairIdToPairIndex;
141 
142         /// Ids of the convex vs convex pairs
143         uint64* mPairIds;
144 
145         /// Array with the broad-phase Ids of the first shape
146         int32* mPairBroadPhaseId1;
147 
148         /// Array with the broad-phase Ids of the second shape
149         int32* mPairBroadPhaseId2;
150 
151         /// Array of Entity of the first collider of the convex vs convex pairs
152         Entity* mColliders1;
153 
154         /// Array of Entity of the second collider of the convex vs convex pairs
155         Entity* mColliders2;
156 
157         /// Temporal coherence collision data for each overlapping collision shapes of this pair.
158         /// Temporal coherence data store collision information about the last frame.
159         /// If two convex shapes overlap, we have a single collision data but if one shape is concave,
160         /// we might have collision data for several overlapping triangles. The key in the map is the
161         /// shape Ids of the two collision shapes.
162         Map<uint64, LastFrameCollisionInfo*>* mLastFrameCollisionInfos;
163 
164         /// True if we need to test if the convex vs convex overlapping pairs of shapes still overlap
165         bool* mNeedToTestOverlap;
166 
167         /// True if the overlapping pair is active (at least one body of the pair is active and not static)
168         bool* mIsActive;
169 
170         /// Array with the pointer to the narrow-phase algorithm for each overlapping pair
171         NarrowPhaseAlgorithmType* mNarrowPhaseAlgorithmType;
172 
173         /// True if the first shape of the pair is convex
174         bool* mIsShape1Convex;
175 
176         /// True if the colliders of the overlapping pair were colliding in the previous frame
177         bool* mCollidingInPreviousFrame;
178 
179         /// True if the colliders of the overlapping pair are colliding in the current frame
180         bool* mCollidingInCurrentFrame;
181 
182         /// Reference to the colliders components
183         ColliderComponents& mColliderComponents;
184 
185         /// Reference to the collision body components
186         CollisionBodyComponents& mCollisionBodyComponents;
187 
188         /// Reference to the rigid bodies components
189         RigidBodyComponents& mRigidBodyComponents;
190 
191         /// Reference to the set of bodies that cannot collide with each others
192         Set<bodypair>& mNoCollisionPairs;
193 
194         /// Reference to the collision dispatch
195         CollisionDispatch& mCollisionDispatch;
196 
197 #ifdef IS_RP3D_PROFILING_ENABLED
198 
199         /// Pointer to the profiler
200         Profiler* mProfiler;
201 
202 #endif
203 
204         // -------------------- Methods -------------------- //
205 
206         /// Allocate memory for a given number of pairs
207         void allocate(uint64 nbPairsToAllocate);
208 
209         /// Compute the index where we need to insert the new pair
210         uint64 prepareAddPair(bool isConvexVsConvex);
211 
212         /// Destroy a pair at a given index
213         void destroyPair(uint64 index);
214 
215         // Move a pair from a source to a destination index in the pairs array
216         void movePairToIndex(uint64 srcIndex, uint64 destIndex);
217 
218         /// Swap two pairs in the array
219         void swapPairs(uint64 index1, uint64 index2);
220 
221     public:
222 
223         // -------------------- Methods -------------------- //
224 
225         /// Constructor
226         OverlappingPairs(MemoryAllocator& persistentMemoryAllocator, MemoryAllocator& temporaryMemoryAllocator,
227                          ColliderComponents& colliderComponents, CollisionBodyComponents& collisionBodyComponents,
228                          RigidBodyComponents& rigidBodyComponents, Set<bodypair>& noCollisionPairs,
229                          CollisionDispatch& collisionDispatch);
230 
231         /// Destructor
232         ~OverlappingPairs();
233 
234         /// Deleted copy-constructor
235         OverlappingPairs(const OverlappingPairs& pair) = delete;
236 
237         /// Deleted assignment operator
238         OverlappingPairs& operator=(const OverlappingPairs& pair) = delete;
239 
240         /// Add an overlapping pair
241         uint64 addPair(Collider* shape1, Collider* shape2);
242 
243         /// Remove a component at a given index
244         void removePair(uint64 pairId);
245 
246         /// Return the number of pairs
247         uint64 getNbPairs() const;
248 
249         /// Return the number of convex vs convex pairs
250         uint64 getNbConvexVsConvexPairs() const;
251 
252         /// Return the number of convex vs concave pairs
253         uint64 getNbConvexVsConcavePairs() const;
254 
255         /// Return the starting index of the convex vs concave pairs
256         uint64 getConvexVsConcavePairsStartIndex() const;
257 
258         /// Return the entity of the first collider
259         Entity getCollider1(uint64 pairId) const;
260 
261         /// Return the entity of the second collider
262         Entity getCollider2(uint64 pairId) const;
263 
264         /// Notify if a given pair is active or not
265         void setIsPairActive(uint64 pairId, bool isActive);
266 
267         /// Return the index of a given overlapping pair in the internal array
268         uint64 getPairIndex(uint64 pairId) const;
269 
270         /// Return the last frame collision info
271         LastFrameCollisionInfo* getLastFrameCollisionInfo(uint64, uint64 shapesId);
272 
273         /// Return a reference to the temporary memory allocator
274         MemoryAllocator& getTemporaryAllocator();
275 
276         /// Add a new last frame collision info if it does not exist for the given shapes already
277         LastFrameCollisionInfo* addLastFrameInfoIfNecessary(uint64 pairIndex, uint32 shapeId1, uint32 shapeId2);
278 
279         /// Update whether a given overlapping pair is active or not
280         void updateOverlappingPairIsActive(uint64 pairId);
281 
282         /// Delete all the obsolete last frame collision info
283         void clearObsoleteLastFrameCollisionInfos();
284 
285         /// Set the collidingInPreviousFrame value with the collidinginCurrentFrame value for each pair
286         void updateCollidingInPreviousFrame();
287 
288         /// Return the pair of bodies index of the pair
289         static bodypair computeBodiesIndexPair(Entity body1Entity, Entity body2Entity);
290 
291         /// Set if we need to test a given pair for overlap
292         void setNeedToTestOverlap(uint64 pairId, bool needToTestOverlap);
293 
294         /// Return true if the two colliders of the pair were already colliding the previous frame
295         bool getCollidingInPreviousFrame(uint64 pairId) const;
296 
297         /// Set to true if the two colliders of the pair were already colliding the previous frame
298         void setCollidingInPreviousFrame(uint64 pairId, bool wereCollidingInPreviousFrame);
299 
300 #ifdef IS_RP3D_PROFILING_ENABLED
301 
302         /// Set the profiler
303         void setProfiler(Profiler* profiler);
304 
305 #endif
306 
307         // -------------------- Friendship -------------------- //
308 
309         friend class PhysicsWorld;
310         friend class CollisionDetectionSystem;
311 };
312 
313 // Return the entity of the first collider
getCollider1(uint64 pairId)314 inline Entity OverlappingPairs::getCollider1(uint64 pairId) const {
315     assert(mMapPairIdToPairIndex.containsKey(pairId));
316     assert(mMapPairIdToPairIndex[pairId] < mNbPairs);
317     return mColliders1[mMapPairIdToPairIndex[pairId]];
318 }
319 
320 // Return the entity of the second collider
getCollider2(uint64 pairId)321 inline Entity OverlappingPairs::getCollider2(uint64 pairId) const {
322     assert(mMapPairIdToPairIndex.containsKey(pairId));
323     assert(mMapPairIdToPairIndex[pairId] < mNbPairs);
324     return mColliders2[mMapPairIdToPairIndex[pairId]];
325 }
326 
327 // Notify if a given pair is active or not
setIsPairActive(uint64 pairId,bool isActive)328 inline void OverlappingPairs::setIsPairActive(uint64 pairId, bool isActive) {
329 
330     assert(mMapPairIdToPairIndex.containsKey(pairId));
331     assert(mMapPairIdToPairIndex[pairId] < mNbPairs);
332     mIsActive[mMapPairIdToPairIndex[pairId]] = isActive;
333 }
334 
335 // Return the index of a given overlapping pair in the internal array
getPairIndex(uint64 pairId)336 inline uint64 OverlappingPairs::getPairIndex(uint64 pairId) const {
337     assert(mMapPairIdToPairIndex.containsKey(pairId));
338     return mMapPairIdToPairIndex[pairId];
339 }
340 
341 // Return the last frame collision info for a given shape id or nullptr if none is found
getLastFrameCollisionInfo(uint64 pairId,uint64 shapesId)342 inline LastFrameCollisionInfo* OverlappingPairs::getLastFrameCollisionInfo(uint64 pairId, uint64 shapesId) {
343 
344     assert(mMapPairIdToPairIndex.containsKey(pairId));
345     const uint64 index = mMapPairIdToPairIndex[pairId];
346     assert(index < mNbPairs);
347 
348     Map<uint64, LastFrameCollisionInfo*>::Iterator it = mLastFrameCollisionInfos[index].find(shapesId);
349     if (it != mLastFrameCollisionInfos[index].end()) {
350         return it->second;
351     }
352 
353     return nullptr;
354 }
355 
356 // Return the pair of bodies index
computeBodiesIndexPair(Entity body1Entity,Entity body2Entity)357 inline bodypair OverlappingPairs::computeBodiesIndexPair(Entity body1Entity, Entity body2Entity) {
358 
359     // Construct the pair of body index
360     bodypair indexPair = body1Entity.id < body2Entity.id ?
361                                  bodypair(body1Entity, body2Entity) :
362                                  bodypair(body2Entity, body1Entity);
363     assert(indexPair.first != indexPair.second);
364     return indexPair;
365 }
366 
367 // Return the number of pairs
getNbPairs()368 inline uint64 OverlappingPairs::getNbPairs() const {
369     return mNbPairs;
370 }
371 
372 // Return the number of convex vs convex pairs
getNbConvexVsConvexPairs()373 inline uint64 OverlappingPairs::getNbConvexVsConvexPairs() const {
374    return mConcavePairsStartIndex;
375 }
376 
377 // Return the number of convex vs concave pairs
getNbConvexVsConcavePairs()378 inline uint64 OverlappingPairs::getNbConvexVsConcavePairs() const {
379    return mNbPairs - mConcavePairsStartIndex;
380 }
381 
382 // Return the starting index of the convex vs concave pairs
getConvexVsConcavePairsStartIndex()383 inline uint64 OverlappingPairs::getConvexVsConcavePairsStartIndex() const {
384    return mConcavePairsStartIndex;
385 }
386 
387 // Return a reference to the temporary memory allocator
getTemporaryAllocator()388 inline MemoryAllocator& OverlappingPairs::getTemporaryAllocator() {
389     return mTempMemoryAllocator;
390 }
391 
392 // Set if we need to test a given pair for overlap
setNeedToTestOverlap(uint64 pairId,bool needToTestOverlap)393 inline void OverlappingPairs::setNeedToTestOverlap(uint64 pairId, bool needToTestOverlap) {
394     assert(mMapPairIdToPairIndex.containsKey(pairId));
395     mNeedToTestOverlap[mMapPairIdToPairIndex[pairId]] = needToTestOverlap;
396 }
397 
398 // Return true if the two colliders of the pair were already colliding the previous frame
getCollidingInPreviousFrame(uint64 pairId)399 inline bool OverlappingPairs::getCollidingInPreviousFrame(uint64 pairId) const {
400     assert(mMapPairIdToPairIndex.containsKey(pairId));
401     return mCollidingInPreviousFrame[mMapPairIdToPairIndex[pairId]];
402 }
403 
404 // Set to true if the two colliders of the pair were already colliding the previous frame
setCollidingInPreviousFrame(uint64 pairId,bool wereCollidingInPreviousFrame)405 inline void OverlappingPairs::setCollidingInPreviousFrame(uint64 pairId, bool wereCollidingInPreviousFrame) {
406     assert(mMapPairIdToPairIndex.containsKey(pairId));
407     mCollidingInPreviousFrame[mMapPairIdToPairIndex[pairId]] = wereCollidingInPreviousFrame;
408 }
409 
410 #ifdef IS_RP3D_PROFILING_ENABLED
411 
412 // Set the profiler
setProfiler(Profiler * profiler)413 inline void OverlappingPairs::setProfiler(Profiler* profiler) {
414     mProfiler = profiler;
415 }
416 
417 #endif
418 }
419 
420 #endif
421 
422