Merging trunk up to revision 41245.
[blender.git] / extern / bullet2 / 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 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"
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 //OVERLAPPING_PAIR_CACHE_H
468
469