Back to index

supertuxkart  0.5+dfsg1
Public Member Functions | Public Attributes | Private Member Functions | Private Attributes
btHashedOverlappingPairCache Class Reference

Hash-space based Pair Cache, thanks to Erin Catto, Box2D, http://www.box2d.org, and Pierre Terdiman, Codercorner, http://codercorner.com. More...

#include <btOverlappingPairCache.h>

Inheritance diagram for btHashedOverlappingPairCache:
Inheritance graph
[legend]
Collaboration diagram for btHashedOverlappingPairCache:
Collaboration graph
[legend]

List of all members.

Public Member Functions

 btHashedOverlappingPairCache ()
virtual ~btHashedOverlappingPairCache ()
void removeOverlappingPairsContainingProxy (btBroadphaseProxy *proxy, btDispatcher *dispatcher)
virtual void * removeOverlappingPair (btBroadphaseProxy *proxy0, btBroadphaseProxy *proxy1, btDispatcher *dispatcher)
SIMD_FORCE_INLINE bool needsBroadphaseCollision (btBroadphaseProxy *proxy0, btBroadphaseProxy *proxy1) const
virtual btBroadphasePair * addOverlappingPair (btBroadphaseProxy *proxy0, btBroadphaseProxy *proxy1)
void cleanProxyFromPairs (btBroadphaseProxy *proxy, btDispatcher *dispatcher)
virtual void processAllOverlappingPairs (btOverlapCallback *, btDispatcher *dispatcher)
virtual btBroadphasePair * getOverlappingPairArrayPtr ()
const btBroadphasePair * getOverlappingPairArrayPtr () const
btBroadphasePairArraygetOverlappingPairArray ()
const btBroadphasePairArraygetOverlappingPairArray () const
void cleanOverlappingPair (btBroadphasePair &pair, btDispatcher *dispatcher)
btBroadphasePair * findPair (btBroadphaseProxy *proxy0, btBroadphaseProxy *proxy1)
int GetCount () const
btOverlapFilterCallbackgetOverlapFilterCallback ()
void setOverlapFilterCallback (btOverlapFilterCallback *callback)
int getNumOverlappingPairs () const

Public Attributes

btAlignedObjectArray< int > m_hashTable
btAlignedObjectArray< int > m_next

Private Member Functions

btBroadphasePair * internalAddPair (btBroadphaseProxy *proxy0, btBroadphaseProxy *proxy1)
void growTables ()
SIMD_FORCE_INLINE bool equalsPair (const btBroadphasePair &pair, int proxyId1, int proxyId2)
SIMD_FORCE_INLINE unsigned int getHash (unsigned int proxyId1, unsigned int proxyId2)
SIMD_FORCE_INLINE
btBroadphasePair * 
internalFindPair (btBroadphaseProxy *proxy0, btBroadphaseProxy *proxy1, int hash)
virtual bool hasDeferredRemoval ()

Private Attributes

btBroadphasePairArray m_overlappingPairArray
btOverlapFilterCallbackm_overlapFilterCallback
bool m_blockedForChanges

Detailed Description

Hash-space based Pair Cache, thanks to Erin Catto, Box2D, http://www.box2d.org, and Pierre Terdiman, Codercorner, http://codercorner.com.

Definition at line 88 of file btOverlappingPairCache.h.


Constructor & Destructor Documentation

Definition at line 32 of file btOverlappingPairCache.cpp.

                                                          :
       m_overlapFilterCallback(0),
       m_blockedForChanges(false)
{
       int initialAllocatedSize= 2;
       m_overlappingPairArray.reserve(initialAllocatedSize);
       growTables();
}

Here is the call graph for this function:

Definition at line 44 of file btOverlappingPairCache.cpp.

{
       //todo/test: show we erase/delete data, or is it automatic
}

Member Function Documentation

virtual btBroadphasePair* btHashedOverlappingPairCache::addOverlappingPair ( btBroadphaseProxy *  proxy0,
btBroadphaseProxy *  proxy1 
) [inline, virtual]

Implements btOverlappingPairCallback.

Definition at line 117 of file btOverlappingPairCache.h.

       {
              gAddedPairs++;

              if (!needsBroadphaseCollision(proxy0,proxy1))
                     return 0;

              return internalAddPair(proxy0,proxy1);
       }

Here is the call graph for this function:

void btHashedOverlappingPairCache::cleanOverlappingPair ( btBroadphasePair &  pair,
btDispatcher dispatcher 
) [virtual]

Implements btOverlappingPairCache.

Definition at line 51 of file btOverlappingPairCache.cpp.

{
       if (pair.m_algorithm)
       {
              {
                     pair.m_algorithm->~btCollisionAlgorithm();
                     dispatcher->freeCollisionAlgorithm(pair.m_algorithm);
                     pair.m_algorithm=0;
              }
       }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void btHashedOverlappingPairCache::cleanProxyFromPairs ( btBroadphaseProxy *  proxy,
btDispatcher dispatcher 
) [virtual]

Implements btOverlappingPairCache.

Definition at line 66 of file btOverlappingPairCache.cpp.

{

       class  CleanPairCallback : public btOverlapCallback
       {
              btBroadphaseProxy* m_cleanProxy;
              btOverlappingPairCache*     m_pairCache;
              btDispatcher* m_dispatcher;

       public:
              CleanPairCallback(btBroadphaseProxy* cleanProxy,btOverlappingPairCache* pairCache,btDispatcher* dispatcher)
                     :m_cleanProxy(cleanProxy),
                     m_pairCache(pairCache),
                     m_dispatcher(dispatcher)
              {
              }
              virtual       bool   processOverlap(btBroadphasePair& pair)
              {
                     if ((pair.m_pProxy0 == m_cleanProxy) ||
                            (pair.m_pProxy1 == m_cleanProxy))
                     {
                            m_pairCache->cleanOverlappingPair(pair,m_dispatcher);
                     }
                     return false;
              }
              
       };

       CleanPairCallback cleanPairs(proxy,this,dispatcher);

       processAllOverlappingPairs(&cleanPairs,dispatcher);

}

Here is the call graph for this function:

SIMD_FORCE_INLINE bool btHashedOverlappingPairCache::equalsPair ( const btBroadphasePair &  pair,
int  proxyId1,
int  proxyId2 
) [inline, private]

Definition at line 183 of file btOverlappingPairCache.h.

       {      
              return pair.m_pProxy0->getUid() == proxyId1 && pair.m_pProxy1->getUid() == proxyId2;
       }

Here is the caller graph for this function:

btBroadphasePair * btHashedOverlappingPairCache::findPair ( btBroadphaseProxy *  proxy0,
btBroadphaseProxy *  proxy1 
) [virtual]

Implements btOverlappingPairCache.

Definition at line 133 of file btOverlappingPairCache.cpp.

{
       gFindPairs++;

       int proxyId1 = proxy0->getUid();
       int proxyId2 = proxy1->getUid();

       if (proxyId1 > proxyId2) 
              btSwap(proxyId1, proxyId2);

       int hash = getHash(proxyId1, proxyId2) & (m_overlappingPairArray.capacity()-1);

       if (hash >= m_hashTable.size())
       {
              return NULL;
       }

       int index = m_hashTable[hash];
       while (index != BT_NULL_PAIR && equalsPair(m_overlappingPairArray[index], proxyId1, proxyId2) == false)
       {
              index = m_next[index];
       }

       if (index == BT_NULL_PAIR)
       {
              return NULL;
       }

       btAssert(index < m_overlappingPairArray.size());

       return &m_overlappingPairArray[index];
}

Here is the call graph for this function:

Definition at line 160 of file btOverlappingPairCache.h.

Here is the call graph for this function:

SIMD_FORCE_INLINE unsigned int btHashedOverlappingPairCache::getHash ( unsigned int  proxyId1,
unsigned int  proxyId2 
) [inline, private]

Definition at line 206 of file btOverlappingPairCache.h.

       {
              int key = ((unsigned int)proxyId1) | (((unsigned int)proxyId2) <<16);
              // Thomas Wang's hash

              key += ~(key << 15);
              key ^=  (key >> 10);
              key +=  (key << 3);
              key ^=  (key >> 6);
              key += ~(key << 11);
              key ^=  (key >> 16);
              return key;
       }

Here is the caller graph for this function:

Implements btOverlappingPairCache.

Definition at line 173 of file btOverlappingPairCache.h.

Here is the call graph for this function:

Definition at line 163 of file btOverlappingPairCache.h.

Implements btOverlappingPairCache.

Definition at line 144 of file btOverlappingPairCache.h.

Definition at line 149 of file btOverlappingPairCache.h.

virtual btBroadphasePair* btHashedOverlappingPairCache::getOverlappingPairArrayPtr ( ) [inline, virtual]

Implements btOverlappingPairCache.

Definition at line 134 of file btOverlappingPairCache.h.

       {
              return &m_overlappingPairArray[0];
       }
const btBroadphasePair* btHashedOverlappingPairCache::getOverlappingPairArrayPtr ( ) const [inline, virtual]

Implements btOverlappingPairCache.

Definition at line 139 of file btOverlappingPairCache.h.

       {
              return &m_overlappingPairArray[0];
       }

Definition at line 168 of file btOverlappingPairCache.cpp.

{

       int newCapacity = m_overlappingPairArray.capacity();

       if (m_hashTable.size() < newCapacity)
       {
              //grow hashtable and next table
              int curHashtableSize = m_hashTable.size();

              m_hashTable.resize(newCapacity);
              m_next.resize(newCapacity);


              int i;

              for (i= 0; i < newCapacity; ++i)
              {
                     m_hashTable[i] = BT_NULL_PAIR;
              }
              for (i = 0; i < newCapacity; ++i)
              {
                     m_next[i] = BT_NULL_PAIR;
              }

              for(i=0;i<curHashtableSize;i++)
              {
       
                     const btBroadphasePair& pair = m_overlappingPairArray[i];
                     int proxyId1 = pair.m_pProxy0->getUid();
                     int proxyId2 = pair.m_pProxy1->getUid();
                     if (proxyId1 > proxyId2) 
                            btSwap(proxyId1, proxyId2);
                     int    hashValue = getHash(proxyId1,proxyId2) & (m_overlappingPairArray.capacity()-1);     // New hash value with new mask
                     m_next[i] = m_hashTable[hashValue];
                     m_hashTable[hashValue] = i;
              }


       }
}

Here is the call graph for this function:

Here is the caller graph for this function:

virtual bool btHashedOverlappingPairCache::hasDeferredRemoval ( ) [inline, private, virtual]

Implements btOverlappingPairCache.

Definition at line 248 of file btOverlappingPairCache.h.

       {
              return false;
       }
btBroadphasePair * btHashedOverlappingPairCache::internalAddPair ( btBroadphaseProxy *  proxy0,
btBroadphaseProxy *  proxy1 
) [private]

Definition at line 210 of file btOverlappingPairCache.cpp.

{
       int proxyId1 = proxy0->getUid();
       int proxyId2 = proxy1->getUid();

       if (proxyId1 > proxyId2) 
              btSwap(proxyId1, proxyId2);

       int hash = getHash(proxyId1, proxyId2) & (m_overlappingPairArray.capacity()-1);

       

       btBroadphasePair* pair = internalFindPair(proxy0, proxy1, hash);
       if (pair != NULL)
       {
              return pair;
       }

       int count = m_overlappingPairArray.size();
       int oldCapacity = m_overlappingPairArray.capacity();
       void* mem = &m_overlappingPairArray.expand();
       int newCapacity = m_overlappingPairArray.capacity();

       if (oldCapacity < newCapacity)
       {
              growTables();
              //hash with new capacity
              hash = getHash(proxyId1, proxyId2) & (m_overlappingPairArray.capacity()-1);
       }
       
       pair = new (mem) btBroadphasePair(*proxy0,*proxy1);
//     pair->m_pProxy0 = proxy0;
//     pair->m_pProxy1 = proxy1;
       pair->m_algorithm = 0;
       pair->m_userInfo = 0;
       

       m_next[count] = m_hashTable[hash];
       m_hashTable[hash] = count;

       return pair;
}

Here is the call graph for this function:

Here is the caller graph for this function:

SIMD_FORCE_INLINE btBroadphasePair* btHashedOverlappingPairCache::internalFindPair ( btBroadphaseProxy *  proxy0,
btBroadphaseProxy *  proxy1,
int  hash 
) [inline, private]

Definition at line 224 of file btOverlappingPairCache.h.

       {
              int proxyId1 = proxy0->getUid();
              int proxyId2 = proxy1->getUid();
              if (proxyId1 > proxyId2) 
                     btSwap(proxyId1, proxyId2);

              int index = m_hashTable[hash];
              
              while( index != BT_NULL_PAIR && equalsPair(m_overlappingPairArray[index], proxyId1, proxyId2) == false)
              {
                     index = m_next[index];
              }

              if ( index == BT_NULL_PAIR )
              {
                     return NULL;
              }

              btAssert(index < m_overlappingPairArray.size());

              return &m_overlappingPairArray[index];
       }

Here is the call graph for this function:

Here is the caller graph for this function:

SIMD_FORCE_INLINE bool btHashedOverlappingPairCache::needsBroadphaseCollision ( btBroadphaseProxy *  proxy0,
btBroadphaseProxy *  proxy1 
) const [inline]

Definition at line 104 of file btOverlappingPairCache.h.

       {
              if (m_overlapFilterCallback)
                     return m_overlapFilterCallback->needBroadphaseCollision(proxy0,proxy1);

              bool collides = (proxy0->m_collisionFilterGroup & proxy1->m_collisionFilterMask) != 0;
              collides = collides && (proxy1->m_collisionFilterGroup & proxy0->m_collisionFilterMask);
              
              return collides;
       }

Here is the call graph for this function:

Here is the caller graph for this function:

Implements btOverlappingPairCache.

Definition at line 354 of file btOverlappingPairCache.cpp.

{

       int i;

//     printf("m_overlappingPairArray.size()=%d\n",m_overlappingPairArray.size());
       for (i=0;i<m_overlappingPairArray.size();)
       {
       
              btBroadphasePair* pair = &m_overlappingPairArray[i];
              if (callback->processOverlap(*pair))
              {
                     removeOverlappingPair(pair->m_pProxy0,pair->m_pProxy1,dispatcher);

                     gOverlappingPairs--;
              } else
              {
                     i++;
              }
       }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void * btHashedOverlappingPairCache::removeOverlappingPair ( btBroadphaseProxy *  proxy0,
btBroadphaseProxy *  proxy1,
btDispatcher dispatcher 
) [virtual]

Implements btOverlappingPairCallback.

Definition at line 255 of file btOverlappingPairCache.cpp.

{
       gRemovePairs++;

       int proxyId1 = proxy0->getUid();
       int proxyId2 = proxy1->getUid();

       if (proxyId1 > proxyId2) 
              btSwap(proxyId1, proxyId2);

       int hash = getHash(proxyId1, proxyId2) & (m_overlappingPairArray.capacity()-1);

       btBroadphasePair* pair = internalFindPair(proxy0, proxy1, hash);
       if (pair == NULL)
       {
              return 0;
       }

       cleanOverlappingPair(*pair,dispatcher);

       void* userData = pair->m_userInfo;

       btAssert(pair->m_pProxy0->getUid() == proxyId1);
       btAssert(pair->m_pProxy1->getUid() == proxyId2);

       int pairIndex = int(pair - &m_overlappingPairArray[0]);
       btAssert(pairIndex < m_overlappingPairArray.size());

       // Remove the pair from the hash table.
       int index = m_hashTable[hash];
       btAssert(index != BT_NULL_PAIR);

       int previous = BT_NULL_PAIR;
       while (index != pairIndex)
       {
              previous = index;
              index = m_next[index];
       }

       if (previous != BT_NULL_PAIR)
       {
              btAssert(m_next[previous] == pairIndex);
              m_next[previous] = m_next[pairIndex];
       }
       else
       {
              m_hashTable[hash] = m_next[pairIndex];
       }

       // We now move the last pair into spot of the
       // pair being removed. We need to fix the hash
       // table indices to support the move.

       int lastPairIndex = m_overlappingPairArray.size() - 1;

       // If the removed pair is the last pair, we are done.
       if (lastPairIndex == pairIndex)
       {
              m_overlappingPairArray.pop_back();
              return userData;
       }

       // Remove the last pair from the hash table.
       const btBroadphasePair* last = &m_overlappingPairArray[lastPairIndex];
       int lastHash = getHash(last->m_pProxy0->getUid(), last->m_pProxy1->getUid()) & (m_overlappingPairArray.capacity()-1);

       index = m_hashTable[lastHash];
       btAssert(index != BT_NULL_PAIR);

       previous = BT_NULL_PAIR;
       while (index != lastPairIndex)
       {
              previous = index;
              index = m_next[index];
       }

       if (previous != BT_NULL_PAIR)
       {
              btAssert(m_next[previous] == lastPairIndex);
              m_next[previous] = m_next[lastPairIndex];
       }
       else
       {
              m_hashTable[lastHash] = m_next[lastPairIndex];
       }

       // Copy the last pair into the remove pair's spot.
       m_overlappingPairArray[pairIndex] = m_overlappingPairArray[lastPairIndex];

       // Insert the last pair into the hash table
       m_next[pairIndex] = m_hashTable[lastHash];
       m_hashTable[lastHash] = pairIndex;

       m_overlappingPairArray.pop_back();

       return userData;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void btHashedOverlappingPairCache::removeOverlappingPairsContainingProxy ( btBroadphaseProxy *  proxy,
btDispatcher dispatcher 
) [virtual]

Implements btOverlappingPairCallback.

Definition at line 103 of file btOverlappingPairCache.cpp.

{

       class  RemovePairCallback : public btOverlapCallback
       {
              btBroadphaseProxy* m_obsoleteProxy;

       public:
              RemovePairCallback(btBroadphaseProxy* obsoleteProxy)
                     :m_obsoleteProxy(obsoleteProxy)
              {
              }
              virtual       bool   processOverlap(btBroadphasePair& pair)
              {
                     return ((pair.m_pProxy0 == m_obsoleteProxy) ||
                            (pair.m_pProxy1 == m_obsoleteProxy));
              }
              
       };


       RemovePairCallback removeCallback(proxy);

       processAllOverlappingPairs(&removeCallback,dispatcher);
}

Here is the call graph for this function:

Implements btOverlappingPairCache.

Definition at line 168 of file btOverlappingPairCache.h.

       {
              m_overlapFilterCallback = callback;
       }

Member Data Documentation

Definition at line 92 of file btOverlappingPairCache.h.

Definition at line 255 of file btOverlappingPairCache.h.

Definition at line 256 of file btOverlappingPairCache.h.

Definition at line 91 of file btOverlappingPairCache.h.

Definition at line 90 of file btOverlappingPairCache.h.


The documentation for this class was generated from the following files: