Back to index

supertuxkart  0.5+dfsg1
btOverlappingPairCache.h
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 #ifndef OVERLAPPING_PAIR_CACHE_H
00017 #define OVERLAPPING_PAIR_CACHE_H
00018 
00019 
00020 #include "btBroadphaseInterface.h"
00021 #include "btBroadphaseProxy.h"
00022 #include "btOverlappingPairCallback.h"
00023 
00024 #include "LinearMath/btPoint3.h"
00025 #include "LinearMath/btAlignedObjectArray.h"
00026 class btDispatcher;
00027 
00028 typedef btAlignedObjectArray<btBroadphasePair>   btBroadphasePairArray;
00029 
00030 struct btOverlapCallback
00031 {
00032        virtual ~btOverlapCallback()
00033        {}
00034        //return true for deletion of the pair
00035        virtual bool  processOverlap(btBroadphasePair& pair) = 0;
00036 
00037 };
00038 
00039 struct btOverlapFilterCallback
00040 {
00041        virtual ~btOverlapFilterCallback()
00042        {}
00043        // return true when pairs need collision
00044        virtual bool  needBroadphaseCollision(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1) const = 0;
00045 };
00046 
00047 
00048 
00049 
00050 
00051 
00052 
00053 extern int gRemovePairs;
00054 extern int gAddedPairs;
00055 extern int gFindPairs;
00056 
00057 const int BT_NULL_PAIR=0xffffffff;
00058 
00061 class btOverlappingPairCache : public btOverlappingPairCallback
00062 {
00063 public:
00064 
00065        virtual btBroadphasePair*   getOverlappingPairArrayPtr() = 0;
00066        
00067        virtual const btBroadphasePair*    getOverlappingPairArrayPtr() const = 0;
00068 
00069        virtual btBroadphasePairArray&     getOverlappingPairArray() = 0;
00070 
00071        virtual       void   cleanOverlappingPair(btBroadphasePair& pair,btDispatcher* dispatcher) = 0;
00072 
00073        virtual int getNumOverlappingPairs() const = 0;
00074 
00075        virtual void  cleanProxyFromPairs(btBroadphaseProxy* proxy,btDispatcher* dispatcher) = 0;
00076 
00077        virtual       void setOverlapFilterCallback(btOverlapFilterCallback* callback) = 0;
00078 
00079        virtual void  processAllOverlappingPairs(btOverlapCallback*,btDispatcher* dispatcher) = 0;
00080 
00081        virtual btBroadphasePair* findPair(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1) = 0;
00082 
00083        virtual bool  hasDeferredRemoval() = 0;
00084 
00085 };
00086 
00088 class btHashedOverlappingPairCache : public btOverlappingPairCache
00089 {
00090        btBroadphasePairArray       m_overlappingPairArray;
00091        btOverlapFilterCallback* m_overlapFilterCallback;
00092        bool          m_blockedForChanges;
00093 
00094 
00095 public:
00096        btHashedOverlappingPairCache();
00097        virtual ~btHashedOverlappingPairCache();
00098 
00099        
00100        void   removeOverlappingPairsContainingProxy(btBroadphaseProxy* proxy,btDispatcher* dispatcher);
00101 
00102        virtual void* removeOverlappingPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1,btDispatcher* dispatcher);
00103        
00104        SIMD_FORCE_INLINE bool needsBroadphaseCollision(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1) const
00105        {
00106               if (m_overlapFilterCallback)
00107                      return m_overlapFilterCallback->needBroadphaseCollision(proxy0,proxy1);
00108 
00109               bool collides = (proxy0->m_collisionFilterGroup & proxy1->m_collisionFilterMask) != 0;
00110               collides = collides && (proxy1->m_collisionFilterGroup & proxy0->m_collisionFilterMask);
00111               
00112               return collides;
00113        }
00114 
00115        // Add a pair and return the new pair. If the pair already exists,
00116        // no new pair is created and the old one is returned.
00117        virtual btBroadphasePair*   addOverlappingPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1)
00118        {
00119               gAddedPairs++;
00120 
00121               if (!needsBroadphaseCollision(proxy0,proxy1))
00122                      return 0;
00123 
00124               return internalAddPair(proxy0,proxy1);
00125        }
00126 
00127        
00128 
00129        void   cleanProxyFromPairs(btBroadphaseProxy* proxy,btDispatcher* dispatcher);
00130 
00131        
00132        virtual void  processAllOverlappingPairs(btOverlapCallback*,btDispatcher* dispatcher);
00133 
00134        virtual btBroadphasePair*   getOverlappingPairArrayPtr()
00135        {
00136               return &m_overlappingPairArray[0];
00137        }
00138 
00139        const btBroadphasePair*     getOverlappingPairArrayPtr() const
00140        {
00141               return &m_overlappingPairArray[0];
00142        }
00143 
00144        btBroadphasePairArray&      getOverlappingPairArray()
00145        {
00146               return m_overlappingPairArray;
00147        }
00148 
00149        const btBroadphasePairArray&       getOverlappingPairArray() const
00150        {
00151               return m_overlappingPairArray;
00152        }
00153 
00154        void   cleanOverlappingPair(btBroadphasePair& pair,btDispatcher* dispatcher);
00155 
00156 
00157 
00158        btBroadphasePair* findPair(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1);
00159 
00160        int GetCount() const { return m_overlappingPairArray.size(); }
00161 //     btBroadphasePair* GetPairs() { return m_pairs; }
00162 
00163        btOverlapFilterCallback* getOverlapFilterCallback()
00164        {
00165               return m_overlapFilterCallback;
00166        }
00167 
00168        void setOverlapFilterCallback(btOverlapFilterCallback* callback)
00169        {
00170               m_overlapFilterCallback = callback;
00171        }
00172 
00173        int    getNumOverlappingPairs() const
00174        {
00175               return m_overlappingPairArray.size();
00176        }
00177 private:
00178        
00179        btBroadphasePair*    internalAddPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1);
00180 
00181        void   growTables();
00182 
00183        SIMD_FORCE_INLINE bool equalsPair(const btBroadphasePair& pair, int proxyId1, int proxyId2)
00184        {      
00185               return pair.m_pProxy0->getUid() == proxyId1 && pair.m_pProxy1->getUid() == proxyId2;
00186        }
00187 
00188        /*
00189        // Thomas Wang's hash, see: http://www.concentric.net/~Ttwang/tech/inthash.htm
00190        // This assumes proxyId1 and proxyId2 are 16-bit.
00191        SIMD_FORCE_INLINE int getHash(int proxyId1, int proxyId2)
00192        {
00193               int key = (proxyId2 << 16) | proxyId1;
00194               key = ~key + (key << 15);
00195               key = key ^ (key >> 12);
00196               key = key + (key << 2);
00197               key = key ^ (key >> 4);
00198               key = key * 2057;
00199               key = key ^ (key >> 16);
00200               return key;
00201        }
00202        */
00203 
00204 
00205        
00206        SIMD_FORCE_INLINE    unsigned int getHash(unsigned int proxyId1, unsigned int proxyId2)
00207        {
00208               int key = ((unsigned int)proxyId1) | (((unsigned int)proxyId2) <<16);
00209               // Thomas Wang's hash
00210 
00211               key += ~(key << 15);
00212               key ^=  (key >> 10);
00213               key +=  (key << 3);
00214               key ^=  (key >> 6);
00215               key += ~(key << 11);
00216               key ^=  (key >> 16);
00217               return key;
00218        }
00219        
00220 
00221 
00222 
00223 
00224        SIMD_FORCE_INLINE btBroadphasePair* internalFindPair(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1, int hash)
00225        {
00226               int proxyId1 = proxy0->getUid();
00227               int proxyId2 = proxy1->getUid();
00228               if (proxyId1 > proxyId2) 
00229                      btSwap(proxyId1, proxyId2);
00230 
00231               int index = m_hashTable[hash];
00232               
00233               while( index != BT_NULL_PAIR && equalsPair(m_overlappingPairArray[index], proxyId1, proxyId2) == false)
00234               {
00235                      index = m_next[index];
00236               }
00237 
00238               if ( index == BT_NULL_PAIR )
00239               {
00240                      return NULL;
00241               }
00242 
00243               btAssert(index < m_overlappingPairArray.size());
00244 
00245               return &m_overlappingPairArray[index];
00246        }
00247 
00248        virtual bool  hasDeferredRemoval()
00249        {
00250               return false;
00251        }
00252 
00253 public:
00254        
00255        btAlignedObjectArray<int>   m_hashTable;
00256        btAlignedObjectArray<int>   m_next;
00257        
00258 };
00259 
00260 
00261 
00262 
00265 class  btSortedOverlappingPairCache : public btOverlappingPairCache
00266 {
00267        protected:
00268               //avoid brute-force finding all the time
00269               btBroadphasePairArray       m_overlappingPairArray;
00270 
00271               //during the dispatch, check that user doesn't destroy/create proxy
00272               bool          m_blockedForChanges;
00273 
00275               bool          m_hasDeferredRemoval;
00276               
00277               //if set, use the callback instead of the built in filter in needBroadphaseCollision
00278               btOverlapFilterCallback* m_overlapFilterCallback;
00279 
00280        public:
00281                      
00282               btSortedOverlappingPairCache();    
00283               virtual ~btSortedOverlappingPairCache();
00284 
00285               virtual void  processAllOverlappingPairs(btOverlapCallback*,btDispatcher* dispatcher);
00286 
00287               void*  removeOverlappingPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1,btDispatcher* dispatcher);
00288 
00289               void   cleanOverlappingPair(btBroadphasePair& pair,btDispatcher* dispatcher);
00290               
00291               btBroadphasePair*    addOverlappingPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1);
00292 
00293               btBroadphasePair*    findPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1);
00294                      
00295               
00296               void   cleanProxyFromPairs(btBroadphaseProxy* proxy,btDispatcher* dispatcher);
00297 
00298               void   removeOverlappingPairsContainingProxy(btBroadphaseProxy* proxy,btDispatcher* dispatcher);
00299 
00300 
00301               inline bool needsBroadphaseCollision(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1) const
00302               {
00303                      if (m_overlapFilterCallback)
00304                             return m_overlapFilterCallback->needBroadphaseCollision(proxy0,proxy1);
00305 
00306                      bool collides = (proxy0->m_collisionFilterGroup & proxy1->m_collisionFilterMask) != 0;
00307                      collides = collides && (proxy1->m_collisionFilterGroup & proxy0->m_collisionFilterMask);
00308                      
00309                      return collides;
00310               }
00311               
00312               btBroadphasePairArray&      getOverlappingPairArray()
00313               {
00314                      return m_overlappingPairArray;
00315               }
00316 
00317               const btBroadphasePairArray&       getOverlappingPairArray() const
00318               {
00319                      return m_overlappingPairArray;
00320               }
00321 
00322               
00323 
00324 
00325               btBroadphasePair*    getOverlappingPairArrayPtr()
00326               {
00327                      return &m_overlappingPairArray[0];
00328               }
00329 
00330               const btBroadphasePair*     getOverlappingPairArrayPtr() const
00331               {
00332                      return &m_overlappingPairArray[0];
00333               }
00334 
00335               int    getNumOverlappingPairs() const
00336               {
00337                      return m_overlappingPairArray.size();
00338               }
00339               
00340               btOverlapFilterCallback* getOverlapFilterCallback()
00341               {
00342                      return m_overlapFilterCallback;
00343               }
00344 
00345               void setOverlapFilterCallback(btOverlapFilterCallback* callback)
00346               {
00347                      m_overlapFilterCallback = callback;
00348               }
00349 
00350               virtual bool  hasDeferredRemoval()
00351               {
00352                      return m_hasDeferredRemoval;
00353               }
00354 
00355 
00356 };
00357 
00358 
00359 
00361 class btNullPairCache : public btOverlappingPairCache
00362 {
00363 
00364        btBroadphasePairArray       m_overlappingPairArray;
00365 
00366 public:
00367 
00368        virtual btBroadphasePair*   getOverlappingPairArrayPtr()
00369        {
00370               return &m_overlappingPairArray[0];
00371        }
00372        const btBroadphasePair*     getOverlappingPairArrayPtr() const
00373        {
00374               return &m_overlappingPairArray[0];
00375        }
00376        btBroadphasePairArray&      getOverlappingPairArray()
00377        {
00378               return m_overlappingPairArray;
00379        }
00380        
00381        virtual       void   cleanOverlappingPair(btBroadphasePair& pair,btDispatcher* dispatcher)
00382        {
00383 
00384        }
00385 
00386        virtual int getNumOverlappingPairs() const
00387        {
00388               return 0;
00389        }
00390 
00391        virtual void  cleanProxyFromPairs(btBroadphaseProxy* proxy,btDispatcher* dispatcher)
00392        {
00393 
00394        }
00395 
00396        virtual       void setOverlapFilterCallback(btOverlapFilterCallback* callback)
00397        {
00398        }
00399 
00400        virtual void  processAllOverlappingPairs(btOverlapCallback*,btDispatcher* dispatcher)
00401        {
00402        }
00403 
00404        virtual btBroadphasePair* findPair(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1)
00405        {
00406               return 0;
00407        }
00408 
00409        virtual bool  hasDeferredRemoval()
00410        {
00411               return true;
00412        }
00413 
00414        virtual btBroadphasePair*   addOverlappingPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1)
00415        {
00416               return 0;
00417        }
00418 
00419        virtual void* removeOverlappingPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1,btDispatcher* dispatcher)
00420        {
00421               return 0;
00422        }
00423 
00424        virtual void  removeOverlappingPairsContainingProxy(btBroadphaseProxy* proxy0,btDispatcher* dispatcher)
00425        {
00426        }
00427 
00428 
00429 };
00430 
00431 
00432 #endif //OVERLAPPING_PAIR_CACHE_H
00433 
00434