dali-physics/third-party/bullet3/src/BulletCollision/BroadphaseCollision/btOverlappingPairCache.h

   1 /*
   2 Bullet Continuous Collision Detection and Physics Library
   3 Copyright (c) 2003-2006 Erwin Coumans  https://bulletphysics.org
   4
   5 This software is provided 'as-is', without any express or implied warranty.
   6 In no event will the authors be held liable for any damages arising from the use of this software.
   7 Permission is granted to anyone to use this software for any purpose,
   8 including commercial applications, and to alter it and redistribute it freely,
   9 subject to the following restrictions:
  10
  11 1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
  12 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
  13 3. This notice may not be removed or altered from any source distribution.
  14 */
  15
  16 #ifndef BT_OVERLAPPING_PAIR_CACHE_H
  17 #define BT_OVERLAPPING_PAIR_CACHE_H
  18
  19 #include "btBroadphaseInterface.h"
  20 #include "btBroadphaseProxy.h"
  21 #include "btOverlappingPairCallback.h"
  22
  23 #include "LinearMath/btAlignedObjectArray.h"
  24 class btDispatcher;
  25
  26 typedef btAlignedObjectArray<btBroadphasePair> btBroadphasePairArray;
  27
  28 struct btOverlapCallback
  29 {
  30         virtual ~btOverlapCallback()
  31         {
  32         }
  33         //return true for deletion of the pair
  34         virtual bool processOverlap(btBroadphasePair& pair) = 0;
  35 };
  36
  37 struct btOverlapFilterCallback
  38 {
  39         virtual ~btOverlapFilterCallback()
  40         {
  41         }
  42         // return true when pairs need collision
  43         virtual bool needBroadphaseCollision(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1) const = 0;
  44 };
  45
  46 const int BT_NULL_PAIR = 0xffffffff;
  47
  48 ///The btOverlappingPairCache provides an interface for overlapping pair management (add, remove, storage), used by the btBroadphaseInterface broadphases.
  49 ///The btHashedOverlappingPairCache and btSortedOverlappingPairCache classes are two implementations.
  50 class btOverlappingPairCache : public btOverlappingPairCallback
  51 {
  52 public:
  53         virtual ~btOverlappingPairCache() {}  // this is needed so we can get to the derived class destructor
  54
  55         virtual btBroadphasePair* getOverlappingPairArrayPtr() = 0;
  56
  57         virtual const btBroadphasePair* getOverlappingPairArrayPtr() const = 0;
  58
  59         virtual btBroadphasePairArray& getOverlappingPairArray() = 0;
  60
  61         virtual void cleanOverlappingPair(btBroadphasePair& pair, btDispatcher* dispatcher) = 0;
  62
  63         virtual int getNumOverlappingPairs() const = 0;
  64         virtual bool needsBroadphaseCollision(btBroadphaseProxy * proxy0, btBroadphaseProxy * proxy1) const = 0;
  65         virtual btOverlapFilterCallback* getOverlapFilterCallback() = 0;
  66         virtual void cleanProxyFromPairs(btBroadphaseProxy* proxy, btDispatcher* dispatcher) = 0;
  67
  68         virtual void setOverlapFilterCallback(btOverlapFilterCallback* callback) = 0;
  69
  70         virtual void processAllOverlappingPairs(btOverlapCallback*, btDispatcher* dispatcher) = 0;
  71
  72         virtual void processAllOverlappingPairs(btOverlapCallback* callback, btDispatcher* dispatcher, const struct btDispatcherInfo& /*dispatchInfo*/)
  73         {
  74                 processAllOverlappingPairs(callback, dispatcher);
  75         }
  76         virtual btBroadphasePair* findPair(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1) = 0;
  77
  78         virtual bool hasDeferredRemoval() = 0;
  79
  80         virtual void setInternalGhostPairCallback(btOverlappingPairCallback* ghostPairCallback) = 0;
  81
  82         virtual void sortOverlappingPairs(btDispatcher* dispatcher) = 0;
  83 };
  84
  85 /// Hash-space based Pair Cache, thanks to Erin Catto, Box2D, http://www.box2d.org, and Pierre Terdiman, Codercorner, http://codercorner.com
  86
  87 ATTRIBUTE_ALIGNED16(class)
  88 btHashedOverlappingPairCache : public btOverlappingPairCache
  89 {
  90         btBroadphasePairArray m_overlappingPairArray;
  91         btOverlapFilterCallback* m_overlapFilterCallback;
  92
  93 protected:
  94         btAlignedObjectArray<int> m_hashTable;
  95         btAlignedObjectArray<int> m_next;
  96         btOverlappingPairCallback* m_ghostPairCallback;
  97
  98 public:
  99         BT_DECLARE_ALIGNED_ALLOCATOR();
 100
 101         btHashedOverlappingPairCache();
 102         virtual ~btHashedOverlappingPairCache();
 103
 104         void removeOverlappingPairsContainingProxy(btBroadphaseProxy * proxy, btDispatcher * dispatcher);
 105
 106         virtual void* removeOverlappingPair(btBroadphaseProxy * proxy0, btBroadphaseProxy * proxy1, btDispatcher * dispatcher);
 107
 108         SIMD_FORCE_INLINE bool needsBroadphaseCollision(btBroadphaseProxy * proxy0, btBroadphaseProxy * proxy1) const
 109         {
 110                 if (m_overlapFilterCallback)
 111                         return m_overlapFilterCallback->needBroadphaseCollision(proxy0, proxy1);
 112
 113                 bool collides = (proxy0->m_collisionFilterGroup & proxy1->m_collisionFilterMask) != 0;
 114                 collides = collides && (proxy1->m_collisionFilterGroup & proxy0->m_collisionFilterMask);
 115
 116                 return collides;
 117         }
 118
 119         // Add a pair and return the new pair. If the pair already exists,
 120         // no new pair is created and the old one is returned.
 121         virtual btBroadphasePair* addOverlappingPair(btBroadphaseProxy * proxy0, btBroadphaseProxy * proxy1)
 122         {
 123                 if (!needsBroadphaseCollision(proxy0, proxy1))
 124                         return 0;
 125
 126                 return internalAddPair(proxy0, proxy1);
 127         }
 128
 129         void cleanProxyFromPairs(btBroadphaseProxy * proxy, btDispatcher * dispatcher);
 130
 131         virtual void processAllOverlappingPairs(btOverlapCallback*, btDispatcher * dispatcher);
 132
 133         virtual void processAllOverlappingPairs(btOverlapCallback * callback, btDispatcher * dispatcher, const struct btDispatcherInfo& dispatchInfo);
 134
 135         virtual btBroadphasePair* getOverlappingPairArrayPtr()
 136         {
 137                 return &m_overlappingPairArray[0];
 138         }
 139
 140         const btBroadphasePair* getOverlappingPairArrayPtr() const
 141         {
 142                 return &m_overlappingPairArray[0];
 143         }
 144
 145         btBroadphasePairArray& getOverlappingPairArray()
 146         {
 147                 return m_overlappingPairArray;
 148         }
 149
 150         const btBroadphasePairArray& getOverlappingPairArray() const
 151         {
 152                 return m_overlappingPairArray;
 153         }
 154
 155         void cleanOverlappingPair(btBroadphasePair & pair, btDispatcher * dispatcher);
 156
 157         btBroadphasePair* findPair(btBroadphaseProxy * proxy0, btBroadphaseProxy * proxy1);
 158
 159         int GetCount() const { return m_overlappingPairArray.size(); }
 160         //      btBroadphasePair* GetPairs() { return m_pairs; }
 161
 162         btOverlapFilterCallback* getOverlapFilterCallback()
 163         {
 164                 return m_overlapFilterCallback;
 165         }
 166
 167         void setOverlapFilterCallback(btOverlapFilterCallback * callback)
 168         {
 169                 m_overlapFilterCallback = callback;
 170         }
 171
 172         int getNumOverlappingPairs() const
 173         {
 174                 return m_overlappingPairArray.size();
 175         }
 176
 177 private:
 178         btBroadphasePair* internalAddPair(btBroadphaseProxy * proxy0, btBroadphaseProxy * proxy1);
 179
 180         void growTables();
 181
 182         SIMD_FORCE_INLINE bool equalsPair(const btBroadphasePair& pair, int proxyId1, int proxyId2)
 183         {
 184                 return pair.m_pProxy0->getUid() == proxyId1 && pair.m_pProxy1->getUid() == proxyId2;
 185         }
 186
 187         /*
 188         // Thomas Wang's hash, see: http://www.concentric.net/~Ttwang/tech/inthash.htm
 189         // This assumes proxyId1 and proxyId2 are 16-bit.
 190         SIMD_FORCE_INLINE int getHash(int proxyId1, int proxyId2)
 191         {
 192                 int key = (proxyId2 << 16) | proxyId1;
 193                 key = ~key + (key << 15);
 194                 key = key ^ (key >> 12);
 195                 key = key + (key << 2);
 196                 key = key ^ (key >> 4);
 197                 key = key * 2057;
 198                 key = key ^ (key >> 16);
 199                 return key;
 200         }
 201         */
 202
 203         SIMD_FORCE_INLINE unsigned int getHash(unsigned int proxyId1, unsigned int proxyId2)
 204         {
 205                 unsigned int key = proxyId1 | (proxyId2 << 16);
 206                 // Thomas Wang's hash
 207
 208                 key += ~(key << 15);
 209                 key ^= (key >> 10);
 210                 key += (key << 3);
 211                 key ^= (key >> 6);
 212                 key += ~(key << 11);
 213                 key ^= (key >> 16);
 214                 return key;
 215         }
 216
 217         SIMD_FORCE_INLINE btBroadphasePair* internalFindPair(btBroadphaseProxy * proxy0, btBroadphaseProxy * proxy1, int hash)
 218         {
 219                 int proxyId1 = proxy0->getUid();
 220                 int proxyId2 = proxy1->getUid();
 221 #if 0  // wrong, 'equalsPair' use unsorted uids, copy-past devil striked again. Nat.
 222                 if (proxyId1 > proxyId2)
 223                         btSwap(proxyId1, proxyId2);
 224 #endif
 225
 226                 int index = m_hashTable[hash];
 227
 228                 while (index != BT_NULL_PAIR && equalsPair(m_overlappingPairArray[index], proxyId1, proxyId2) == false)
 229                 {
 230                         index = m_next[index];
 231                 }
 232
 233                 if (index == BT_NULL_PAIR)
 234                 {
 235                         return NULL;
 236                 }
 237
 238                 btAssert(index < m_overlappingPairArray.size());
 239
 240                 return &m_overlappingPairArray[index];
 241         }
 242
 243         virtual bool hasDeferredRemoval()
 244         {
 245                 return false;
 246         }
 247
 248         virtual void setInternalGhostPairCallback(btOverlappingPairCallback * ghostPairCallback)
 249         {
 250                 m_ghostPairCallback = ghostPairCallback;
 251         }
 252
 253         virtual void sortOverlappingPairs(btDispatcher * dispatcher);
 254 };
 255
 256 ///btSortedOverlappingPairCache maintains the objects with overlapping AABB
 257 ///Typically managed by the Broadphase, Axis3Sweep or btSimpleBroadphase
 258 class btSortedOverlappingPairCache : public btOverlappingPairCache
 259 {
 260 protected:
 261         //avoid brute-force finding all the time
 262         btBroadphasePairArray m_overlappingPairArray;
 263
 264         //during the dispatch, check that user doesn't destroy/create proxy
 265         bool m_blockedForChanges;
 266
 267         ///by default, do the removal during the pair traversal
 268         bool m_hasDeferredRemoval;
 269
 270         //if set, use the callback instead of the built in filter in needBroadphaseCollision
 271         btOverlapFilterCallback* m_overlapFilterCallback;
 272
 273         btOverlappingPairCallback* m_ghostPairCallback;
 274
 275 public:
 276         btSortedOverlappingPairCache();
 277         virtual ~btSortedOverlappingPairCache();
 278
 279         virtual void processAllOverlappingPairs(btOverlapCallback*, btDispatcher* dispatcher);
 280
 281         void* removeOverlappingPair(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1, btDispatcher* dispatcher);
 282
 283         void cleanOverlappingPair(btBroadphasePair& pair, btDispatcher* dispatcher);
 284
 285         btBroadphasePair* addOverlappingPair(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1);
 286
 287         btBroadphasePair* findPair(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1);
 288
 289         void cleanProxyFromPairs(btBroadphaseProxy* proxy, btDispatcher* dispatcher);
 290
 291         void removeOverlappingPairsContainingProxy(btBroadphaseProxy* proxy, btDispatcher* dispatcher);
 292
 293         inline bool needsBroadphaseCollision(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1) const
 294         {
 295                 if (m_overlapFilterCallback)
 296                         return m_overlapFilterCallback->needBroadphaseCollision(proxy0, proxy1);
 297
 298                 bool collides = (proxy0->m_collisionFilterGroup & proxy1->m_collisionFilterMask) != 0;
 299                 collides = collides && (proxy1->m_collisionFilterGroup & proxy0->m_collisionFilterMask);
 300
 301                 return collides;
 302         }
 303
 304         btBroadphasePairArray& getOverlappingPairArray()
 305         {
 306                 return m_overlappingPairArray;
 307         }
 308
 309         const btBroadphasePairArray& getOverlappingPairArray() const
 310         {
 311                 return m_overlappingPairArray;
 312         }
 313
 314         btBroadphasePair* getOverlappingPairArrayPtr()
 315         {
 316                 return &m_overlappingPairArray[0];
 317         }
 318
 319         const btBroadphasePair* getOverlappingPairArrayPtr() const
 320         {
 321                 return &m_overlappingPairArray[0];
 322         }
 323
 324         int getNumOverlappingPairs() const
 325         {
 326                 return m_overlappingPairArray.size();
 327         }
 328
 329         btOverlapFilterCallback* getOverlapFilterCallback()
 330         {
 331                 return m_overlapFilterCallback;
 332         }
 333
 334         void setOverlapFilterCallback(btOverlapFilterCallback* callback)
 335         {
 336                 m_overlapFilterCallback = callback;
 337         }
 338
 339         virtual bool hasDeferredRemoval()
 340         {
 341                 return m_hasDeferredRemoval;
 342         }
 343
 344         virtual void setInternalGhostPairCallback(btOverlappingPairCallback* ghostPairCallback)
 345         {
 346                 m_ghostPairCallback = ghostPairCallback;
 347         }
 348
 349         virtual void sortOverlappingPairs(btDispatcher* dispatcher);
 350 };
 351
 352 ///btNullPairCache skips add/removal of overlapping pairs. Userful for benchmarking and unit testing.
 353 class btNullPairCache : public btOverlappingPairCache
 354 {
 355         btBroadphasePairArray m_overlappingPairArray;
 356
 357 public:
 358         virtual btBroadphasePair* getOverlappingPairArrayPtr()
 359         {
 360                 return &m_overlappingPairArray[0];
 361         }
 362         const btBroadphasePair* getOverlappingPairArrayPtr() const
 363         {
 364                 return &m_overlappingPairArray[0];
 365         }
 366         btBroadphasePairArray& getOverlappingPairArray()
 367         {
 368                 return m_overlappingPairArray;
 369         }
 370
 371         virtual void cleanOverlappingPair(btBroadphasePair& /*pair*/, btDispatcher* /*dispatcher*/)
 372         {
 373         }
 374
 375         virtual int getNumOverlappingPairs() const
 376         {
 377                 return 0;
 378         }
 379
 380         virtual void cleanProxyFromPairs(btBroadphaseProxy* /*proxy*/, btDispatcher* /*dispatcher*/)
 381         {
 382         }
 383
 384         bool needsBroadphaseCollision(btBroadphaseProxy*, btBroadphaseProxy*) const
 385         {
 386                 return true;
 387         }
 388         btOverlapFilterCallback* getOverlapFilterCallback()
 389         {
 390                 return 0;
 391         }
 392         virtual void setOverlapFilterCallback(btOverlapFilterCallback* /*callback*/)
 393         {
 394         }
 395
 396         virtual void processAllOverlappingPairs(btOverlapCallback*, btDispatcher* /*dispatcher*/)
 397         {
 398         }
 399
 400         virtual btBroadphasePair* findPair(btBroadphaseProxy* /*proxy0*/, btBroadphaseProxy* /*proxy1*/)
 401         {
 402                 return 0;
 403         }
 404
 405         virtual bool hasDeferredRemoval()
 406         {
 407                 return true;
 408         }
 409
 410         virtual void setInternalGhostPairCallback(btOverlappingPairCallback* /* ghostPairCallback */)
 411         {
 412         }
 413
 414         virtual btBroadphasePair* addOverlappingPair(btBroadphaseProxy* /*proxy0*/, btBroadphaseProxy* /*proxy1*/)
 415         {
 416                 return 0;
 417         }
 418
 419         virtual void* removeOverlappingPair(btBroadphaseProxy* /*proxy0*/, btBroadphaseProxy* /*proxy1*/, btDispatcher* /*dispatcher*/)
 420         {
 421                 return 0;
 422         }
 423
 424         virtual void removeOverlappingPairsContainingProxy(btBroadphaseProxy* /*proxy0*/, btDispatcher* /*dispatcher*/)
 425         {
 426         }
 427
 428         virtual void sortOverlappingPairs(btDispatcher* dispatcher)
 429         {
 430                 (void)dispatcher;
 431         }
 432 };
 433
 434 #endif  //BT_OVERLAPPING_PAIR_CACHE_H