dali-physics/third-party/bullet3/src/Bullet3Collision/BroadPhaseCollision/b3OverlappingPairCache.h

   1 /*
   2 Bullet Continuous Collision Detection and Physics Library
   3 Copyright (c) 2003-2013 Erwin Coumans  http://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 B3_OVERLAPPING_PAIR_CACHE_H
  17 #define B3_OVERLAPPING_PAIR_CACHE_H
  18
  19 #include "Bullet3Common/shared/b3Int2.h"
  20 #include "Bullet3Common/b3AlignedObjectArray.h"
  21
  22 class b3Dispatcher;
  23 #include "b3OverlappingPair.h"
  24
  25 typedef b3AlignedObjectArray<b3BroadphasePair> b3BroadphasePairArray;
  26
  27 struct b3OverlapCallback
  28 {
  29         virtual ~b3OverlapCallback()
  30         {
  31         }
  32         //return true for deletion of the pair
  33         virtual bool processOverlap(b3BroadphasePair& pair) = 0;
  34 };
  35
  36 struct b3OverlapFilterCallback
  37 {
  38         virtual ~b3OverlapFilterCallback()
  39         {
  40         }
  41         // return true when pairs need collision
  42         virtual bool needBroadphaseCollision(int proxy0, int proxy1) const = 0;
  43 };
  44
  45 extern int b3g_removePairs;
  46 extern int b3g_addedPairs;
  47 extern int b3g_findPairs;
  48
  49 const int B3_NULL_PAIR = 0xffffffff;
  50
  51 ///The b3OverlappingPairCache provides an interface for overlapping pair management (add, remove, storage), used by the b3BroadphaseInterface broadphases.
  52 ///The b3HashedOverlappingPairCache and b3SortedOverlappingPairCache classes are two implementations.
  53 class b3OverlappingPairCache
  54 {
  55 public:
  56         virtual ~b3OverlappingPairCache() {}  // this is needed so we can get to the derived class destructor
  57
  58         virtual b3BroadphasePair* getOverlappingPairArrayPtr() = 0;
  59
  60         virtual const b3BroadphasePair* getOverlappingPairArrayPtr() const = 0;
  61
  62         virtual b3BroadphasePairArray& getOverlappingPairArray() = 0;
  63
  64         virtual void cleanOverlappingPair(b3BroadphasePair& pair, b3Dispatcher* dispatcher) = 0;
  65
  66         virtual int getNumOverlappingPairs() const = 0;
  67
  68         virtual void cleanProxyFromPairs(int proxy, b3Dispatcher* dispatcher) = 0;
  69
  70         virtual void setOverlapFilterCallback(b3OverlapFilterCallback* callback) = 0;
  71
  72         virtual void processAllOverlappingPairs(b3OverlapCallback*, b3Dispatcher* dispatcher) = 0;
  73
  74         virtual b3BroadphasePair* findPair(int proxy0, int proxy1) = 0;
  75
  76         virtual bool hasDeferredRemoval() = 0;
  77
  78         //virtual       void    setInternalGhostPairCallback(b3OverlappingPairCallback* ghostPairCallback)=0;
  79
  80         virtual b3BroadphasePair* addOverlappingPair(int proxy0, int proxy1) = 0;
  81         virtual void* removeOverlappingPair(int proxy0, int proxy1, b3Dispatcher* dispatcher) = 0;
  82         virtual void removeOverlappingPairsContainingProxy(int /*proxy0*/, b3Dispatcher* /*dispatcher*/) = 0;
  83
  84         virtual void sortOverlappingPairs(b3Dispatcher* dispatcher) = 0;
  85 };
  86
  87 /// Hash-space based Pair Cache, thanks to Erin Catto, Box2D, http://www.box2d.org, and Pierre Terdiman, Codercorner, http://codercorner.com
  88 class b3HashedOverlappingPairCache : public b3OverlappingPairCache
  89 {
  90         b3BroadphasePairArray m_overlappingPairArray;
  91         b3OverlapFilterCallback* m_overlapFilterCallback;
  92         //      bool            m_blockedForChanges;
  93
  94 public:
  95         b3HashedOverlappingPairCache();
  96         virtual ~b3HashedOverlappingPairCache();
  97
  98         virtual void removeOverlappingPairsContainingProxy(int proxy, b3Dispatcher* dispatcher);
  99
 100         virtual void* removeOverlappingPair(int proxy0, int proxy1, b3Dispatcher* dispatcher);
 101
 102         B3_FORCE_INLINE bool needsBroadphaseCollision(int proxy0, int proxy1) const
 103         {
 104                 if (m_overlapFilterCallback)
 105                         return m_overlapFilterCallback->needBroadphaseCollision(proxy0, proxy1);
 106
 107                 bool collides = true;  //(proxy0->m_collisionFilterGroup & proxy1->m_collisionFilterMask) != 0;
 108                 //collides = collides && (proxy1->m_collisionFilterGroup & proxy0->m_collisionFilterMask);
 109
 110                 return collides;
 111         }
 112
 113         // Add a pair and return the new pair. If the pair already exists,
 114         // no new pair is created and the old one is returned.
 115         virtual b3BroadphasePair* addOverlappingPair(int proxy0, int proxy1)
 116         {
 117                 b3g_addedPairs++;
 118
 119                 if (!needsBroadphaseCollision(proxy0, proxy1))
 120                         return 0;
 121
 122                 return internalAddPair(proxy0, proxy1);
 123         }
 124
 125         void cleanProxyFromPairs(int proxy, b3Dispatcher* dispatcher);
 126
 127         virtual void processAllOverlappingPairs(b3OverlapCallback*, b3Dispatcher* dispatcher);
 128
 129         virtual b3BroadphasePair* getOverlappingPairArrayPtr()
 130         {
 131                 return &m_overlappingPairArray[0];
 132         }
 133
 134         const b3BroadphasePair* getOverlappingPairArrayPtr() const
 135         {
 136                 return &m_overlappingPairArray[0];
 137         }
 138
 139         b3BroadphasePairArray& getOverlappingPairArray()
 140         {
 141                 return m_overlappingPairArray;
 142         }
 143
 144         const b3BroadphasePairArray& getOverlappingPairArray() const
 145         {
 146                 return m_overlappingPairArray;
 147         }
 148
 149         void cleanOverlappingPair(b3BroadphasePair& pair, b3Dispatcher* dispatcher);
 150
 151         b3BroadphasePair* findPair(int proxy0, int proxy1);
 152
 153         int GetCount() const { return m_overlappingPairArray.size(); }
 154         //      b3BroadphasePair* GetPairs() { return m_pairs; }
 155
 156         b3OverlapFilterCallback* getOverlapFilterCallback()
 157         {
 158                 return m_overlapFilterCallback;
 159         }
 160
 161         void setOverlapFilterCallback(b3OverlapFilterCallback* callback)
 162         {
 163                 m_overlapFilterCallback = callback;
 164         }
 165
 166         int getNumOverlappingPairs() const
 167         {
 168                 return m_overlappingPairArray.size();
 169         }
 170
 171 private:
 172         b3BroadphasePair* internalAddPair(int proxy0, int proxy1);
 173
 174         void growTables();
 175
 176         B3_FORCE_INLINE bool equalsPair(const b3BroadphasePair& pair, int proxyId1, int proxyId2)
 177         {
 178                 return pair.x == proxyId1 && pair.y == proxyId2;
 179         }
 180
 181         /*
 182         // Thomas Wang's hash, see: http://www.concentric.net/~Ttwang/tech/inthash.htm
 183         // This assumes proxyId1 and proxyId2 are 16-bit.
 184         B3_FORCE_INLINE int getHash(int proxyId1, int proxyId2)
 185         {
 186                 int key = (proxyId2 << 16) | proxyId1;
 187                 key = ~key + (key << 15);
 188                 key = key ^ (key >> 12);
 189                 key = key + (key << 2);
 190                 key = key ^ (key >> 4);
 191                 key = key * 2057;
 192                 key = key ^ (key >> 16);
 193                 return key;
 194         }
 195         */
 196
 197         B3_FORCE_INLINE unsigned int getHash(unsigned int proxyId1, unsigned int proxyId2)
 198         {
 199                 int key = static_cast<int>(((unsigned int)proxyId1) | (((unsigned int)proxyId2) << 16));
 200                 // Thomas Wang's hash
 201
 202                 key += ~(key << 15);
 203                 key ^= (key >> 10);
 204                 key += (key << 3);
 205                 key ^= (key >> 6);
 206                 key += ~(key << 11);
 207                 key ^= (key >> 16);
 208                 return static_cast<unsigned int>(key);
 209         }
 210
 211         B3_FORCE_INLINE b3BroadphasePair* internalFindPair(int proxy0, int proxy1, int hash)
 212         {
 213                 int proxyId1 = proxy0;
 214                 int proxyId2 = proxy1;
 215 #if 0  // wrong, 'equalsPair' use unsorted uids, copy-past devil striked again. Nat.
 216                 if (proxyId1 > proxyId2)
 217                         b3Swap(proxyId1, proxyId2);
 218 #endif
 219
 220                 int index = m_hashTable[hash];
 221
 222                 while (index != B3_NULL_PAIR && equalsPair(m_overlappingPairArray[index], proxyId1, proxyId2) == false)
 223                 {
 224                         index = m_next[index];
 225                 }
 226
 227                 if (index == B3_NULL_PAIR)
 228                 {
 229                         return NULL;
 230                 }
 231
 232                 b3Assert(index < m_overlappingPairArray.size());
 233
 234                 return &m_overlappingPairArray[index];
 235         }
 236
 237         virtual bool hasDeferredRemoval()
 238         {
 239                 return false;
 240         }
 241
 242         /*      virtual void    setInternalGhostPairCallback(b3OverlappingPairCallback* ghostPairCallback)
 243         {
 244                 m_ghostPairCallback = ghostPairCallback;
 245         }
 246         */
 247
 248         virtual void sortOverlappingPairs(b3Dispatcher* dispatcher);
 249
 250 protected:
 251         b3AlignedObjectArray<int> m_hashTable;
 252         b3AlignedObjectArray<int> m_next;
 253         //      b3OverlappingPairCallback*      m_ghostPairCallback;
 254 };
 255
 256 ///b3SortedOverlappingPairCache maintains the objects with overlapping AABB
 257 ///Typically managed by the Broadphase, Axis3Sweep or b3SimpleBroadphase
 258 class b3SortedOverlappingPairCache : public b3OverlappingPairCache
 259 {
 260 protected:
 261         //avoid brute-force finding all the time
 262         b3BroadphasePairArray 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         b3OverlapFilterCallback* m_overlapFilterCallback;
 272
 273         //              b3OverlappingPairCallback*      m_ghostPairCallback;
 274
 275 public:
 276         b3SortedOverlappingPairCache();
 277         virtual ~b3SortedOverlappingPairCache();
 278
 279         virtual void processAllOverlappingPairs(b3OverlapCallback*, b3Dispatcher* dispatcher);
 280
 281         void* removeOverlappingPair(int proxy0, int proxy1, b3Dispatcher* dispatcher);
 282
 283         void cleanOverlappingPair(b3BroadphasePair& pair, b3Dispatcher* dispatcher);
 284
 285         b3BroadphasePair* addOverlappingPair(int proxy0, int proxy1);
 286
 287         b3BroadphasePair* findPair(int proxy0, int proxy1);
 288
 289         void cleanProxyFromPairs(int proxy, b3Dispatcher* dispatcher);
 290
 291         virtual void removeOverlappingPairsContainingProxy(int proxy, b3Dispatcher* dispatcher);
 292
 293         inline bool needsBroadphaseCollision(int proxy0, int proxy1) const
 294         {
 295                 if (m_overlapFilterCallback)
 296                         return m_overlapFilterCallback->needBroadphaseCollision(proxy0, proxy1);
 297
 298                 bool collides = true;  //(proxy0->m_collisionFilterGroup & proxy1->m_collisionFilterMask) != 0;
 299                 //collides = collides && (proxy1->m_collisionFilterGroup & proxy0->m_collisionFilterMask);
 300
 301                 return collides;
 302         }
 303
 304         b3BroadphasePairArray& getOverlappingPairArray()
 305         {
 306                 return m_overlappingPairArray;
 307         }
 308
 309         const b3BroadphasePairArray& getOverlappingPairArray() const
 310         {
 311                 return m_overlappingPairArray;
 312         }
 313
 314         b3BroadphasePair* getOverlappingPairArrayPtr()
 315         {
 316                 return &m_overlappingPairArray[0];
 317         }
 318
 319         const b3BroadphasePair* getOverlappingPairArrayPtr() const
 320         {
 321                 return &m_overlappingPairArray[0];
 322         }
 323
 324         int getNumOverlappingPairs() const
 325         {
 326                 return m_overlappingPairArray.size();
 327         }
 328
 329         b3OverlapFilterCallback* getOverlapFilterCallback()
 330         {
 331                 return m_overlapFilterCallback;
 332         }
 333
 334         void setOverlapFilterCallback(b3OverlapFilterCallback* callback)
 335         {
 336                 m_overlapFilterCallback = callback;
 337         }
 338
 339         virtual bool hasDeferredRemoval()
 340         {
 341                 return m_hasDeferredRemoval;
 342         }
 343
 344         /*              virtual void    setInternalGhostPairCallback(b3OverlappingPairCallback* ghostPairCallback)
 345                 {
 346                         m_ghostPairCallback = ghostPairCallback;
 347                 }
 348                 */
 349         virtual void sortOverlappingPairs(b3Dispatcher* dispatcher);
 350 };
 351
 352 ///b3NullPairCache skips add/removal of overlapping pairs. Userful for benchmarking and unit testing.
 353 class b3NullPairCache : public b3OverlappingPairCache
 354 {
 355         b3BroadphasePairArray m_overlappingPairArray;
 356
 357 public:
 358         virtual b3BroadphasePair* getOverlappingPairArrayPtr()
 359         {
 360                 return &m_overlappingPairArray[0];
 361         }
 362         const b3BroadphasePair* getOverlappingPairArrayPtr() const
 363         {
 364                 return &m_overlappingPairArray[0];
 365         }
 366         b3BroadphasePairArray& getOverlappingPairArray()
 367         {
 368                 return m_overlappingPairArray;
 369         }
 370
 371         virtual void cleanOverlappingPair(b3BroadphasePair& /*pair*/, b3Dispatcher* /*dispatcher*/)
 372         {
 373         }
 374
 375         virtual int getNumOverlappingPairs() const
 376         {
 377                 return 0;
 378         }
 379
 380         virtual void cleanProxyFromPairs(int /*proxy*/, b3Dispatcher* /*dispatcher*/)
 381         {
 382         }
 383
 384         virtual void setOverlapFilterCallback(b3OverlapFilterCallback* /*callback*/)
 385         {
 386         }
 387
 388         virtual void processAllOverlappingPairs(b3OverlapCallback*, b3Dispatcher* /*dispatcher*/)
 389         {
 390         }
 391
 392         virtual b3BroadphasePair* findPair(int /*proxy0*/, int /*proxy1*/)
 393         {
 394                 return 0;
 395         }
 396
 397         virtual bool hasDeferredRemoval()
 398         {
 399                 return true;
 400         }
 401
 402         //      virtual void    setInternalGhostPairCallback(b3OverlappingPairCallback* /* ghostPairCallback */)
 403         //      {
 404         //
 405         //      }
 406
 407         virtual b3BroadphasePair* addOverlappingPair(int /*proxy0*/, int /*proxy1*/)
 408         {
 409                 return 0;
 410         }
 411
 412         virtual void* removeOverlappingPair(int /*proxy0*/, int /*proxy1*/, b3Dispatcher* /*dispatcher*/)
 413         {
 414                 return 0;
 415         }
 416
 417         virtual void removeOverlappingPairsContainingProxy(int /*proxy0*/, b3Dispatcher* /*dispatcher*/)
 418         {
 419         }
 420
 421         virtual void sortOverlappingPairs(b3Dispatcher* dispatcher)
 422         {
 423                 (void)dispatcher;
 424         }
 425 };
 426
 427 #endif  //B3_OVERLAPPING_PAIR_CACHE_H