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 protected: 100 101 btAlignedObjectArray<int> m_hashTable; 102 btAlignedObjectArray<int> m_next; 103 btOverlappingPairCallback* m_ghostPairCallback; 104 105 106 public: 107 btHashedOverlappingPairCache(); 108 virtual ~btHashedOverlappingPairCache(); 109 110 111 void removeOverlappingPairsContainingProxy(btBroadphaseProxy* proxy,btDispatcher* dispatcher); 112 113 virtual void* removeOverlappingPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1,btDispatcher* dispatcher); 114 115 SIMD_FORCE_INLINE bool needsBroadphaseCollision(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1) const 116 { 117 if (m_overlapFilterCallback) 118 return m_overlapFilterCallback->needBroadphaseCollision(proxy0,proxy1); 119 120 bool collides = (proxy0->m_collisionFilterGroup & proxy1->m_collisionFilterMask) != 0; 121 collides = collides && (proxy1->m_collisionFilterGroup & proxy0->m_collisionFilterMask); 122 123 return collides; 124 } 125 126 // Add a pair and return the new pair. If the pair already exists, 127 // no new pair is created and the old one is returned. 128 virtual btBroadphasePair* addOverlappingPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1) 129 { 130 gAddedPairs++; 131 132 if (!needsBroadphaseCollision(proxy0,proxy1)) 133 return 0; 134 135 return internalAddPair(proxy0,proxy1); 136 } 137 138 139 140 void cleanProxyFromPairs(btBroadphaseProxy* proxy,btDispatcher* dispatcher); 141 142 143 virtual void processAllOverlappingPairs(btOverlapCallback*,btDispatcher* dispatcher); 144 145 virtual btBroadphasePair* getOverlappingPairArrayPtr() 146 { 147 return &m_overlappingPairArray[0]; 148 } 149 150 const btBroadphasePair* getOverlappingPairArrayPtr() const 151 { 152 return &m_overlappingPairArray[0]; 153 } 154 155 btBroadphasePairArray& getOverlappingPairArray() 156 { 157 return m_overlappingPairArray; 158 } 159 160 const btBroadphasePairArray& getOverlappingPairArray() const 161 { 162 return m_overlappingPairArray; 163 } 164 165 void cleanOverlappingPair(btBroadphasePair& pair,btDispatcher* dispatcher); 166 167 168 169 btBroadphasePair* findPair(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1); 170 171 int GetCount() const { return m_overlappingPairArray.size(); } 172 // btBroadphasePair* GetPairs() { return m_pairs; } 173 174 btOverlapFilterCallback* getOverlapFilterCallback() 175 { 176 return m_overlapFilterCallback; 177 } 178 179 void setOverlapFilterCallback(btOverlapFilterCallback* callback) 180 { 181 m_overlapFilterCallback = callback; 182 } 183 184 int getNumOverlappingPairs() const 185 { 186 return m_overlappingPairArray.size(); 187 } 188 private: 189 190 btBroadphasePair* internalAddPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1); 191 192 void growTables(); 193 194 SIMD_FORCE_INLINE bool equalsPair(const btBroadphasePair& pair, int proxyId1, int proxyId2) 195 { 196 return pair.m_pProxy0->getUid() == proxyId1 && pair.m_pProxy1->getUid() == proxyId2; 197 } 198 199 /* 200 // Thomas Wang's hash, see: http://www.concentric.net/~Ttwang/tech/inthash.htm 201 // This assumes proxyId1 and proxyId2 are 16-bit. 202 SIMD_FORCE_INLINE int getHash(int proxyId1, int proxyId2) 203 { 204 int key = (proxyId2 << 16) | proxyId1; 205 key = ~key + (key << 15); 206 key = key ^ (key >> 12); 207 key = key + (key << 2); 208 key = key ^ (key >> 4); 209 key = key * 2057; 210 key = key ^ (key >> 16); 211 return key; 212 } 213 */ 214 215 216 217 SIMD_FORCE_INLINE unsigned int getHash(unsigned int proxyId1, unsigned int proxyId2) 218 { 219 int key = static_cast<int>(((unsigned int)proxyId1) | (((unsigned int)proxyId2) <<16)); 220 // Thomas Wang's hash 221 222 key += ~(key << 15); 223 key ^= (key >> 10); 224 key += (key << 3); 225 key ^= (key >> 6); 226 key += ~(key << 11); 227 key ^= (key >> 16); 228 return static_cast<unsigned int>(key); 229 } 230 231 232 233 234 235 SIMD_FORCE_INLINE btBroadphasePair* internalFindPair(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1, int hash) 236 { 237 int proxyId1 = proxy0->getUid(); 238 int proxyId2 = proxy1->getUid(); 239 #if 0 // wrong, 'equalsPair' use unsorted uids, copy-past devil striked again. Nat. 240 if (proxyId1 > proxyId2) 241 btSwap(proxyId1, proxyId2); 242 #endif 243 244 int index = m_hashTable[hash]; 245 246 while( index != BT_NULL_PAIR && equalsPair(m_overlappingPairArray[index], proxyId1, proxyId2) == false) 247 { 248 index = m_next[index]; 249 } 250 251 if ( index == BT_NULL_PAIR ) 252 { 253 return NULL; 254 } 255 256 btAssert(index < m_overlappingPairArray.size()); 257 258 return &m_overlappingPairArray[index]; 259 } 260 261 virtual bool hasDeferredRemoval() 262 { 263 return false; 264 } 265 266 virtual void setInternalGhostPairCallback(btOverlappingPairCallback* ghostPairCallback) 267 { 268 m_ghostPairCallback = ghostPairCallback; 269 } 270 271 virtual void sortOverlappingPairs(btDispatcher* dispatcher); 272 273 274 275 }; 276 277 278 279 280 ///btSortedOverlappingPairCache maintains the objects with overlapping AABB 281 ///Typically managed by the Broadphase, Axis3Sweep or btSimpleBroadphase 282 class btSortedOverlappingPairCache : public btOverlappingPairCache 283 { 284 protected: 285 //avoid brute-force finding all the time 286 btBroadphasePairArray m_overlappingPairArray; 287 288 //during the dispatch, check that user doesn't destroy/create proxy 289 bool m_blockedForChanges; 290 291 ///by default, do the removal during the pair traversal 292 bool m_hasDeferredRemoval; 293 294 //if set, use the callback instead of the built in filter in needBroadphaseCollision 295 btOverlapFilterCallback* m_overlapFilterCallback; 296 297 btOverlappingPairCallback* m_ghostPairCallback; 298 299 public: 300 301 btSortedOverlappingPairCache(); 302 virtual ~btSortedOverlappingPairCache(); 303 304 virtual void processAllOverlappingPairs(btOverlapCallback*,btDispatcher* dispatcher); 305 306 void* removeOverlappingPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1,btDispatcher* dispatcher); 307 308 void cleanOverlappingPair(btBroadphasePair& pair,btDispatcher* dispatcher); 309 310 btBroadphasePair* addOverlappingPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1); 311 312 btBroadphasePair* findPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1); 313 314 315 void cleanProxyFromPairs(btBroadphaseProxy* proxy,btDispatcher* dispatcher); 316 317 void removeOverlappingPairsContainingProxy(btBroadphaseProxy* proxy,btDispatcher* dispatcher); 318 319 320 inline bool needsBroadphaseCollision(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1) const 321 { 322 if (m_overlapFilterCallback) 323 return m_overlapFilterCallback->needBroadphaseCollision(proxy0,proxy1); 324 325 bool collides = (proxy0->m_collisionFilterGroup & proxy1->m_collisionFilterMask) != 0; 326 collides = collides && (proxy1->m_collisionFilterGroup & proxy0->m_collisionFilterMask); 327 328 return collides; 329 } 330 331 btBroadphasePairArray& getOverlappingPairArray() 332 { 333 return m_overlappingPairArray; 334 } 335 336 const btBroadphasePairArray& getOverlappingPairArray() const 337 { 338 return m_overlappingPairArray; 339 } 340 341 342 343 344 btBroadphasePair* getOverlappingPairArrayPtr() 345 { 346 return &m_overlappingPairArray[0]; 347 } 348 349 const btBroadphasePair* getOverlappingPairArrayPtr() const 350 { 351 return &m_overlappingPairArray[0]; 352 } 353 354 int getNumOverlappingPairs() const 355 { 356 return m_overlappingPairArray.size(); 357 } 358 359 btOverlapFilterCallback* getOverlapFilterCallback() 360 { 361 return m_overlapFilterCallback; 362 } 363 364 void setOverlapFilterCallback(btOverlapFilterCallback* callback) 365 { 366 m_overlapFilterCallback = callback; 367 } 368 369 virtual bool hasDeferredRemoval() 370 { 371 return m_hasDeferredRemoval; 372 } 373 374 virtual void setInternalGhostPairCallback(btOverlappingPairCallback* ghostPairCallback) 375 { 376 m_ghostPairCallback = ghostPairCallback; 377 } 378 379 virtual void sortOverlappingPairs(btDispatcher* dispatcher); 380 381 382 }; 383 384 385 386 ///btNullPairCache skips add/removal of overlapping pairs. Userful for benchmarking and unit testing. 387 class btNullPairCache : public btOverlappingPairCache 388 { 389 390 btBroadphasePairArray m_overlappingPairArray; 391 392 public: 393 394 virtual btBroadphasePair* getOverlappingPairArrayPtr() 395 { 396 return &m_overlappingPairArray[0]; 397 } 398 const btBroadphasePair* getOverlappingPairArrayPtr() const 399 { 400 return &m_overlappingPairArray[0]; 401 } 402 btBroadphasePairArray& getOverlappingPairArray() 403 { 404 return m_overlappingPairArray; 405 } 406 407 virtual void cleanOverlappingPair(btBroadphasePair& /*pair*/,btDispatcher* /*dispatcher*/) 408 { 409 410 } 411 412 virtual int getNumOverlappingPairs() const 413 { 414 return 0; 415 } 416 417 virtual void cleanProxyFromPairs(btBroadphaseProxy* /*proxy*/,btDispatcher* /*dispatcher*/) 418 { 419 420 } 421 422 virtual void setOverlapFilterCallback(btOverlapFilterCallback* /*callback*/) 423 { 424 } 425 426 virtual void processAllOverlappingPairs(btOverlapCallback*,btDispatcher* /*dispatcher*/) 427 { 428 } 429 430 virtual btBroadphasePair* findPair(btBroadphaseProxy* /*proxy0*/, btBroadphaseProxy* /*proxy1*/) 431 { 432 return 0; 433 } 434 435 virtual bool hasDeferredRemoval() 436 { 437 return true; 438 } 439 440 virtual void setInternalGhostPairCallback(btOverlappingPairCallback* /* ghostPairCallback */) 441 { 442 443 } 444 445 virtual btBroadphasePair* addOverlappingPair(btBroadphaseProxy* /*proxy0*/,btBroadphaseProxy* /*proxy1*/) 446 { 447 return 0; 448 } 449 450 virtual void* removeOverlappingPair(btBroadphaseProxy* /*proxy0*/,btBroadphaseProxy* /*proxy1*/,btDispatcher* /*dispatcher*/) 451 { 452 return 0; 453 } 454 455 virtual void removeOverlappingPairsContainingProxy(btBroadphaseProxy* /*proxy0*/,btDispatcher* /*dispatcher*/) 456 { 457 } 458 459 virtual void sortOverlappingPairs(btDispatcher* dispatcher) 460 { 461 (void) dispatcher; 462 } 463 464 465 }; 466 467 468 #endif //BT_OVERLAPPING_PAIR_CACHE_H 469 470 471