Back to index

supertuxkart  0.5+dfsg1
btSimpleBroadphase.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 #include "btSimpleBroadphase.h"
00017 #include "BulletCollision/BroadphaseCollision/btDispatcher.h"
00018 #include "BulletCollision/BroadphaseCollision/btCollisionAlgorithm.h"
00019 
00020 #include "LinearMath/btVector3.h"
00021 #include "LinearMath/btTransform.h"
00022 #include "LinearMath/btMatrix3x3.h"
00023 #include <new>
00024 
00025 extern int gOverlappingPairs;
00026 
00027 void   btSimpleBroadphase::validate()
00028 {
00029        for (int i=0;i<m_numHandles;i++)
00030        {
00031               for (int j=i+1;j<m_numHandles;j++)
00032               {
00033                      btAssert(&m_pHandles[i] != &m_pHandles[j]);
00034               }
00035        }
00036        
00037 }
00038 
00039 btSimpleBroadphase::btSimpleBroadphase(int maxProxies, btOverlappingPairCache* overlappingPairCache)
00040        :m_pairCache(overlappingPairCache),
00041        m_ownsPairCache(false),
00042        m_invalidPair(0)
00043 {
00044 
00045        if (!overlappingPairCache)
00046        {
00047               void* mem = btAlignedAlloc(sizeof(btHashedOverlappingPairCache),16);
00048               m_pairCache = new (mem)btHashedOverlappingPairCache();
00049               m_ownsPairCache = true;
00050        }
00051 
00052        // allocate handles buffer and put all handles on free list
00053        void* ptr = btAlignedAlloc(sizeof(btSimpleBroadphaseProxy)*maxProxies,16);
00054        m_pHandles = new(ptr) btSimpleBroadphaseProxy[maxProxies];
00055        m_maxHandles = maxProxies;
00056        m_numHandles = 0;
00057        m_firstFreeHandle = 0;
00058        m_firstAllocatedHandle = -1;
00059 
00060        {
00061               for (int i = m_firstFreeHandle; i < maxProxies; i++)
00062               {
00063                      m_pHandles[i].SetNextFree(i + 1);
00064                      m_pHandles[i].m_uniqueId = i+2;//any UID will do, we just avoid too trivial values (0,1) for debugging purposes
00065                      m_pHandles[i].SetNextAllocated(-1);
00066               }
00067               m_pHandles[maxProxies - 1].SetNextFree(0);
00068               m_pHandles[maxProxies - 1].SetNextAllocated(-1);
00069        
00070        }
00071 
00072 }
00073 
00074 btSimpleBroadphase::~btSimpleBroadphase()
00075 {
00076        btAlignedFree(m_pHandles);
00077 
00078        if (m_ownsPairCache)
00079        {
00080               m_pairCache->~btOverlappingPairCache();
00081               btAlignedFree(m_pairCache);
00082        }
00083 }
00084 
00085 
00086 btBroadphaseProxy*   btSimpleBroadphase::createProxy(  const btVector3& aabbMin,  const btVector3& aabbMax,int shapeType,void* userPtr ,short int collisionFilterGroup,short int collisionFilterMask, btDispatcher* dispatcher,void* multiSapProxy)
00087 {
00088        if (m_numHandles >= m_maxHandles)
00089        {
00090               btAssert(0);
00091               return 0; //should never happen, but don't let the game crash ;-)
00092        }
00093        assert(aabbMin[0]<= aabbMax[0] && aabbMin[1]<= aabbMax[1] && aabbMin[2]<= aabbMax[2]);
00094 
00095        int newHandleIndex = allocHandle();
00096        btSimpleBroadphaseProxy* proxy = new (&m_pHandles[newHandleIndex])btSimpleBroadphaseProxy(aabbMin,aabbMax,shapeType,userPtr,collisionFilterGroup,collisionFilterMask,multiSapProxy);
00097 
00098        return proxy;
00099 }
00100 
00101 class  RemovingOverlapCallback : public btOverlapCallback
00102 {
00103 protected:
00104        virtual bool  processOverlap(btBroadphasePair& pair)
00105        {
00106               (void)pair;
00107               btAssert(0);
00108               return false;
00109        }
00110 };
00111 
00112 class RemovePairContainingProxy
00113 {
00114 
00115        btBroadphaseProxy*   m_targetProxy;
00116        public:
00117        virtual ~RemovePairContainingProxy()
00118        {
00119        }
00120 protected:
00121        virtual bool processOverlap(btBroadphasePair& pair)
00122        {
00123               btSimpleBroadphaseProxy* proxy0 = static_cast<btSimpleBroadphaseProxy*>(pair.m_pProxy0);
00124               btSimpleBroadphaseProxy* proxy1 = static_cast<btSimpleBroadphaseProxy*>(pair.m_pProxy1);
00125 
00126               return ((m_targetProxy == proxy0 || m_targetProxy == proxy1));
00127        };
00128 };
00129 
00130 void   btSimpleBroadphase::destroyProxy(btBroadphaseProxy* proxyOrg,btDispatcher* dispatcher)
00131 {
00132               
00133               btSimpleBroadphaseProxy* proxy0 = static_cast<btSimpleBroadphaseProxy*>(proxyOrg);
00134               freeHandle(proxy0);
00135 
00136               m_pairCache->removeOverlappingPairsContainingProxy(proxyOrg,dispatcher);
00137 
00138               //validate();
00139               
00140 }
00141 
00142 void   btSimpleBroadphase::setAabb(btBroadphaseProxy* proxy,const btVector3& aabbMin,const btVector3& aabbMax, btDispatcher* dispatcher)
00143 {
00144        btSimpleBroadphaseProxy* sbp = getSimpleProxyFromProxy(proxy);
00145        sbp->m_min = aabbMin;
00146        sbp->m_max = aabbMax;
00147 }
00148 
00149 
00150 
00151 
00152 
00153        
00154 
00155 
00156 
00157 bool   btSimpleBroadphase::aabbOverlap(btSimpleBroadphaseProxy* proxy0,btSimpleBroadphaseProxy* proxy1)
00158 {
00159        return proxy0->m_min[0] <= proxy1->m_max[0] && proxy1->m_min[0] <= proxy0->m_max[0] && 
00160                  proxy0->m_min[1] <= proxy1->m_max[1] && proxy1->m_min[1] <= proxy0->m_max[1] &&
00161                  proxy0->m_min[2] <= proxy1->m_max[2] && proxy1->m_min[2] <= proxy0->m_max[2];
00162 
00163 }
00164 
00165 
00166 
00167 //then remove non-overlapping ones
00168 class CheckOverlapCallback : public btOverlapCallback
00169 {
00170 public:
00171        virtual bool processOverlap(btBroadphasePair& pair)
00172        {
00173               return (!btSimpleBroadphase::aabbOverlap(static_cast<btSimpleBroadphaseProxy*>(pair.m_pProxy0),static_cast<btSimpleBroadphaseProxy*>(pair.m_pProxy1)));
00174        }
00175 };
00176 
00177 void   btSimpleBroadphase::calculateOverlappingPairs(btDispatcher* dispatcher)
00178 {
00179        //first check for new overlapping pairs
00180        int i,j;
00181 
00182        if (m_firstAllocatedHandle >= 0)
00183        {
00184 
00185               btSimpleBroadphaseProxy* proxy0 = &m_pHandles[m_firstAllocatedHandle];
00186 
00187               for (i=0;i<m_numHandles;i++)
00188               {
00189                      btSimpleBroadphaseProxy* proxy1 = &m_pHandles[m_firstAllocatedHandle];
00190 
00191                      for (j=0;j<m_numHandles;j++)
00192                      {
00193                             
00194                             if (proxy0 != proxy1)
00195                             {
00196                                    btSimpleBroadphaseProxy* p0 = getSimpleProxyFromProxy(proxy0);
00197                                    btSimpleBroadphaseProxy* p1 = getSimpleProxyFromProxy(proxy1);
00198 
00199                                    if (aabbOverlap(p0,p1))
00200                                    {
00201                                           if ( !m_pairCache->findPair(proxy0,proxy1))
00202                                           {
00203                                                  m_pairCache->addOverlappingPair(proxy0,proxy1);
00204                                           }
00205                                    } else
00206                                    {
00207                                    if (!m_pairCache->hasDeferredRemoval())
00208                                    {
00209                                           if ( m_pairCache->findPair(proxy0,proxy1))
00210                                           {
00211                                                  m_pairCache->removeOverlappingPair(proxy0,proxy1,dispatcher);
00212                                           }
00213                                    }
00214 
00215                                    }
00216                             }
00217                             proxy1 = &m_pHandles[proxy1->GetNextAllocated()];
00218 
00219                      }
00220                      proxy0 = &m_pHandles[proxy0->GetNextAllocated()];
00221 
00222               }
00223 
00224               if (m_ownsPairCache && m_pairCache->hasDeferredRemoval())
00225               {
00226                      
00227                      btBroadphasePairArray&      overlappingPairArray = m_pairCache->getOverlappingPairArray();
00228 
00229                      //perform a sort, to find duplicates and to sort 'invalid' pairs to the end
00230                      overlappingPairArray.quickSort(btBroadphasePairSortPredicate());
00231 
00232                      overlappingPairArray.resize(overlappingPairArray.size() - m_invalidPair);
00233                      m_invalidPair = 0;
00234 
00235 
00236                      btBroadphasePair previousPair;
00237                      previousPair.m_pProxy0 = 0;
00238                      previousPair.m_pProxy1 = 0;
00239                      previousPair.m_algorithm = 0;
00240                      
00241                      
00242                      for (i=0;i<overlappingPairArray.size();i++)
00243                      {
00244                      
00245                             btBroadphasePair& pair = overlappingPairArray[i];
00246 
00247                             bool isDuplicate = (pair == previousPair);
00248 
00249                             previousPair = pair;
00250 
00251                             bool needsRemoval = false;
00252 
00253                             if (!isDuplicate)
00254                             {
00255                                    bool hasOverlap = testAabbOverlap(pair.m_pProxy0,pair.m_pProxy1);
00256 
00257                                    if (hasOverlap)
00258                                    {
00259                                           needsRemoval = false;//callback->processOverlap(pair);
00260                                    } else
00261                                    {
00262                                           needsRemoval = true;
00263                                    }
00264                             } else
00265                             {
00266                                    //remove duplicate
00267                                    needsRemoval = true;
00268                                    //should have no algorithm
00269                                    btAssert(!pair.m_algorithm);
00270                             }
00271                             
00272                             if (needsRemoval)
00273                             {
00274                                    m_pairCache->cleanOverlappingPair(pair,dispatcher);
00275 
00276                      //            m_overlappingPairArray.swap(i,m_overlappingPairArray.size()-1);
00277                      //            m_overlappingPairArray.pop_back();
00278                                    pair.m_pProxy0 = 0;
00279                                    pair.m_pProxy1 = 0;
00280                                    m_invalidPair++;
00281                                    gOverlappingPairs--;
00282                             } 
00283                             
00284                      }
00285 
00287               #define CLEAN_INVALID_PAIRS 1
00288               #ifdef CLEAN_INVALID_PAIRS
00289 
00290                      //perform a sort, to sort 'invalid' pairs to the end
00291                      overlappingPairArray.quickSort(btBroadphasePairSortPredicate());
00292 
00293                      overlappingPairArray.resize(overlappingPairArray.size() - m_invalidPair);
00294                      m_invalidPair = 0;
00295               #endif//CLEAN_INVALID_PAIRS
00296 
00297               }
00298        }
00299 }
00300 
00301 
00302 bool btSimpleBroadphase::testAabbOverlap(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1)
00303 {
00304        btSimpleBroadphaseProxy* p0 = getSimpleProxyFromProxy(proxy0);
00305        btSimpleBroadphaseProxy* p1 = getSimpleProxyFromProxy(proxy1);
00306        return aabbOverlap(p0,p1);
00307 }
00308 
00309 
00310