Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: code/trunk/src/external/bullet/BulletCollision/BroadphaseCollision/btOverlappingPairCache.h @ 8577

Last change on this file since 8577 was 8393, checked in by rgrieder, 14 years ago

Updated Bullet from v2.77 to v2.78.
(I'm not going to make a branch for that since the update from 2.74 to 2.77 hasn't been tested that much either).

You will HAVE to do a complete RECOMPILE! I tested with MSVC and MinGW and they both threw linker errors at me.

  • Property svn:eol-style set to native
File size: 12.2 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#ifndef BT_OVERLAPPING_PAIR_CACHE_H
17#define BT_OVERLAPPING_PAIR_CACHE_H
18
19
20#include "btBroadphaseInterface.h"
21#include "btBroadphaseProxy.h"
22#include "btOverlappingPairCallback.h"
23
24#include "LinearMath/btAlignedObjectArray.h"
25class btDispatcher;
26
27typedef btAlignedObjectArray<btBroadphasePair>  btBroadphasePairArray;
28
29struct  btOverlapCallback
30{
31        virtual ~btOverlapCallback()
32        {}
33        //return true for deletion of the pair
34        virtual bool    processOverlap(btBroadphasePair& pair) = 0;
35
36};
37
38struct btOverlapFilterCallback
39{
40        virtual ~btOverlapFilterCallback()
41        {}
42        // return true when pairs need collision
43        virtual bool    needBroadphaseCollision(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1) const = 0;
44};
45
46
47
48
49
50
51
52extern int gRemovePairs;
53extern int gAddedPairs;
54extern int gFindPairs;
55
56const int BT_NULL_PAIR=0xffffffff;
57
58///The btOverlappingPairCache provides an interface for overlapping pair management (add, remove, storage), used by the btBroadphaseInterface broadphases.
59///The btHashedOverlappingPairCache and btSortedOverlappingPairCache classes are two implementations.
60class btOverlappingPairCache : public btOverlappingPairCallback
61{
62public:
63        virtual ~btOverlappingPairCache() {} // this is needed so we can get to the derived class destructor
64
65        virtual btBroadphasePair*       getOverlappingPairArrayPtr() = 0;
66       
67        virtual const btBroadphasePair* getOverlappingPairArrayPtr() const = 0;
68
69        virtual btBroadphasePairArray&  getOverlappingPairArray() = 0;
70
71        virtual void    cleanOverlappingPair(btBroadphasePair& pair,btDispatcher* dispatcher) = 0;
72
73        virtual int getNumOverlappingPairs() const = 0;
74
75        virtual void    cleanProxyFromPairs(btBroadphaseProxy* proxy,btDispatcher* dispatcher) = 0;
76
77        virtual void setOverlapFilterCallback(btOverlapFilterCallback* callback) = 0;
78
79        virtual void    processAllOverlappingPairs(btOverlapCallback*,btDispatcher* dispatcher) = 0;
80
81        virtual btBroadphasePair* findPair(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1) = 0;
82
83        virtual bool    hasDeferredRemoval() = 0;
84
85        virtual void    setInternalGhostPairCallback(btOverlappingPairCallback* ghostPairCallback)=0;
86
87        virtual void    sortOverlappingPairs(btDispatcher* dispatcher) = 0;
88
89
90};
91
92/// Hash-space based Pair Cache, thanks to Erin Catto, Box2D, http://www.box2d.org, and Pierre Terdiman, Codercorner, http://codercorner.com
93class btHashedOverlappingPairCache : public btOverlappingPairCache
94{
95        btBroadphasePairArray   m_overlappingPairArray;
96        btOverlapFilterCallback* m_overlapFilterCallback;
97        bool            m_blockedForChanges;
98
99
100public:
101        btHashedOverlappingPairCache();
102        virtual ~btHashedOverlappingPairCache();
103
104       
105        void    removeOverlappingPairsContainingProxy(btBroadphaseProxy* proxy,btDispatcher* dispatcher);
106
107        virtual void*   removeOverlappingPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1,btDispatcher* dispatcher);
108       
109        SIMD_FORCE_INLINE bool needsBroadphaseCollision(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1) const
110        {
111                if (m_overlapFilterCallback)
112                        return m_overlapFilterCallback->needBroadphaseCollision(proxy0,proxy1);
113
114                bool collides = (proxy0->m_collisionFilterGroup & proxy1->m_collisionFilterMask) != 0;
115                collides = collides && (proxy1->m_collisionFilterGroup & proxy0->m_collisionFilterMask);
116               
117                return collides;
118        }
119
120        // Add a pair and return the new pair. If the pair already exists,
121        // no new pair is created and the old one is returned.
122        virtual btBroadphasePair*       addOverlappingPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1)
123        {
124                gAddedPairs++;
125
126                if (!needsBroadphaseCollision(proxy0,proxy1))
127                        return 0;
128
129                return internalAddPair(proxy0,proxy1);
130        }
131
132       
133
134        void    cleanProxyFromPairs(btBroadphaseProxy* proxy,btDispatcher* dispatcher);
135
136       
137        virtual void    processAllOverlappingPairs(btOverlapCallback*,btDispatcher* dispatcher);
138
139        virtual btBroadphasePair*       getOverlappingPairArrayPtr()
140        {
141                return &m_overlappingPairArray[0];
142        }
143
144        const btBroadphasePair* getOverlappingPairArrayPtr() const
145        {
146                return &m_overlappingPairArray[0];
147        }
148
149        btBroadphasePairArray&  getOverlappingPairArray()
150        {
151                return m_overlappingPairArray;
152        }
153
154        const btBroadphasePairArray&    getOverlappingPairArray() const
155        {
156                return m_overlappingPairArray;
157        }
158
159        void    cleanOverlappingPair(btBroadphasePair& pair,btDispatcher* dispatcher);
160
161
162
163        btBroadphasePair* findPair(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1);
164
165        int GetCount() const { return m_overlappingPairArray.size(); }
166//      btBroadphasePair* GetPairs() { return m_pairs; }
167
168        btOverlapFilterCallback* getOverlapFilterCallback()
169        {
170                return m_overlapFilterCallback;
171        }
172
173        void setOverlapFilterCallback(btOverlapFilterCallback* callback)
174        {
175                m_overlapFilterCallback = callback;
176        }
177
178        int     getNumOverlappingPairs() const
179        {
180                return m_overlappingPairArray.size();
181        }
182private:
183       
184        btBroadphasePair*       internalAddPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1);
185
186        void    growTables();
187
188        SIMD_FORCE_INLINE bool equalsPair(const btBroadphasePair& pair, int proxyId1, int proxyId2)
189        {       
190                return pair.m_pProxy0->getUid() == proxyId1 && pair.m_pProxy1->getUid() == proxyId2;
191        }
192
193        /*
194        // Thomas Wang's hash, see: http://www.concentric.net/~Ttwang/tech/inthash.htm
195        // This assumes proxyId1 and proxyId2 are 16-bit.
196        SIMD_FORCE_INLINE int getHash(int proxyId1, int proxyId2)
197        {
198                int key = (proxyId2 << 16) | proxyId1;
199                key = ~key + (key << 15);
200                key = key ^ (key >> 12);
201                key = key + (key << 2);
202                key = key ^ (key >> 4);
203                key = key * 2057;
204                key = key ^ (key >> 16);
205                return key;
206        }
207        */
208
209
210       
211        SIMD_FORCE_INLINE       unsigned int getHash(unsigned int proxyId1, unsigned int proxyId2)
212        {
213                int key = static_cast<int>(((unsigned int)proxyId1) | (((unsigned int)proxyId2) <<16));
214                // Thomas Wang's hash
215
216                key += ~(key << 15);
217                key ^=  (key >> 10);
218                key +=  (key << 3);
219                key ^=  (key >> 6);
220                key += ~(key << 11);
221                key ^=  (key >> 16);
222                return static_cast<unsigned int>(key);
223        }
224       
225
226
227
228
229        SIMD_FORCE_INLINE btBroadphasePair* internalFindPair(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1, int hash)
230        {
231                int proxyId1 = proxy0->getUid();
232                int proxyId2 = proxy1->getUid();
233                #if 0 // wrong, 'equalsPair' use unsorted uids, copy-past devil striked again. Nat.
234                if (proxyId1 > proxyId2)
235                        btSwap(proxyId1, proxyId2);
236                #endif
237
238                int index = m_hashTable[hash];
239               
240                while( index != BT_NULL_PAIR && equalsPair(m_overlappingPairArray[index], proxyId1, proxyId2) == false)
241                {
242                        index = m_next[index];
243                }
244
245                if ( index == BT_NULL_PAIR )
246                {
247                        return NULL;
248                }
249
250                btAssert(index < m_overlappingPairArray.size());
251
252                return &m_overlappingPairArray[index];
253        }
254
255        virtual bool    hasDeferredRemoval()
256        {
257                return false;
258        }
259
260        virtual void    setInternalGhostPairCallback(btOverlappingPairCallback* ghostPairCallback)
261        {
262                m_ghostPairCallback = ghostPairCallback;
263        }
264
265        virtual void    sortOverlappingPairs(btDispatcher* dispatcher);
266       
267
268protected:
269       
270        btAlignedObjectArray<int>       m_hashTable;
271        btAlignedObjectArray<int>       m_next;
272        btOverlappingPairCallback*      m_ghostPairCallback;
273       
274};
275
276
277
278
279///btSortedOverlappingPairCache maintains the objects with overlapping AABB
280///Typically managed by the Broadphase, Axis3Sweep or btSimpleBroadphase
281class   btSortedOverlappingPairCache : public btOverlappingPairCache
282{
283        protected:
284                //avoid brute-force finding all the time
285                btBroadphasePairArray   m_overlappingPairArray;
286
287                //during the dispatch, check that user doesn't destroy/create proxy
288                bool            m_blockedForChanges;
289
290                ///by default, do the removal during the pair traversal
291                bool            m_hasDeferredRemoval;
292               
293                //if set, use the callback instead of the built in filter in needBroadphaseCollision
294                btOverlapFilterCallback* m_overlapFilterCallback;
295
296                btOverlappingPairCallback*      m_ghostPairCallback;
297
298        public:
299                       
300                btSortedOverlappingPairCache(); 
301                virtual ~btSortedOverlappingPairCache();
302
303                virtual void    processAllOverlappingPairs(btOverlapCallback*,btDispatcher* dispatcher);
304
305                void*   removeOverlappingPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1,btDispatcher* dispatcher);
306
307                void    cleanOverlappingPair(btBroadphasePair& pair,btDispatcher* dispatcher);
308               
309                btBroadphasePair*       addOverlappingPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1);
310
311                btBroadphasePair*       findPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1);
312                       
313               
314                void    cleanProxyFromPairs(btBroadphaseProxy* proxy,btDispatcher* dispatcher);
315
316                void    removeOverlappingPairsContainingProxy(btBroadphaseProxy* proxy,btDispatcher* dispatcher);
317
318
319                inline bool needsBroadphaseCollision(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1) const
320                {
321                        if (m_overlapFilterCallback)
322                                return m_overlapFilterCallback->needBroadphaseCollision(proxy0,proxy1);
323
324                        bool collides = (proxy0->m_collisionFilterGroup & proxy1->m_collisionFilterMask) != 0;
325                        collides = collides && (proxy1->m_collisionFilterGroup & proxy0->m_collisionFilterMask);
326                       
327                        return collides;
328                }
329               
330                btBroadphasePairArray&  getOverlappingPairArray()
331                {
332                        return m_overlappingPairArray;
333                }
334
335                const btBroadphasePairArray&    getOverlappingPairArray() const
336                {
337                        return m_overlappingPairArray;
338                }
339
340               
341
342
343                btBroadphasePair*       getOverlappingPairArrayPtr()
344                {
345                        return &m_overlappingPairArray[0];
346                }
347
348                const btBroadphasePair* getOverlappingPairArrayPtr() const
349                {
350                        return &m_overlappingPairArray[0];
351                }
352
353                int     getNumOverlappingPairs() const
354                {
355                        return m_overlappingPairArray.size();
356                }
357               
358                btOverlapFilterCallback* getOverlapFilterCallback()
359                {
360                        return m_overlapFilterCallback;
361                }
362
363                void setOverlapFilterCallback(btOverlapFilterCallback* callback)
364                {
365                        m_overlapFilterCallback = callback;
366                }
367
368                virtual bool    hasDeferredRemoval()
369                {
370                        return m_hasDeferredRemoval;
371                }
372
373                virtual void    setInternalGhostPairCallback(btOverlappingPairCallback* ghostPairCallback)
374                {
375                        m_ghostPairCallback = ghostPairCallback;
376                }
377
378                virtual void    sortOverlappingPairs(btDispatcher* dispatcher);
379               
380
381};
382
383
384
385///btNullPairCache skips add/removal of overlapping pairs. Userful for benchmarking and unit testing.
386class btNullPairCache : public btOverlappingPairCache
387{
388
389        btBroadphasePairArray   m_overlappingPairArray;
390
391public:
392
393        virtual btBroadphasePair*       getOverlappingPairArrayPtr()
394        {
395                return &m_overlappingPairArray[0];
396        }
397        const btBroadphasePair* getOverlappingPairArrayPtr() const
398        {
399                return &m_overlappingPairArray[0];
400        }
401        btBroadphasePairArray&  getOverlappingPairArray()
402        {
403                return m_overlappingPairArray;
404        }
405       
406        virtual void    cleanOverlappingPair(btBroadphasePair& /*pair*/,btDispatcher* /*dispatcher*/)
407        {
408
409        }
410
411        virtual int getNumOverlappingPairs() const
412        {
413                return 0;
414        }
415
416        virtual void    cleanProxyFromPairs(btBroadphaseProxy* /*proxy*/,btDispatcher* /*dispatcher*/)
417        {
418
419        }
420
421        virtual void setOverlapFilterCallback(btOverlapFilterCallback* /*callback*/)
422        {
423        }
424
425        virtual void    processAllOverlappingPairs(btOverlapCallback*,btDispatcher* /*dispatcher*/)
426        {
427        }
428
429        virtual btBroadphasePair* findPair(btBroadphaseProxy* /*proxy0*/, btBroadphaseProxy* /*proxy1*/)
430        {
431                return 0;
432        }
433
434        virtual bool    hasDeferredRemoval()
435        {
436                return true;
437        }
438
439        virtual void    setInternalGhostPairCallback(btOverlappingPairCallback* /* ghostPairCallback */)
440        {
441
442        }
443
444        virtual btBroadphasePair*       addOverlappingPair(btBroadphaseProxy* /*proxy0*/,btBroadphaseProxy* /*proxy1*/)
445        {
446                return 0;
447        }
448
449        virtual void*   removeOverlappingPair(btBroadphaseProxy* /*proxy0*/,btBroadphaseProxy* /*proxy1*/,btDispatcher* /*dispatcher*/)
450        {
451                return 0;
452        }
453
454        virtual void    removeOverlappingPairsContainingProxy(btBroadphaseProxy* /*proxy0*/,btDispatcher* /*dispatcher*/)
455        {
456        }
457       
458        virtual void    sortOverlappingPairs(btDispatcher* dispatcher)
459        {
460        (void) dispatcher;
461        }
462
463
464};
465
466
467#endif //BT_OVERLAPPING_PAIR_CACHE_H
468
469
Note: See TracBrowser for help on using the repository browser.