Back to index

supertuxkart  0.5+dfsg1
btOverlappingPairCache.cpp
Go to the documentation of this file.
00001 /*
00002 Bullet Continuous Collision Detection and Physics Library
00003 Copyright (c) 2003-2006 Erwin Coumans  http://continuousphysics.com/Bullet/
00004 
00005 This software is provided 'as-is', without any express or implied warranty.
00006 In no event will the authors be held liable for any damages arising from the use of this software.
00007 Permission is granted to anyone to use this software for any purpose, 
00008 including commercial applications, and to alter it and redistribute it freely, 
00009 subject to the following restrictions:
00010 
00011 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.
00012 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
00013 3. This notice may not be removed or altered from any source distribution.
00014 */
00015 
00016 
00017 
00018 #include "btOverlappingPairCache.h"
00019 
00020 #include "btDispatcher.h"
00021 #include "btCollisionAlgorithm.h"
00022 
00023 int    gOverlappingPairs = 0;
00024 
00025 int gRemovePairs =0;
00026 int gAddedPairs =0;
00027 int gFindPairs =0;
00028 
00029 
00030 
00031 
00032 btHashedOverlappingPairCache::btHashedOverlappingPairCache():
00033        m_overlapFilterCallback(0),
00034        m_blockedForChanges(false)
00035 {
00036        int initialAllocatedSize= 2;
00037        m_overlappingPairArray.reserve(initialAllocatedSize);
00038        growTables();
00039 }
00040 
00041 
00042 
00043 
00044 btHashedOverlappingPairCache::~btHashedOverlappingPairCache()
00045 {
00046        //todo/test: show we erase/delete data, or is it automatic
00047 }
00048 
00049 
00050 
00051 void   btHashedOverlappingPairCache::cleanOverlappingPair(btBroadphasePair& pair,btDispatcher* dispatcher)
00052 {
00053        if (pair.m_algorithm)
00054        {
00055               {
00056                      pair.m_algorithm->~btCollisionAlgorithm();
00057                      dispatcher->freeCollisionAlgorithm(pair.m_algorithm);
00058                      pair.m_algorithm=0;
00059               }
00060        }
00061 }
00062 
00063 
00064 
00065 
00066 void   btHashedOverlappingPairCache::cleanProxyFromPairs(btBroadphaseProxy* proxy,btDispatcher* dispatcher)
00067 {
00068 
00069        class  CleanPairCallback : public btOverlapCallback
00070        {
00071               btBroadphaseProxy* m_cleanProxy;
00072               btOverlappingPairCache*     m_pairCache;
00073               btDispatcher* m_dispatcher;
00074 
00075        public:
00076               CleanPairCallback(btBroadphaseProxy* cleanProxy,btOverlappingPairCache* pairCache,btDispatcher* dispatcher)
00077                      :m_cleanProxy(cleanProxy),
00078                      m_pairCache(pairCache),
00079                      m_dispatcher(dispatcher)
00080               {
00081               }
00082               virtual       bool   processOverlap(btBroadphasePair& pair)
00083               {
00084                      if ((pair.m_pProxy0 == m_cleanProxy) ||
00085                             (pair.m_pProxy1 == m_cleanProxy))
00086                      {
00087                             m_pairCache->cleanOverlappingPair(pair,m_dispatcher);
00088                      }
00089                      return false;
00090               }
00091               
00092        };
00093 
00094        CleanPairCallback cleanPairs(proxy,this,dispatcher);
00095 
00096        processAllOverlappingPairs(&cleanPairs,dispatcher);
00097 
00098 }
00099 
00100 
00101 
00102 
00103 void   btHashedOverlappingPairCache::removeOverlappingPairsContainingProxy(btBroadphaseProxy* proxy,btDispatcher* dispatcher)
00104 {
00105 
00106        class  RemovePairCallback : public btOverlapCallback
00107        {
00108               btBroadphaseProxy* m_obsoleteProxy;
00109 
00110        public:
00111               RemovePairCallback(btBroadphaseProxy* obsoleteProxy)
00112                      :m_obsoleteProxy(obsoleteProxy)
00113               {
00114               }
00115               virtual       bool   processOverlap(btBroadphasePair& pair)
00116               {
00117                      return ((pair.m_pProxy0 == m_obsoleteProxy) ||
00118                             (pair.m_pProxy1 == m_obsoleteProxy));
00119               }
00120               
00121        };
00122 
00123 
00124        RemovePairCallback removeCallback(proxy);
00125 
00126        processAllOverlappingPairs(&removeCallback,dispatcher);
00127 }
00128 
00129 
00130 
00131 
00132 
00133 btBroadphasePair* btHashedOverlappingPairCache::findPair(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1)
00134 {
00135        gFindPairs++;
00136 
00137        int proxyId1 = proxy0->getUid();
00138        int proxyId2 = proxy1->getUid();
00139 
00140        if (proxyId1 > proxyId2) 
00141               btSwap(proxyId1, proxyId2);
00142 
00143        int hash = getHash(proxyId1, proxyId2) & (m_overlappingPairArray.capacity()-1);
00144 
00145        if (hash >= m_hashTable.size())
00146        {
00147               return NULL;
00148        }
00149 
00150        int index = m_hashTable[hash];
00151        while (index != BT_NULL_PAIR && equalsPair(m_overlappingPairArray[index], proxyId1, proxyId2) == false)
00152        {
00153               index = m_next[index];
00154        }
00155 
00156        if (index == BT_NULL_PAIR)
00157        {
00158               return NULL;
00159        }
00160 
00161        btAssert(index < m_overlappingPairArray.size());
00162 
00163        return &m_overlappingPairArray[index];
00164 }
00165 
00166 //#include <stdio.h>
00167 
00168 void   btHashedOverlappingPairCache::growTables()
00169 {
00170 
00171        int newCapacity = m_overlappingPairArray.capacity();
00172 
00173        if (m_hashTable.size() < newCapacity)
00174        {
00175               //grow hashtable and next table
00176               int curHashtableSize = m_hashTable.size();
00177 
00178               m_hashTable.resize(newCapacity);
00179               m_next.resize(newCapacity);
00180 
00181 
00182               int i;
00183 
00184               for (i= 0; i < newCapacity; ++i)
00185               {
00186                      m_hashTable[i] = BT_NULL_PAIR;
00187               }
00188               for (i = 0; i < newCapacity; ++i)
00189               {
00190                      m_next[i] = BT_NULL_PAIR;
00191               }
00192 
00193               for(i=0;i<curHashtableSize;i++)
00194               {
00195        
00196                      const btBroadphasePair& pair = m_overlappingPairArray[i];
00197                      int proxyId1 = pair.m_pProxy0->getUid();
00198                      int proxyId2 = pair.m_pProxy1->getUid();
00199                      if (proxyId1 > proxyId2) 
00200                             btSwap(proxyId1, proxyId2);
00201                      int    hashValue = getHash(proxyId1,proxyId2) & (m_overlappingPairArray.capacity()-1);     // New hash value with new mask
00202                      m_next[i] = m_hashTable[hashValue];
00203                      m_hashTable[hashValue] = i;
00204               }
00205 
00206 
00207        }
00208 }
00209 
00210 btBroadphasePair* btHashedOverlappingPairCache::internalAddPair(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1)
00211 {
00212        int proxyId1 = proxy0->getUid();
00213        int proxyId2 = proxy1->getUid();
00214 
00215        if (proxyId1 > proxyId2) 
00216               btSwap(proxyId1, proxyId2);
00217 
00218        int hash = getHash(proxyId1, proxyId2) & (m_overlappingPairArray.capacity()-1);
00219 
00220        
00221 
00222        btBroadphasePair* pair = internalFindPair(proxy0, proxy1, hash);
00223        if (pair != NULL)
00224        {
00225               return pair;
00226        }
00227 
00228        int count = m_overlappingPairArray.size();
00229        int oldCapacity = m_overlappingPairArray.capacity();
00230        void* mem = &m_overlappingPairArray.expand();
00231        int newCapacity = m_overlappingPairArray.capacity();
00232 
00233        if (oldCapacity < newCapacity)
00234        {
00235               growTables();
00236               //hash with new capacity
00237               hash = getHash(proxyId1, proxyId2) & (m_overlappingPairArray.capacity()-1);
00238        }
00239        
00240        pair = new (mem) btBroadphasePair(*proxy0,*proxy1);
00241 //     pair->m_pProxy0 = proxy0;
00242 //     pair->m_pProxy1 = proxy1;
00243        pair->m_algorithm = 0;
00244        pair->m_userInfo = 0;
00245        
00246 
00247        m_next[count] = m_hashTable[hash];
00248        m_hashTable[hash] = count;
00249 
00250        return pair;
00251 }
00252 
00253 
00254 
00255 void* btHashedOverlappingPairCache::removeOverlappingPair(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1,btDispatcher* dispatcher)
00256 {
00257        gRemovePairs++;
00258 
00259        int proxyId1 = proxy0->getUid();
00260        int proxyId2 = proxy1->getUid();
00261 
00262        if (proxyId1 > proxyId2) 
00263               btSwap(proxyId1, proxyId2);
00264 
00265        int hash = getHash(proxyId1, proxyId2) & (m_overlappingPairArray.capacity()-1);
00266 
00267        btBroadphasePair* pair = internalFindPair(proxy0, proxy1, hash);
00268        if (pair == NULL)
00269        {
00270               return 0;
00271        }
00272 
00273        cleanOverlappingPair(*pair,dispatcher);
00274 
00275        void* userData = pair->m_userInfo;
00276 
00277        btAssert(pair->m_pProxy0->getUid() == proxyId1);
00278        btAssert(pair->m_pProxy1->getUid() == proxyId2);
00279 
00280        int pairIndex = int(pair - &m_overlappingPairArray[0]);
00281        btAssert(pairIndex < m_overlappingPairArray.size());
00282 
00283        // Remove the pair from the hash table.
00284        int index = m_hashTable[hash];
00285        btAssert(index != BT_NULL_PAIR);
00286 
00287        int previous = BT_NULL_PAIR;
00288        while (index != pairIndex)
00289        {
00290               previous = index;
00291               index = m_next[index];
00292        }
00293 
00294        if (previous != BT_NULL_PAIR)
00295        {
00296               btAssert(m_next[previous] == pairIndex);
00297               m_next[previous] = m_next[pairIndex];
00298        }
00299        else
00300        {
00301               m_hashTable[hash] = m_next[pairIndex];
00302        }
00303 
00304        // We now move the last pair into spot of the
00305        // pair being removed. We need to fix the hash
00306        // table indices to support the move.
00307 
00308        int lastPairIndex = m_overlappingPairArray.size() - 1;
00309 
00310        // If the removed pair is the last pair, we are done.
00311        if (lastPairIndex == pairIndex)
00312        {
00313               m_overlappingPairArray.pop_back();
00314               return userData;
00315        }
00316 
00317        // Remove the last pair from the hash table.
00318        const btBroadphasePair* last = &m_overlappingPairArray[lastPairIndex];
00319        int lastHash = getHash(last->m_pProxy0->getUid(), last->m_pProxy1->getUid()) & (m_overlappingPairArray.capacity()-1);
00320 
00321        index = m_hashTable[lastHash];
00322        btAssert(index != BT_NULL_PAIR);
00323 
00324        previous = BT_NULL_PAIR;
00325        while (index != lastPairIndex)
00326        {
00327               previous = index;
00328               index = m_next[index];
00329        }
00330 
00331        if (previous != BT_NULL_PAIR)
00332        {
00333               btAssert(m_next[previous] == lastPairIndex);
00334               m_next[previous] = m_next[lastPairIndex];
00335        }
00336        else
00337        {
00338               m_hashTable[lastHash] = m_next[lastPairIndex];
00339        }
00340 
00341        // Copy the last pair into the remove pair's spot.
00342        m_overlappingPairArray[pairIndex] = m_overlappingPairArray[lastPairIndex];
00343 
00344        // Insert the last pair into the hash table
00345        m_next[pairIndex] = m_hashTable[lastHash];
00346        m_hashTable[lastHash] = pairIndex;
00347 
00348        m_overlappingPairArray.pop_back();
00349 
00350        return userData;
00351 }
00352 //#include <stdio.h>
00353 
00354 void   btHashedOverlappingPairCache::processAllOverlappingPairs(btOverlapCallback* callback,btDispatcher* dispatcher)
00355 {
00356 
00357        int i;
00358 
00359 //     printf("m_overlappingPairArray.size()=%d\n",m_overlappingPairArray.size());
00360        for (i=0;i<m_overlappingPairArray.size();)
00361        {
00362        
00363               btBroadphasePair* pair = &m_overlappingPairArray[i];
00364               if (callback->processOverlap(*pair))
00365               {
00366                      removeOverlappingPair(pair->m_pProxy0,pair->m_pProxy1,dispatcher);
00367 
00368                      gOverlappingPairs--;
00369               } else
00370               {
00371                      i++;
00372               }
00373        }
00374 }
00375 
00376 
00377 
00378 void*  btSortedOverlappingPairCache::removeOverlappingPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1, btDispatcher* dispatcher )
00379 {
00380        if (!hasDeferredRemoval())
00381        {
00382               btBroadphasePair findPair(*proxy0,*proxy1);
00383 
00384               int findIndex = m_overlappingPairArray.findLinearSearch(findPair);
00385               if (findIndex < m_overlappingPairArray.size())
00386               {
00387                      gOverlappingPairs--;
00388                      btBroadphasePair& pair = m_overlappingPairArray[findIndex];
00389                      void* userData = pair.m_userInfo;
00390                      cleanOverlappingPair(pair,dispatcher);
00391                      
00392                      m_overlappingPairArray.swap(findIndex,m_overlappingPairArray.capacity()-1);
00393                      m_overlappingPairArray.pop_back();
00394                      return userData;
00395               }
00396        }
00397 
00398        return 0;
00399 }
00400 
00401 
00402 
00403 
00404 
00405 
00406 
00407 
00408 btBroadphasePair*    btSortedOverlappingPairCache::addOverlappingPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1)
00409 {
00410        //don't add overlap with own
00411        assert(proxy0 != proxy1);
00412 
00413        if (!needsBroadphaseCollision(proxy0,proxy1))
00414               return 0;
00415        
00416        void* mem = &m_overlappingPairArray.expand();
00417        btBroadphasePair* pair = new (mem) btBroadphasePair(*proxy0,*proxy1);
00418        gOverlappingPairs++;
00419        return pair;
00420        
00421 }
00422 
00427  btBroadphasePair*   btSortedOverlappingPairCache::findPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1)
00428 {
00429        if (!needsBroadphaseCollision(proxy0,proxy1))
00430               return 0;
00431 
00432        btBroadphasePair tmpPair(*proxy0,*proxy1);
00433        int findIndex = m_overlappingPairArray.findLinearSearch(tmpPair);
00434 
00435        if (findIndex < m_overlappingPairArray.size())
00436        {
00437               //assert(it != m_overlappingPairSet.end());
00438                btBroadphasePair* pair = &m_overlappingPairArray[findIndex];
00439               return pair;
00440        }
00441        return 0;
00442 }
00443 
00444 
00445 
00446 
00447 
00448 
00449 
00450 
00451 
00452 
00453 //#include <stdio.h>
00454 
00455 void   btSortedOverlappingPairCache::processAllOverlappingPairs(btOverlapCallback* callback,btDispatcher* dispatcher)
00456 {
00457 
00458        int i;
00459 
00460        for (i=0;i<m_overlappingPairArray.size();)
00461        {
00462        
00463               btBroadphasePair* pair = &m_overlappingPairArray[i];
00464               if (callback->processOverlap(*pair))
00465               {
00466                      cleanOverlappingPair(*pair,dispatcher);
00467 
00468                      m_overlappingPairArray.swap(i,m_overlappingPairArray.capacity()-1);
00469                      m_overlappingPairArray.pop_back();
00470                      gOverlappingPairs--;
00471               } else
00472               {
00473                      i++;
00474               }
00475        }
00476 }
00477 
00478 
00479 
00480 
00481 btSortedOverlappingPairCache::btSortedOverlappingPairCache():
00482        m_overlapFilterCallback(0),
00483        m_blockedForChanges(false),
00484        m_hasDeferredRemoval(true)
00485 {
00486        int initialAllocatedSize= 2;
00487        m_overlappingPairArray.reserve(initialAllocatedSize);
00488 }
00489 
00490 btSortedOverlappingPairCache::~btSortedOverlappingPairCache()
00491 {
00492        //todo/test: show we erase/delete data, or is it automatic
00493 }
00494 
00495 void   btSortedOverlappingPairCache::cleanOverlappingPair(btBroadphasePair& pair,btDispatcher* dispatcher)
00496 {
00497        if (pair.m_algorithm)
00498        {
00499               {
00500                      pair.m_algorithm->~btCollisionAlgorithm();
00501                      dispatcher->freeCollisionAlgorithm(pair.m_algorithm);
00502                      pair.m_algorithm=0;
00503               }
00504        }
00505 }
00506 
00507 
00508 void   btSortedOverlappingPairCache::cleanProxyFromPairs(btBroadphaseProxy* proxy,btDispatcher* dispatcher)
00509 {
00510 
00511        class  CleanPairCallback : public btOverlapCallback
00512        {
00513               btBroadphaseProxy* m_cleanProxy;
00514               btOverlappingPairCache*     m_pairCache;
00515               btDispatcher* m_dispatcher;
00516 
00517        public:
00518               CleanPairCallback(btBroadphaseProxy* cleanProxy,btOverlappingPairCache* pairCache,btDispatcher* dispatcher)
00519                      :m_cleanProxy(cleanProxy),
00520                      m_pairCache(pairCache),
00521                      m_dispatcher(dispatcher)
00522               {
00523               }
00524               virtual       bool   processOverlap(btBroadphasePair& pair)
00525               {
00526                      if ((pair.m_pProxy0 == m_cleanProxy) ||
00527                             (pair.m_pProxy1 == m_cleanProxy))
00528                      {
00529                             m_pairCache->cleanOverlappingPair(pair,m_dispatcher);
00530                      }
00531                      return false;
00532               }
00533               
00534        };
00535 
00536        CleanPairCallback cleanPairs(proxy,this,dispatcher);
00537 
00538        processAllOverlappingPairs(&cleanPairs,dispatcher);
00539 
00540 }
00541 
00542 
00543 void   btSortedOverlappingPairCache::removeOverlappingPairsContainingProxy(btBroadphaseProxy* proxy,btDispatcher* dispatcher)
00544 {
00545 
00546        class  RemovePairCallback : public btOverlapCallback
00547        {
00548               btBroadphaseProxy* m_obsoleteProxy;
00549 
00550        public:
00551               RemovePairCallback(btBroadphaseProxy* obsoleteProxy)
00552                      :m_obsoleteProxy(obsoleteProxy)
00553               {
00554               }
00555               virtual       bool   processOverlap(btBroadphasePair& pair)
00556               {
00557                      return ((pair.m_pProxy0 == m_obsoleteProxy) ||
00558                             (pair.m_pProxy1 == m_obsoleteProxy));
00559               }
00560               
00561        };
00562 
00563        RemovePairCallback removeCallback(proxy);
00564 
00565        processAllOverlappingPairs(&removeCallback,dispatcher);
00566 }