src/BulletCollision/BroadphaseCollision/btOverlappingPairCache.h

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