[1963] | 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 | #include "btSimpleBroadphase.h" |
---|
| 17 | #include "BulletCollision/BroadphaseCollision/btDispatcher.h" |
---|
| 18 | #include "BulletCollision/BroadphaseCollision/btCollisionAlgorithm.h" |
---|
| 19 | |
---|
| 20 | #include "LinearMath/btVector3.h" |
---|
| 21 | #include "LinearMath/btTransform.h" |
---|
| 22 | #include "LinearMath/btMatrix3x3.h" |
---|
| 23 | #include <new> |
---|
| 24 | |
---|
| 25 | extern int gOverlappingPairs; |
---|
| 26 | |
---|
| 27 | void btSimpleBroadphase::validate() |
---|
| 28 | { |
---|
| 29 | for (int i=0;i<m_numHandles;i++) |
---|
| 30 | { |
---|
| 31 | for (int j=i+1;j<m_numHandles;j++) |
---|
| 32 | { |
---|
| 33 | btAssert(&m_pHandles[i] != &m_pHandles[j]); |
---|
| 34 | } |
---|
| 35 | } |
---|
| 36 | |
---|
| 37 | } |
---|
| 38 | |
---|
| 39 | btSimpleBroadphase::btSimpleBroadphase(int maxProxies, btOverlappingPairCache* overlappingPairCache) |
---|
| 40 | :m_pairCache(overlappingPairCache), |
---|
| 41 | m_ownsPairCache(false), |
---|
| 42 | m_invalidPair(0) |
---|
| 43 | { |
---|
| 44 | |
---|
| 45 | if (!overlappingPairCache) |
---|
| 46 | { |
---|
| 47 | void* mem = btAlignedAlloc(sizeof(btHashedOverlappingPairCache),16); |
---|
| 48 | m_pairCache = new (mem)btHashedOverlappingPairCache(); |
---|
| 49 | m_ownsPairCache = true; |
---|
| 50 | } |
---|
| 51 | |
---|
| 52 | // allocate handles buffer and put all handles on free list |
---|
| 53 | m_pHandlesRawPtr = btAlignedAlloc(sizeof(btSimpleBroadphaseProxy)*maxProxies,16); |
---|
| 54 | m_pHandles = new(m_pHandlesRawPtr) btSimpleBroadphaseProxy[maxProxies]; |
---|
| 55 | m_maxHandles = maxProxies; |
---|
| 56 | m_numHandles = 0; |
---|
| 57 | m_firstFreeHandle = 0; |
---|
| 58 | |
---|
| 59 | |
---|
| 60 | { |
---|
| 61 | for (int i = m_firstFreeHandle; i < maxProxies; i++) |
---|
| 62 | { |
---|
| 63 | m_pHandles[i].SetNextFree(i + 1); |
---|
| 64 | m_pHandles[i].m_uniqueId = i+2;//any UID will do, we just avoid too trivial values (0,1) for debugging purposes |
---|
| 65 | } |
---|
| 66 | m_pHandles[maxProxies - 1].SetNextFree(0); |
---|
| 67 | |
---|
| 68 | } |
---|
| 69 | |
---|
| 70 | } |
---|
| 71 | |
---|
| 72 | btSimpleBroadphase::~btSimpleBroadphase() |
---|
| 73 | { |
---|
| 74 | btAlignedFree(m_pHandlesRawPtr); |
---|
| 75 | |
---|
| 76 | if (m_ownsPairCache) |
---|
| 77 | { |
---|
| 78 | m_pairCache->~btOverlappingPairCache(); |
---|
| 79 | btAlignedFree(m_pairCache); |
---|
| 80 | } |
---|
| 81 | } |
---|
| 82 | |
---|
| 83 | |
---|
| 84 | btBroadphaseProxy* btSimpleBroadphase::createProxy( const btVector3& aabbMin, const btVector3& aabbMax,int shapeType,void* userPtr ,short int collisionFilterGroup,short int collisionFilterMask, btDispatcher* /*dispatcher*/,void* multiSapProxy) |
---|
| 85 | { |
---|
| 86 | if (m_numHandles >= m_maxHandles) |
---|
| 87 | { |
---|
| 88 | btAssert(0); |
---|
| 89 | return 0; //should never happen, but don't let the game crash ;-) |
---|
| 90 | } |
---|
| 91 | btAssert(aabbMin[0]<= aabbMax[0] && aabbMin[1]<= aabbMax[1] && aabbMin[2]<= aabbMax[2]); |
---|
| 92 | |
---|
| 93 | int newHandleIndex = allocHandle(); |
---|
| 94 | btSimpleBroadphaseProxy* proxy = new (&m_pHandles[newHandleIndex])btSimpleBroadphaseProxy(aabbMin,aabbMax,shapeType,userPtr,collisionFilterGroup,collisionFilterMask,multiSapProxy); |
---|
| 95 | |
---|
| 96 | return proxy; |
---|
| 97 | } |
---|
| 98 | |
---|
| 99 | class RemovingOverlapCallback : public btOverlapCallback |
---|
| 100 | { |
---|
| 101 | protected: |
---|
| 102 | virtual bool processOverlap(btBroadphasePair& pair) |
---|
| 103 | { |
---|
| 104 | (void)pair; |
---|
| 105 | btAssert(0); |
---|
| 106 | return false; |
---|
| 107 | } |
---|
| 108 | }; |
---|
| 109 | |
---|
| 110 | class RemovePairContainingProxy |
---|
| 111 | { |
---|
| 112 | |
---|
| 113 | btBroadphaseProxy* m_targetProxy; |
---|
| 114 | public: |
---|
| 115 | virtual ~RemovePairContainingProxy() |
---|
| 116 | { |
---|
| 117 | } |
---|
| 118 | protected: |
---|
| 119 | virtual bool processOverlap(btBroadphasePair& pair) |
---|
| 120 | { |
---|
| 121 | btSimpleBroadphaseProxy* proxy0 = static_cast<btSimpleBroadphaseProxy*>(pair.m_pProxy0); |
---|
| 122 | btSimpleBroadphaseProxy* proxy1 = static_cast<btSimpleBroadphaseProxy*>(pair.m_pProxy1); |
---|
| 123 | |
---|
| 124 | return ((m_targetProxy == proxy0 || m_targetProxy == proxy1)); |
---|
| 125 | }; |
---|
| 126 | }; |
---|
| 127 | |
---|
| 128 | void btSimpleBroadphase::destroyProxy(btBroadphaseProxy* proxyOrg,btDispatcher* dispatcher) |
---|
| 129 | { |
---|
| 130 | |
---|
| 131 | btSimpleBroadphaseProxy* proxy0 = static_cast<btSimpleBroadphaseProxy*>(proxyOrg); |
---|
| 132 | freeHandle(proxy0); |
---|
| 133 | |
---|
| 134 | m_pairCache->removeOverlappingPairsContainingProxy(proxyOrg,dispatcher); |
---|
| 135 | |
---|
| 136 | //validate(); |
---|
| 137 | |
---|
| 138 | } |
---|
| 139 | |
---|
| 140 | void btSimpleBroadphase::getAabb(btBroadphaseProxy* proxy,btVector3& aabbMin, btVector3& aabbMax ) const |
---|
| 141 | { |
---|
| 142 | const btSimpleBroadphaseProxy* sbp = getSimpleProxyFromProxy(proxy); |
---|
| 143 | aabbMin = sbp->m_aabbMin; |
---|
| 144 | aabbMax = sbp->m_aabbMax; |
---|
| 145 | } |
---|
| 146 | |
---|
| 147 | void btSimpleBroadphase::setAabb(btBroadphaseProxy* proxy,const btVector3& aabbMin,const btVector3& aabbMax, btDispatcher* /*dispatcher*/) |
---|
| 148 | { |
---|
| 149 | btSimpleBroadphaseProxy* sbp = getSimpleProxyFromProxy(proxy); |
---|
| 150 | sbp->m_aabbMin = aabbMin; |
---|
| 151 | sbp->m_aabbMax = aabbMax; |
---|
| 152 | } |
---|
| 153 | |
---|
| 154 | void btSimpleBroadphase::rayTest(const btVector3& rayFrom,const btVector3& rayTo, btBroadphaseRayCallback& rayCallback) |
---|
| 155 | { |
---|
| 156 | for (int i=0;i<m_numHandles;i++) |
---|
| 157 | { |
---|
| 158 | btSimpleBroadphaseProxy* proxy = &m_pHandles[i]; |
---|
| 159 | rayCallback.process(proxy); |
---|
| 160 | } |
---|
| 161 | } |
---|
| 162 | |
---|
| 163 | |
---|
| 164 | |
---|
| 165 | |
---|
| 166 | |
---|
| 167 | |
---|
| 168 | |
---|
| 169 | bool btSimpleBroadphase::aabbOverlap(btSimpleBroadphaseProxy* proxy0,btSimpleBroadphaseProxy* proxy1) |
---|
| 170 | { |
---|
| 171 | return proxy0->m_aabbMin[0] <= proxy1->m_aabbMax[0] && proxy1->m_aabbMin[0] <= proxy0->m_aabbMax[0] && |
---|
| 172 | proxy0->m_aabbMin[1] <= proxy1->m_aabbMax[1] && proxy1->m_aabbMin[1] <= proxy0->m_aabbMax[1] && |
---|
| 173 | proxy0->m_aabbMin[2] <= proxy1->m_aabbMax[2] && proxy1->m_aabbMin[2] <= proxy0->m_aabbMax[2]; |
---|
| 174 | |
---|
| 175 | } |
---|
| 176 | |
---|
| 177 | |
---|
| 178 | |
---|
| 179 | //then remove non-overlapping ones |
---|
| 180 | class CheckOverlapCallback : public btOverlapCallback |
---|
| 181 | { |
---|
| 182 | public: |
---|
| 183 | virtual bool processOverlap(btBroadphasePair& pair) |
---|
| 184 | { |
---|
| 185 | return (!btSimpleBroadphase::aabbOverlap(static_cast<btSimpleBroadphaseProxy*>(pair.m_pProxy0),static_cast<btSimpleBroadphaseProxy*>(pair.m_pProxy1))); |
---|
| 186 | } |
---|
| 187 | }; |
---|
| 188 | |
---|
| 189 | void btSimpleBroadphase::calculateOverlappingPairs(btDispatcher* dispatcher) |
---|
| 190 | { |
---|
| 191 | //first check for new overlapping pairs |
---|
| 192 | int i,j; |
---|
| 193 | |
---|
| 194 | if (m_numHandles >= 0) |
---|
| 195 | { |
---|
| 196 | |
---|
| 197 | for (i=0;i<m_numHandles;i++) |
---|
| 198 | { |
---|
| 199 | btSimpleBroadphaseProxy* proxy0 = &m_pHandles[i]; |
---|
| 200 | |
---|
| 201 | for (j=i+1;j<m_numHandles;j++) |
---|
| 202 | { |
---|
| 203 | btSimpleBroadphaseProxy* proxy1 = &m_pHandles[j]; |
---|
| 204 | btAssert(proxy0 != proxy1); |
---|
| 205 | |
---|
| 206 | btSimpleBroadphaseProxy* p0 = getSimpleProxyFromProxy(proxy0); |
---|
| 207 | btSimpleBroadphaseProxy* p1 = getSimpleProxyFromProxy(proxy1); |
---|
| 208 | |
---|
| 209 | if (aabbOverlap(p0,p1)) |
---|
| 210 | { |
---|
| 211 | if ( !m_pairCache->findPair(proxy0,proxy1)) |
---|
| 212 | { |
---|
| 213 | m_pairCache->addOverlappingPair(proxy0,proxy1); |
---|
| 214 | } |
---|
| 215 | } else |
---|
| 216 | { |
---|
| 217 | if (!m_pairCache->hasDeferredRemoval()) |
---|
| 218 | { |
---|
| 219 | if ( m_pairCache->findPair(proxy0,proxy1)) |
---|
| 220 | { |
---|
| 221 | m_pairCache->removeOverlappingPair(proxy0,proxy1,dispatcher); |
---|
| 222 | } |
---|
| 223 | } |
---|
| 224 | } |
---|
| 225 | } |
---|
| 226 | } |
---|
| 227 | |
---|
| 228 | if (m_ownsPairCache && m_pairCache->hasDeferredRemoval()) |
---|
| 229 | { |
---|
| 230 | |
---|
| 231 | btBroadphasePairArray& overlappingPairArray = m_pairCache->getOverlappingPairArray(); |
---|
| 232 | |
---|
| 233 | //perform a sort, to find duplicates and to sort 'invalid' pairs to the end |
---|
| 234 | overlappingPairArray.quickSort(btBroadphasePairSortPredicate()); |
---|
| 235 | |
---|
| 236 | overlappingPairArray.resize(overlappingPairArray.size() - m_invalidPair); |
---|
| 237 | m_invalidPair = 0; |
---|
| 238 | |
---|
| 239 | |
---|
| 240 | btBroadphasePair previousPair; |
---|
| 241 | previousPair.m_pProxy0 = 0; |
---|
| 242 | previousPair.m_pProxy1 = 0; |
---|
| 243 | previousPair.m_algorithm = 0; |
---|
| 244 | |
---|
| 245 | |
---|
| 246 | for (i=0;i<overlappingPairArray.size();i++) |
---|
| 247 | { |
---|
| 248 | |
---|
| 249 | btBroadphasePair& pair = overlappingPairArray[i]; |
---|
| 250 | |
---|
| 251 | bool isDuplicate = (pair == previousPair); |
---|
| 252 | |
---|
| 253 | previousPair = pair; |
---|
| 254 | |
---|
| 255 | bool needsRemoval = false; |
---|
| 256 | |
---|
| 257 | if (!isDuplicate) |
---|
| 258 | { |
---|
| 259 | bool hasOverlap = testAabbOverlap(pair.m_pProxy0,pair.m_pProxy1); |
---|
| 260 | |
---|
| 261 | if (hasOverlap) |
---|
| 262 | { |
---|
| 263 | needsRemoval = false;//callback->processOverlap(pair); |
---|
| 264 | } else |
---|
| 265 | { |
---|
| 266 | needsRemoval = true; |
---|
| 267 | } |
---|
| 268 | } else |
---|
| 269 | { |
---|
| 270 | //remove duplicate |
---|
| 271 | needsRemoval = true; |
---|
| 272 | //should have no algorithm |
---|
| 273 | btAssert(!pair.m_algorithm); |
---|
| 274 | } |
---|
| 275 | |
---|
| 276 | if (needsRemoval) |
---|
| 277 | { |
---|
| 278 | m_pairCache->cleanOverlappingPair(pair,dispatcher); |
---|
| 279 | |
---|
| 280 | // m_overlappingPairArray.swap(i,m_overlappingPairArray.size()-1); |
---|
| 281 | // m_overlappingPairArray.pop_back(); |
---|
| 282 | pair.m_pProxy0 = 0; |
---|
| 283 | pair.m_pProxy1 = 0; |
---|
| 284 | m_invalidPair++; |
---|
| 285 | gOverlappingPairs--; |
---|
| 286 | } |
---|
| 287 | |
---|
| 288 | } |
---|
| 289 | |
---|
| 290 | ///if you don't like to skip the invalid pairs in the array, execute following code: |
---|
| 291 | #define CLEAN_INVALID_PAIRS 1 |
---|
| 292 | #ifdef CLEAN_INVALID_PAIRS |
---|
| 293 | |
---|
| 294 | //perform a sort, to sort 'invalid' pairs to the end |
---|
| 295 | overlappingPairArray.quickSort(btBroadphasePairSortPredicate()); |
---|
| 296 | |
---|
| 297 | overlappingPairArray.resize(overlappingPairArray.size() - m_invalidPair); |
---|
| 298 | m_invalidPair = 0; |
---|
| 299 | #endif//CLEAN_INVALID_PAIRS |
---|
| 300 | |
---|
| 301 | } |
---|
| 302 | } |
---|
| 303 | } |
---|
| 304 | |
---|
| 305 | |
---|
| 306 | bool btSimpleBroadphase::testAabbOverlap(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1) |
---|
| 307 | { |
---|
| 308 | btSimpleBroadphaseProxy* p0 = getSimpleProxyFromProxy(proxy0); |
---|
| 309 | btSimpleBroadphaseProxy* p1 = getSimpleProxyFromProxy(proxy1); |
---|
| 310 | return aabbOverlap(p0,p1); |
---|
| 311 | } |
---|
| 312 | |
---|
| 313 | |
---|
| 314 | |
---|