Upgrade Bullet to version 2.83.
[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 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
98 protected:
99         
100         btAlignedObjectArray<int>       m_hashTable;
101         btAlignedObjectArray<int>       m_next;
102         btOverlappingPairCallback*      m_ghostPairCallback;
103
104
105 public:
106         btHashedOverlappingPairCache();
107         virtual ~btHashedOverlappingPairCache();
108
109         
110         void    removeOverlappingPairsContainingProxy(btBroadphaseProxy* proxy,btDispatcher* dispatcher);
111
112         virtual void*   removeOverlappingPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1,btDispatcher* dispatcher);
113         
114         SIMD_FORCE_INLINE bool needsBroadphaseCollision(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1) const
115         {
116                 if (m_overlapFilterCallback)
117                         return m_overlapFilterCallback->needBroadphaseCollision(proxy0,proxy1);
118
119                 bool collides = (proxy0->m_collisionFilterGroup & proxy1->m_collisionFilterMask) != 0;
120                 collides = collides && (proxy1->m_collisionFilterGroup & proxy0->m_collisionFilterMask);
121                 
122                 return collides;
123         }
124
125         // Add a pair and return the new pair. If the pair already exists,
126         // no new pair is created and the old one is returned.
127         virtual btBroadphasePair*       addOverlappingPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1)
128         {
129                 gAddedPairs++;
130
131                 if (!needsBroadphaseCollision(proxy0,proxy1))
132                         return 0;
133
134                 return internalAddPair(proxy0,proxy1);
135         }
136
137         
138
139         void    cleanProxyFromPairs(btBroadphaseProxy* proxy,btDispatcher* dispatcher);
140
141         
142         virtual void    processAllOverlappingPairs(btOverlapCallback*,btDispatcher* dispatcher);
143
144         virtual btBroadphasePair*       getOverlappingPairArrayPtr()
145         {
146                 return &m_overlappingPairArray[0];
147         }
148
149         const btBroadphasePair* getOverlappingPairArrayPtr() const
150         {
151                 return &m_overlappingPairArray[0];
152         }
153
154         btBroadphasePairArray&  getOverlappingPairArray()
155         {
156                 return m_overlappingPairArray;
157         }
158
159         const btBroadphasePairArray&    getOverlappingPairArray() const
160         {
161                 return m_overlappingPairArray;
162         }
163
164         void    cleanOverlappingPair(btBroadphasePair& pair,btDispatcher* dispatcher);
165
166
167
168         btBroadphasePair* findPair(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1);
169
170         int GetCount() const { return m_overlappingPairArray.size(); }
171 //      btBroadphasePair* GetPairs() { return m_pairs; }
172
173         btOverlapFilterCallback* getOverlapFilterCallback()
174         {
175                 return m_overlapFilterCallback;
176         }
177
178         void setOverlapFilterCallback(btOverlapFilterCallback* callback)
179         {
180                 m_overlapFilterCallback = callback;
181         }
182
183         int     getNumOverlappingPairs() const
184         {
185                 return m_overlappingPairArray.size();
186         }
187 private:
188         
189         btBroadphasePair*       internalAddPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1);
190
191         void    growTables();
192
193         SIMD_FORCE_INLINE bool equalsPair(const btBroadphasePair& pair, int proxyId1, int proxyId2)
194         {       
195                 return pair.m_pProxy0->getUid() == proxyId1 && pair.m_pProxy1->getUid() == proxyId2;
196         }
197
198         /*
199         // Thomas Wang's hash, see: http://www.concentric.net/~Ttwang/tech/inthash.htm
200         // This assumes proxyId1 and proxyId2 are 16-bit.
201         SIMD_FORCE_INLINE int getHash(int proxyId1, int proxyId2)
202         {
203                 int key = (proxyId2 << 16) | proxyId1;
204                 key = ~key + (key << 15);
205                 key = key ^ (key >> 12);
206                 key = key + (key << 2);
207                 key = key ^ (key >> 4);
208                 key = key * 2057;
209                 key = key ^ (key >> 16);
210                 return key;
211         }
212         */
213
214
215         
216         SIMD_FORCE_INLINE       unsigned int getHash(unsigned int proxyId1, unsigned int proxyId2)
217         {
218                 int key = static_cast<int>(((unsigned int)proxyId1) | (((unsigned int)proxyId2) <<16));
219                 // Thomas Wang's hash
220
221                 key += ~(key << 15);
222                 key ^=  (key >> 10);
223                 key +=  (key << 3);
224                 key ^=  (key >> 6);
225                 key += ~(key << 11);
226                 key ^=  (key >> 16);
227                 return static_cast<unsigned int>(key);
228         }
229         
230
231
232
233
234         SIMD_FORCE_INLINE btBroadphasePair* internalFindPair(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1, int hash)
235         {
236                 int proxyId1 = proxy0->getUid();
237                 int proxyId2 = proxy1->getUid();
238                 #if 0 // wrong, 'equalsPair' use unsorted uids, copy-past devil striked again. Nat.
239                 if (proxyId1 > proxyId2) 
240                         btSwap(proxyId1, proxyId2);
241                 #endif
242
243                 int index = m_hashTable[hash];
244                 
245                 while( index != BT_NULL_PAIR && equalsPair(m_overlappingPairArray[index], proxyId1, proxyId2) == false)
246                 {
247                         index = m_next[index];
248                 }
249
250                 if ( index == BT_NULL_PAIR )
251                 {
252                         return NULL;
253                 }
254
255                 btAssert(index < m_overlappingPairArray.size());
256
257                 return &m_overlappingPairArray[index];
258         }
259
260         virtual bool    hasDeferredRemoval()
261         {
262                 return false;
263         }
264
265         virtual void    setInternalGhostPairCallback(btOverlappingPairCallback* ghostPairCallback)
266         {
267                 m_ghostPairCallback = ghostPairCallback;
268         }
269
270         virtual void    sortOverlappingPairs(btDispatcher* dispatcher);
271         
272
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