Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: code/branches/physics/src/bullet/BulletCollision/BroadphaseCollision/btOverlappingPairCache.cpp @ 2379

Last change on this file since 2379 was 2192, checked in by rgrieder, 16 years ago

Reverted all changes of attempt to update physics branch.

  • Property svn:eol-style set to native
File size: 14.0 KB
RevLine 
[1963]1/*
2Bullet Continuous Collision Detection and Physics Library
3Copyright (c) 2003-2006 Erwin Coumans  http://continuousphysics.com/Bullet/
4
5This software is provided 'as-is', without any express or implied warranty.
6In no event will the authors be held liable for any damages arising from the use of this software.
7Permission is granted to anyone to use this software for any purpose,
8including commercial applications, and to alter it and redistribute it freely,
9subject to the following restrictions:
10
111. 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.
122. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
133. This notice may not be removed or altered from any source distribution.
14*/
15
16
17
18#include "btOverlappingPairCache.h"
19
20#include "btDispatcher.h"
21#include "btCollisionAlgorithm.h"
22
23#include <stdio.h>
24
25int     gOverlappingPairs = 0;
26
27int gRemovePairs =0;
28int gAddedPairs =0;
29int gFindPairs =0;
30
31
32
33
34btHashedOverlappingPairCache::btHashedOverlappingPairCache():
35        m_overlapFilterCallback(0),
36        m_blockedForChanges(false)
37{
38        int initialAllocatedSize= 2;
39        m_overlappingPairArray.reserve(initialAllocatedSize);
40        growTables();
41}
42
43
44
45
46btHashedOverlappingPairCache::~btHashedOverlappingPairCache()
47{
48        //todo/test: show we erase/delete data, or is it automatic
49}
50
51
52
53void    btHashedOverlappingPairCache::cleanOverlappingPair(btBroadphasePair& pair,btDispatcher* dispatcher)
54{
55        if (pair.m_algorithm)
56        {
57                {
58                        pair.m_algorithm->~btCollisionAlgorithm();
59                        dispatcher->freeCollisionAlgorithm(pair.m_algorithm);
60                        pair.m_algorithm=0;
61                }
62        }
63}
64
65
66
67
68void    btHashedOverlappingPairCache::cleanProxyFromPairs(btBroadphaseProxy* proxy,btDispatcher* dispatcher)
69{
70
71        class   CleanPairCallback : public btOverlapCallback
72        {
73                btBroadphaseProxy* m_cleanProxy;
74                btOverlappingPairCache* m_pairCache;
75                btDispatcher* m_dispatcher;
76
77        public:
78                CleanPairCallback(btBroadphaseProxy* cleanProxy,btOverlappingPairCache* pairCache,btDispatcher* dispatcher)
79                        :m_cleanProxy(cleanProxy),
80                        m_pairCache(pairCache),
81                        m_dispatcher(dispatcher)
82                {
83                }
84                virtual bool    processOverlap(btBroadphasePair& pair)
85                {
86                        if ((pair.m_pProxy0 == m_cleanProxy) ||
87                                (pair.m_pProxy1 == m_cleanProxy))
88                        {
89                                m_pairCache->cleanOverlappingPair(pair,m_dispatcher);
90                        }
91                        return false;
92                }
93               
94        };
95
96        CleanPairCallback cleanPairs(proxy,this,dispatcher);
97
98        processAllOverlappingPairs(&cleanPairs,dispatcher);
99
100}
101
102
103
104
105void    btHashedOverlappingPairCache::removeOverlappingPairsContainingProxy(btBroadphaseProxy* proxy,btDispatcher* dispatcher)
106{
107
108        class   RemovePairCallback : public btOverlapCallback
109        {
110                btBroadphaseProxy* m_obsoleteProxy;
111
112        public:
113                RemovePairCallback(btBroadphaseProxy* obsoleteProxy)
114                        :m_obsoleteProxy(obsoleteProxy)
115                {
116                }
117                virtual bool    processOverlap(btBroadphasePair& pair)
118                {
119                        return ((pair.m_pProxy0 == m_obsoleteProxy) ||
120                                (pair.m_pProxy1 == m_obsoleteProxy));
121                }
122               
123        };
124
125
126        RemovePairCallback removeCallback(proxy);
127
128        processAllOverlappingPairs(&removeCallback,dispatcher);
129}
130
131
132
133
134
135btBroadphasePair* btHashedOverlappingPairCache::findPair(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1)
136{
137        gFindPairs++;
138        if(proxy0>proxy1) btSwap(proxy0,proxy1);
139        int proxyId1 = proxy0->getUid();
140        int proxyId2 = proxy1->getUid();
141
142        /*if (proxyId1 > proxyId2)
143                btSwap(proxyId1, proxyId2);*/
144
145        int hash = static_cast<int>(getHash(static_cast<unsigned int>(proxyId1), static_cast<unsigned int>(proxyId2)) & (m_overlappingPairArray.capacity()-1));
146
147        if (hash >= m_hashTable.size())
148        {
149                return NULL;
150        }
151
152        int index = m_hashTable[hash];
153        while (index != BT_NULL_PAIR && equalsPair(m_overlappingPairArray[index], proxyId1, proxyId2) == false)
154        {
155                index = m_next[index];
156        }
157
158        if (index == BT_NULL_PAIR)
159        {
160                return NULL;
161        }
162
163        btAssert(index < m_overlappingPairArray.size());
164
165        return &m_overlappingPairArray[index];
166}
167
168//#include <stdio.h>
169
170void    btHashedOverlappingPairCache::growTables()
171{
172
173        int newCapacity = m_overlappingPairArray.capacity();
174
175        if (m_hashTable.size() < newCapacity)
176        {
177                //grow hashtable and next table
178                int curHashtableSize = m_hashTable.size();
179
180                m_hashTable.resize(newCapacity);
181                m_next.resize(newCapacity);
182
183
184                int i;
185
186                for (i= 0; i < newCapacity; ++i)
187                {
188                        m_hashTable[i] = BT_NULL_PAIR;
189                }
190                for (i = 0; i < newCapacity; ++i)
191                {
192                        m_next[i] = BT_NULL_PAIR;
193                }
194
195                for(i=0;i<curHashtableSize;i++)
196                {
197       
198                        const btBroadphasePair& pair = m_overlappingPairArray[i];
199                        int proxyId1 = pair.m_pProxy0->getUid();
200                        int proxyId2 = pair.m_pProxy1->getUid();
201                        /*if (proxyId1 > proxyId2)
202                                btSwap(proxyId1, proxyId2);*/
203                        int     hashValue = static_cast<int>(getHash(static_cast<unsigned int>(proxyId1),static_cast<unsigned int>(proxyId2)) & (m_overlappingPairArray.capacity()-1)); // New hash value with new mask
204                        m_next[i] = m_hashTable[hashValue];
205                        m_hashTable[hashValue] = i;
206                }
207
208
209        }
210}
211
212btBroadphasePair* btHashedOverlappingPairCache::internalAddPair(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1)
213{
214        if(proxy0>proxy1) btSwap(proxy0,proxy1);
215        int proxyId1 = proxy0->getUid();
216        int proxyId2 = proxy1->getUid();
217
218        /*if (proxyId1 > proxyId2)
219                btSwap(proxyId1, proxyId2);*/
220
221        int     hash = static_cast<int>(getHash(static_cast<unsigned int>(proxyId1),static_cast<unsigned int>(proxyId2)) & (m_overlappingPairArray.capacity()-1));      // New hash value with new mask
222
223
224        btBroadphasePair* pair = internalFindPair(proxy0, proxy1, hash);
225        if (pair != NULL)
226        {
227                return pair;
228        }
229        /*for(int i=0;i<m_overlappingPairArray.size();++i)
230                {
231                if(     (m_overlappingPairArray[i].m_pProxy0==proxy0)&&
232                        (m_overlappingPairArray[i].m_pProxy1==proxy1))
233                        {
234                        printf("Adding duplicated %u<>%u\r\n",proxyId1,proxyId2);
235                        internalFindPair(proxy0, proxy1, hash);
236                        }
237                }*/
238        int count = m_overlappingPairArray.size();
239        int oldCapacity = m_overlappingPairArray.capacity();
240        void* mem = &m_overlappingPairArray.expand();
241        int newCapacity = m_overlappingPairArray.capacity();
242
243        if (oldCapacity < newCapacity)
244        {
245                growTables();
246                //hash with new capacity
247                hash = static_cast<int>(getHash(static_cast<unsigned int>(proxyId1),static_cast<unsigned int>(proxyId2)) & (m_overlappingPairArray.capacity()-1));
248        }
249       
250        pair = new (mem) btBroadphasePair(*proxy0,*proxy1);
251//      pair->m_pProxy0 = proxy0;
252//      pair->m_pProxy1 = proxy1;
253        pair->m_algorithm = 0;
254        pair->m_userInfo = 0;
255       
256
257        m_next[count] = m_hashTable[hash];
258        m_hashTable[hash] = count;
259
260        return pair;
261}
262
263
264
265void* btHashedOverlappingPairCache::removeOverlappingPair(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1,btDispatcher* dispatcher)
266{
267        gRemovePairs++;
268        if(proxy0>proxy1) btSwap(proxy0,proxy1);
269        int proxyId1 = proxy0->getUid();
270        int proxyId2 = proxy1->getUid();
271
272        /*if (proxyId1 > proxyId2)
273                btSwap(proxyId1, proxyId2);*/
274
275        int     hash = static_cast<int>(getHash(static_cast<unsigned int>(proxyId1),static_cast<unsigned int>(proxyId2)) & (m_overlappingPairArray.capacity()-1));
276
277        btBroadphasePair* pair = internalFindPair(proxy0, proxy1, hash);
278        if (pair == NULL)
279        {
280                return 0;
281        }
282
283        cleanOverlappingPair(*pair,dispatcher);
284
285        void* userData = pair->m_userInfo;
286
287        btAssert(pair->m_pProxy0->getUid() == proxyId1);
288        btAssert(pair->m_pProxy1->getUid() == proxyId2);
289
290        int pairIndex = int(pair - &m_overlappingPairArray[0]);
291        btAssert(pairIndex < m_overlappingPairArray.size());
292
293        // Remove the pair from the hash table.
294        int index = m_hashTable[hash];
295        btAssert(index != BT_NULL_PAIR);
296
297        int previous = BT_NULL_PAIR;
298        while (index != pairIndex)
299        {
300                previous = index;
301                index = m_next[index];
302        }
303
304        if (previous != BT_NULL_PAIR)
305        {
306                btAssert(m_next[previous] == pairIndex);
307                m_next[previous] = m_next[pairIndex];
308        }
309        else
310        {
311                m_hashTable[hash] = m_next[pairIndex];
312        }
313
314        // We now move the last pair into spot of the
315        // pair being removed. We need to fix the hash
316        // table indices to support the move.
317
318        int lastPairIndex = m_overlappingPairArray.size() - 1;
319
320        // If the removed pair is the last pair, we are done.
321        if (lastPairIndex == pairIndex)
322        {
323                m_overlappingPairArray.pop_back();
324                return userData;
325        }
326
327        // Remove the last pair from the hash table.
328        const btBroadphasePair* last = &m_overlappingPairArray[lastPairIndex];
329                /* missing swap here too, Nat. */ 
330        int lastHash = static_cast<int>(getHash(static_cast<unsigned int>(last->m_pProxy0->getUid()), static_cast<unsigned int>(last->m_pProxy1->getUid())) & (m_overlappingPairArray.capacity()-1));
331
332        index = m_hashTable[lastHash];
333        btAssert(index != BT_NULL_PAIR);
334
335        previous = BT_NULL_PAIR;
336        while (index != lastPairIndex)
337        {
338                previous = index;
339                index = m_next[index];
340        }
341
342        if (previous != BT_NULL_PAIR)
343        {
344                btAssert(m_next[previous] == lastPairIndex);
345                m_next[previous] = m_next[lastPairIndex];
346        }
347        else
348        {
349                m_hashTable[lastHash] = m_next[lastPairIndex];
350        }
351
352        // Copy the last pair into the remove pair's spot.
353        m_overlappingPairArray[pairIndex] = m_overlappingPairArray[lastPairIndex];
354
355        // Insert the last pair into the hash table
356        m_next[pairIndex] = m_hashTable[lastHash];
357        m_hashTable[lastHash] = pairIndex;
358
359        m_overlappingPairArray.pop_back();
360
361        return userData;
362}
363//#include <stdio.h>
364
365void    btHashedOverlappingPairCache::processAllOverlappingPairs(btOverlapCallback* callback,btDispatcher* dispatcher)
366{
367
368        int i;
369
370//      printf("m_overlappingPairArray.size()=%d\n",m_overlappingPairArray.size());
371        for (i=0;i<m_overlappingPairArray.size();)
372        {
373       
374                btBroadphasePair* pair = &m_overlappingPairArray[i];
375                if (callback->processOverlap(*pair))
376                {
377                        removeOverlappingPair(pair->m_pProxy0,pair->m_pProxy1,dispatcher);
378
379                        gOverlappingPairs--;
380                } else
381                {
382                        i++;
383                }
384        }
385}
386
387
388
389void*   btSortedOverlappingPairCache::removeOverlappingPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1, btDispatcher* dispatcher )
390{
391        if (!hasDeferredRemoval())
392        {
393                btBroadphasePair findPair(*proxy0,*proxy1);
394
395                int findIndex = m_overlappingPairArray.findLinearSearch(findPair);
396                if (findIndex < m_overlappingPairArray.size())
397                {
398                        gOverlappingPairs--;
399                        btBroadphasePair& pair = m_overlappingPairArray[findIndex];
400                        void* userData = pair.m_userInfo;
401                        cleanOverlappingPair(pair,dispatcher);
402                       
403                        m_overlappingPairArray.swap(findIndex,m_overlappingPairArray.capacity()-1);
404                        m_overlappingPairArray.pop_back();
405                        return userData;
406                }
407        }
408
409        return 0;
410}
411
412
413
414
415
416
417
418
419btBroadphasePair*       btSortedOverlappingPairCache::addOverlappingPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1)
420{
421        //don't add overlap with own
422        assert(proxy0 != proxy1);
423
424        if (!needsBroadphaseCollision(proxy0,proxy1))
425                return 0;
426       
427        void* mem = &m_overlappingPairArray.expand();
428        btBroadphasePair* pair = new (mem) btBroadphasePair(*proxy0,*proxy1);
429        gOverlappingPairs++;
430        gAddedPairs++;
431        return pair;
432       
433}
434
435///this findPair becomes really slow. Either sort the list to speedup the query, or
436///use a different solution. It is mainly used for Removing overlapping pairs. Removal could be delayed.
437///we could keep a linked list in each proxy, and store pair in one of the proxies (with lowest memory address)
438///Also we can use a 2D bitmap, which can be useful for a future GPU implementation
439 btBroadphasePair*      btSortedOverlappingPairCache::findPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1)
440{
441        if (!needsBroadphaseCollision(proxy0,proxy1))
442                return 0;
443
444        btBroadphasePair tmpPair(*proxy0,*proxy1);
445        int findIndex = m_overlappingPairArray.findLinearSearch(tmpPair);
446
447        if (findIndex < m_overlappingPairArray.size())
448        {
449                //assert(it != m_overlappingPairSet.end());
450                 btBroadphasePair* pair = &m_overlappingPairArray[findIndex];
451                return pair;
452        }
453        return 0;
454}
455
456
457
458
459
460
461
462
463
464
465//#include <stdio.h>
466
467void    btSortedOverlappingPairCache::processAllOverlappingPairs(btOverlapCallback* callback,btDispatcher* dispatcher)
468{
469
470        int i;
471
472        for (i=0;i<m_overlappingPairArray.size();)
473        {
474       
475                btBroadphasePair* pair = &m_overlappingPairArray[i];
476                if (callback->processOverlap(*pair))
477                {
478                        cleanOverlappingPair(*pair,dispatcher);
479
480                        m_overlappingPairArray.swap(i,m_overlappingPairArray.capacity()-1);
481                        m_overlappingPairArray.pop_back();
482                        gOverlappingPairs--;
483                } else
484                {
485                        i++;
486                }
487        }
488}
489
490
491
492
493btSortedOverlappingPairCache::btSortedOverlappingPairCache():
494        m_blockedForChanges(false),
495        m_hasDeferredRemoval(true),
496        m_overlapFilterCallback(0)
497{
498        int initialAllocatedSize= 2;
499        m_overlappingPairArray.reserve(initialAllocatedSize);
500}
501
502btSortedOverlappingPairCache::~btSortedOverlappingPairCache()
503{
504        //todo/test: show we erase/delete data, or is it automatic
505}
506
507void    btSortedOverlappingPairCache::cleanOverlappingPair(btBroadphasePair& pair,btDispatcher* dispatcher)
508{
509        if (pair.m_algorithm)
510        {
511                {
512                        pair.m_algorithm->~btCollisionAlgorithm();
513                        dispatcher->freeCollisionAlgorithm(pair.m_algorithm);
514                        pair.m_algorithm=0;
515                        gRemovePairs--;
516                }
517        }
518}
519
520
521void    btSortedOverlappingPairCache::cleanProxyFromPairs(btBroadphaseProxy* proxy,btDispatcher* dispatcher)
522{
523
524        class   CleanPairCallback : public btOverlapCallback
525        {
526                btBroadphaseProxy* m_cleanProxy;
527                btOverlappingPairCache* m_pairCache;
528                btDispatcher* m_dispatcher;
529
530        public:
531                CleanPairCallback(btBroadphaseProxy* cleanProxy,btOverlappingPairCache* pairCache,btDispatcher* dispatcher)
532                        :m_cleanProxy(cleanProxy),
533                        m_pairCache(pairCache),
534                        m_dispatcher(dispatcher)
535                {
536                }
537                virtual bool    processOverlap(btBroadphasePair& pair)
538                {
539                        if ((pair.m_pProxy0 == m_cleanProxy) ||
540                                (pair.m_pProxy1 == m_cleanProxy))
541                        {
542                                m_pairCache->cleanOverlappingPair(pair,m_dispatcher);
543                        }
544                        return false;
545                }
546               
547        };
548
549        CleanPairCallback cleanPairs(proxy,this,dispatcher);
550
551        processAllOverlappingPairs(&cleanPairs,dispatcher);
552
553}
554
555
556void    btSortedOverlappingPairCache::removeOverlappingPairsContainingProxy(btBroadphaseProxy* proxy,btDispatcher* dispatcher)
557{
558
559        class   RemovePairCallback : public btOverlapCallback
560        {
561                btBroadphaseProxy* m_obsoleteProxy;
562
563        public:
564                RemovePairCallback(btBroadphaseProxy* obsoleteProxy)
565                        :m_obsoleteProxy(obsoleteProxy)
566                {
567                }
568                virtual bool    processOverlap(btBroadphasePair& pair)
569                {
570                        return ((pair.m_pProxy0 == m_obsoleteProxy) ||
571                                (pair.m_pProxy1 == m_obsoleteProxy));
572                }
573               
574        };
575
576        RemovePairCallback removeCallback(proxy);
577
578        processAllOverlappingPairs(&removeCallback,dispatcher);
579}
Note: See TracBrowser for help on using the repository browser.