Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: code/branches/pickups/src/bullet/BulletCollision/BroadphaseCollision/btOverlappingPairCache.cpp @ 2921

Last change on this file since 2921 was 2662, checked in by rgrieder, 16 years ago

Merged presentation branch back to trunk.

  • Property svn:eol-style set to native
File size: 14.3 KB
Line 
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        m_ghostPairCallback(0)
38{
39        int initialAllocatedSize= 2;
40        m_overlappingPairArray.reserve(initialAllocatedSize);
41        growTables();
42}
43
44
45
46
47btHashedOverlappingPairCache::~btHashedOverlappingPairCache()
48{
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
242        //this is where we add an actual pair, so also call the 'ghost'
243        if (m_ghostPairCallback)
244                m_ghostPairCallback->addOverlappingPair(proxy0,proxy1);
245
246        int newCapacity = m_overlappingPairArray.capacity();
247
248        if (oldCapacity < newCapacity)
249        {
250                growTables();
251                //hash with new capacity
252                hash = static_cast<int>(getHash(static_cast<unsigned int>(proxyId1),static_cast<unsigned int>(proxyId2)) & (m_overlappingPairArray.capacity()-1));
253        }
254       
255        pair = new (mem) btBroadphasePair(*proxy0,*proxy1);
256//      pair->m_pProxy0 = proxy0;
257//      pair->m_pProxy1 = proxy1;
258        pair->m_algorithm = 0;
259        pair->m_internalTmpValue = 0;
260       
261
262        m_next[count] = m_hashTable[hash];
263        m_hashTable[hash] = count;
264
265        return pair;
266}
267
268
269
270void* btHashedOverlappingPairCache::removeOverlappingPair(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1,btDispatcher* dispatcher)
271{
272        gRemovePairs++;
273        if(proxy0>proxy1) btSwap(proxy0,proxy1);
274        int proxyId1 = proxy0->getUid();
275        int proxyId2 = proxy1->getUid();
276
277        /*if (proxyId1 > proxyId2)
278                btSwap(proxyId1, proxyId2);*/
279
280        int     hash = static_cast<int>(getHash(static_cast<unsigned int>(proxyId1),static_cast<unsigned int>(proxyId2)) & (m_overlappingPairArray.capacity()-1));
281
282        btBroadphasePair* pair = internalFindPair(proxy0, proxy1, hash);
283        if (pair == NULL)
284        {
285                return 0;
286        }
287
288        cleanOverlappingPair(*pair,dispatcher);
289
290        void* userData = pair->m_internalInfo1;
291
292        btAssert(pair->m_pProxy0->getUid() == proxyId1);
293        btAssert(pair->m_pProxy1->getUid() == proxyId2);
294
295        int pairIndex = int(pair - &m_overlappingPairArray[0]);
296        btAssert(pairIndex < m_overlappingPairArray.size());
297
298        // Remove the pair from the hash table.
299        int index = m_hashTable[hash];
300        btAssert(index != BT_NULL_PAIR);
301
302        int previous = BT_NULL_PAIR;
303        while (index != pairIndex)
304        {
305                previous = index;
306                index = m_next[index];
307        }
308
309        if (previous != BT_NULL_PAIR)
310        {
311                btAssert(m_next[previous] == pairIndex);
312                m_next[previous] = m_next[pairIndex];
313        }
314        else
315        {
316                m_hashTable[hash] = m_next[pairIndex];
317        }
318
319        // We now move the last pair into spot of the
320        // pair being removed. We need to fix the hash
321        // table indices to support the move.
322
323        int lastPairIndex = m_overlappingPairArray.size() - 1;
324
325        if (m_ghostPairCallback)
326                m_ghostPairCallback->removeOverlappingPair(proxy0, proxy1,dispatcher);
327
328        // If the removed pair is the last pair, we are done.
329        if (lastPairIndex == pairIndex)
330        {
331                m_overlappingPairArray.pop_back();
332                return userData;
333        }
334
335        // Remove the last pair from the hash table.
336        const btBroadphasePair* last = &m_overlappingPairArray[lastPairIndex];
337                /* missing swap here too, Nat. */ 
338        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));
339
340        index = m_hashTable[lastHash];
341        btAssert(index != BT_NULL_PAIR);
342
343        previous = BT_NULL_PAIR;
344        while (index != lastPairIndex)
345        {
346                previous = index;
347                index = m_next[index];
348        }
349
350        if (previous != BT_NULL_PAIR)
351        {
352                btAssert(m_next[previous] == lastPairIndex);
353                m_next[previous] = m_next[lastPairIndex];
354        }
355        else
356        {
357                m_hashTable[lastHash] = m_next[lastPairIndex];
358        }
359
360        // Copy the last pair into the remove pair's spot.
361        m_overlappingPairArray[pairIndex] = m_overlappingPairArray[lastPairIndex];
362
363        // Insert the last pair into the hash table
364        m_next[pairIndex] = m_hashTable[lastHash];
365        m_hashTable[lastHash] = pairIndex;
366
367        m_overlappingPairArray.pop_back();
368
369        return userData;
370}
371//#include <stdio.h>
372
373void    btHashedOverlappingPairCache::processAllOverlappingPairs(btOverlapCallback* callback,btDispatcher* dispatcher)
374{
375
376        int i;
377
378//      printf("m_overlappingPairArray.size()=%d\n",m_overlappingPairArray.size());
379        for (i=0;i<m_overlappingPairArray.size();)
380        {
381       
382                btBroadphasePair* pair = &m_overlappingPairArray[i];
383                if (callback->processOverlap(*pair))
384                {
385                        removeOverlappingPair(pair->m_pProxy0,pair->m_pProxy1,dispatcher);
386
387                        gOverlappingPairs--;
388                } else
389                {
390                        i++;
391                }
392        }
393}
394
395
396
397void*   btSortedOverlappingPairCache::removeOverlappingPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1, btDispatcher* dispatcher )
398{
399        if (!hasDeferredRemoval())
400        {
401                btBroadphasePair findPair(*proxy0,*proxy1);
402
403                int findIndex = m_overlappingPairArray.findLinearSearch(findPair);
404                if (findIndex < m_overlappingPairArray.size())
405                {
406                        gOverlappingPairs--;
407                        btBroadphasePair& pair = m_overlappingPairArray[findIndex];
408                        void* userData = pair.m_internalInfo1;
409                        cleanOverlappingPair(pair,dispatcher);
410                        if (m_ghostPairCallback)
411                                m_ghostPairCallback->removeOverlappingPair(proxy0, proxy1,dispatcher);
412                       
413                        m_overlappingPairArray.swap(findIndex,m_overlappingPairArray.capacity()-1);
414                        m_overlappingPairArray.pop_back();
415                        return userData;
416                }
417        }
418
419        return 0;
420}
421
422
423
424
425
426
427
428
429btBroadphasePair*       btSortedOverlappingPairCache::addOverlappingPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1)
430{
431        //don't add overlap with own
432        assert(proxy0 != proxy1);
433
434        if (!needsBroadphaseCollision(proxy0,proxy1))
435                return 0;
436       
437        void* mem = &m_overlappingPairArray.expand();
438        btBroadphasePair* pair = new (mem) btBroadphasePair(*proxy0,*proxy1);
439       
440        gOverlappingPairs++;
441        gAddedPairs++;
442       
443        if (m_ghostPairCallback)
444                m_ghostPairCallback->addOverlappingPair(proxy0, proxy1);
445        return pair;
446       
447}
448
449///this findPair becomes really slow. Either sort the list to speedup the query, or
450///use a different solution. It is mainly used for Removing overlapping pairs. Removal could be delayed.
451///we could keep a linked list in each proxy, and store pair in one of the proxies (with lowest memory address)
452///Also we can use a 2D bitmap, which can be useful for a future GPU implementation
453 btBroadphasePair*      btSortedOverlappingPairCache::findPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1)
454{
455        if (!needsBroadphaseCollision(proxy0,proxy1))
456                return 0;
457
458        btBroadphasePair tmpPair(*proxy0,*proxy1);
459        int findIndex = m_overlappingPairArray.findLinearSearch(tmpPair);
460
461        if (findIndex < m_overlappingPairArray.size())
462        {
463                //assert(it != m_overlappingPairSet.end());
464                 btBroadphasePair* pair = &m_overlappingPairArray[findIndex];
465                return pair;
466        }
467        return 0;
468}
469
470
471
472
473
474
475
476
477
478
479//#include <stdio.h>
480
481void    btSortedOverlappingPairCache::processAllOverlappingPairs(btOverlapCallback* callback,btDispatcher* dispatcher)
482{
483
484        int i;
485
486        for (i=0;i<m_overlappingPairArray.size();)
487        {
488       
489                btBroadphasePair* pair = &m_overlappingPairArray[i];
490                if (callback->processOverlap(*pair))
491                {
492                        cleanOverlappingPair(*pair,dispatcher);
493
494                        m_overlappingPairArray.swap(i,m_overlappingPairArray.capacity()-1);
495                        m_overlappingPairArray.pop_back();
496                        gOverlappingPairs--;
497                } else
498                {
499                        i++;
500                }
501        }
502}
503
504
505
506
507btSortedOverlappingPairCache::btSortedOverlappingPairCache():
508        m_blockedForChanges(false),
509        m_hasDeferredRemoval(true),
510        m_overlapFilterCallback(0),
511        m_ghostPairCallback(0)
512{
513        int initialAllocatedSize= 2;
514        m_overlappingPairArray.reserve(initialAllocatedSize);
515}
516
517btSortedOverlappingPairCache::~btSortedOverlappingPairCache()
518{
519}
520
521void    btSortedOverlappingPairCache::cleanOverlappingPair(btBroadphasePair& pair,btDispatcher* dispatcher)
522{
523        if (pair.m_algorithm)
524        {
525                {
526                        pair.m_algorithm->~btCollisionAlgorithm();
527                        dispatcher->freeCollisionAlgorithm(pair.m_algorithm);
528                        pair.m_algorithm=0;
529                        gRemovePairs--;
530                }
531        }
532}
533
534
535void    btSortedOverlappingPairCache::cleanProxyFromPairs(btBroadphaseProxy* proxy,btDispatcher* dispatcher)
536{
537
538        class   CleanPairCallback : public btOverlapCallback
539        {
540                btBroadphaseProxy* m_cleanProxy;
541                btOverlappingPairCache* m_pairCache;
542                btDispatcher* m_dispatcher;
543
544        public:
545                CleanPairCallback(btBroadphaseProxy* cleanProxy,btOverlappingPairCache* pairCache,btDispatcher* dispatcher)
546                        :m_cleanProxy(cleanProxy),
547                        m_pairCache(pairCache),
548                        m_dispatcher(dispatcher)
549                {
550                }
551                virtual bool    processOverlap(btBroadphasePair& pair)
552                {
553                        if ((pair.m_pProxy0 == m_cleanProxy) ||
554                                (pair.m_pProxy1 == m_cleanProxy))
555                        {
556                                m_pairCache->cleanOverlappingPair(pair,m_dispatcher);
557                        }
558                        return false;
559                }
560               
561        };
562
563        CleanPairCallback cleanPairs(proxy,this,dispatcher);
564
565        processAllOverlappingPairs(&cleanPairs,dispatcher);
566
567}
568
569
570void    btSortedOverlappingPairCache::removeOverlappingPairsContainingProxy(btBroadphaseProxy* proxy,btDispatcher* dispatcher)
571{
572
573        class   RemovePairCallback : public btOverlapCallback
574        {
575                btBroadphaseProxy* m_obsoleteProxy;
576
577        public:
578                RemovePairCallback(btBroadphaseProxy* obsoleteProxy)
579                        :m_obsoleteProxy(obsoleteProxy)
580                {
581                }
582                virtual bool    processOverlap(btBroadphasePair& pair)
583                {
584                        return ((pair.m_pProxy0 == m_obsoleteProxy) ||
585                                (pair.m_pProxy1 == m_obsoleteProxy));
586                }
587               
588        };
589
590        RemovePairCallback removeCallback(proxy);
591
592        processAllOverlappingPairs(&removeCallback,dispatcher);
593}
Note: See TracBrowser for help on using the repository browser.