Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: code/branches/netp2/src/bullet/BulletCollision/BroadphaseCollision/btOverlappingPairCache.h @ 3008

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

Merged presentation branch back to trunk.

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