← Back to branch summary

~ubuntu-branches/ubuntu/vivid/emscripten/vivid

« back to all changes in this revision

Viewing changes to tests/bullet/src/BulletCollision/BroadphaseCollision/btOverlappingPairCache.h

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2013-05-02 13:11:51 UTC
  • Revision ID: package-import@ubuntu.com-20130502131151-q8dvteqr1ef2x7xz
Tags: upstream-1.4.1~20130504~adb56cb
Import upstream version 1.4.1~20130504~adb56cb

Show diffs side-by-side

added added

removed removed

Lines of Context:
tests/bullet/src/BulletCollision/BroadphaseCollision/btOverlappingPairCache.h
 
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
#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"
 
25
class btDispatcher;
 
26
 
 
27
typedef btAlignedObjectArray<btBroadphasePair>  btBroadphasePairArray;
 
28
 
 
29
struct  btOverlapCallback
 
30
{
 
31
        virtual ~btOverlapCallback()
 
32
        {}
 
33
        //return true for deletion of the pair
 
34
        virtual bool    processOverlap(btBroadphasePair& pair) = 0;
 
35
 
 
36
};
 
37
 
 
38
struct 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
 
 
52
extern int gRemovePairs;
 
53
extern int gAddedPairs;
 
54
extern int gFindPairs;
 
55
 
 
56
const 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.
 
60
class btOverlappingPairCache : public btOverlappingPairCallback
 
61
{
 
62
public:
 
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
 
93
class btHashedOverlappingPairCache : public btOverlappingPairCache
 
94
{
 
95
        btBroadphasePairArray   m_overlappingPairArray;
 
96
        btOverlapFilterCallback* m_overlapFilterCallback;
 
97
        bool            m_blockedForChanges;
 
98
 
 
99
 
 
100
public:
 
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
        }
 
182
private:
 
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
 
 
268
protected:
 
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
 
281
class   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.
 
386
class btNullPairCache : public btOverlappingPairCache
 
387
{
 
388
 
 
389
        btBroadphasePairArray   m_overlappingPairArray;
 
390
 
 
391
public:
 
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