Bullet Collision Detection & Physics Library
btOverlappingPairCache.h
Go to the documentation of this file.
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
21#include "btBroadphaseProxy.h"
23
25class btDispatcher;
26
28
30{
32 {}
33 //return true for deletion of the pair
34 virtual bool processOverlap(btBroadphasePair& pair) = 0;
35
36};
37
39{
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
61{
62public:
63 virtual ~btOverlappingPairCache() {} // this is needed so we can get to the derived class destructor
64
66
67 virtual const btBroadphasePair* getOverlappingPairArrayPtr() const = 0;
68
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
78
80
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
93
95{
98
99protected:
100
104
105
106public:
108
111
112
113 void removeOverlappingPairsContainingProxy(btBroadphaseProxy* proxy,btDispatcher* dispatcher);
114
115 virtual void* removeOverlappingPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1,btDispatcher* dispatcher);
116
118 {
119 if (m_overlapFilterCallback)
120 return m_overlapFilterCallback->needBroadphaseCollision(proxy0,proxy1);
121
122 bool collides = (proxy0->m_collisionFilterGroup & proxy1->m_collisionFilterMask) != 0;
123 collides = collides && (proxy1->m_collisionFilterGroup & proxy0->m_collisionFilterMask);
124
125 return collides;
126 }
127
128 // Add a pair and return the new pair. If the pair already exists,
129 // no new pair is created and the old one is returned.
131 {
132 gAddedPairs++;
133
134 if (!needsBroadphaseCollision(proxy0,proxy1))
135 return 0;
136
137 return internalAddPair(proxy0,proxy1);
138 }
139
140
141
142 void cleanProxyFromPairs(btBroadphaseProxy* proxy,btDispatcher* dispatcher);
143
144
145 virtual void processAllOverlappingPairs(btOverlapCallback*,btDispatcher* dispatcher);
146
148 {
149 return &m_overlappingPairArray[0];
150 }
151
153 {
154 return &m_overlappingPairArray[0];
155 }
156
158 {
159 return m_overlappingPairArray;
160 }
161
163 {
164 return m_overlappingPairArray;
165 }
166
167 void cleanOverlappingPair(btBroadphasePair& pair,btDispatcher* dispatcher);
168
169
170
171 btBroadphasePair* findPair(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1);
172
173 int GetCount() const { return m_overlappingPairArray.size(); }
174// btBroadphasePair* GetPairs() { return m_pairs; }
175
177 {
178 return m_overlapFilterCallback;
179 }
180
182 {
183 m_overlapFilterCallback = callback;
184 }
185
187 {
188 return m_overlappingPairArray.size();
189 }
190private:
191
192 btBroadphasePair* internalAddPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1);
193
194 void growTables();
195
196 SIMD_FORCE_INLINE bool equalsPair(const btBroadphasePair& pair, int proxyId1, int proxyId2)
197 {
198 return pair.m_pProxy0->getUid() == proxyId1 && pair.m_pProxy1->getUid() == proxyId2;
199 }
200
201 /*
202 // Thomas Wang's hash, see: http://www.concentric.net/~Ttwang/tech/inthash.htm
203 // This assumes proxyId1 and proxyId2 are 16-bit.
204 SIMD_FORCE_INLINE int getHash(int proxyId1, int proxyId2)
205 {
206 int key = (proxyId2 << 16) | proxyId1;
207 key = ~key + (key << 15);
208 key = key ^ (key >> 12);
209 key = key + (key << 2);
210 key = key ^ (key >> 4);
211 key = key * 2057;
212 key = key ^ (key >> 16);
213 return key;
214 }
215 */
216
217
218 SIMD_FORCE_INLINE unsigned int getHash(unsigned int proxyId1, unsigned int proxyId2)
219 {
220 unsigned int key = proxyId1 | (proxyId2 << 16);
221 // Thomas Wang's hash
222
223 key += ~(key << 15);
224 key ^= (key >> 10);
225 key += (key << 3);
226 key ^= (key >> 6);
227 key += ~(key << 11);
228 key ^= (key >> 16);
229 return key;
230 }
231
232
233
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
266 {
267 m_ghostPairCallback = ghostPairCallback;
268 }
269
270 virtual void sortOverlappingPairs(btDispatcher* dispatcher);
271
272
273
274};
275
276
277
278
282{
283 protected:
284 //avoid brute-force finding all the time
286
287 //during the dispatch, check that user doesn't destroy/create proxy
289
292
293 //if set, use the callback instead of the built in filter in needBroadphaseCollision
295
297
298 public:
299
302
304
306
307 void cleanOverlappingPair(btBroadphasePair& pair,btDispatcher* dispatcher);
308
310
312
313
314 void cleanProxyFromPairs(btBroadphaseProxy* proxy,btDispatcher* dispatcher);
315
317
318
320 {
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
331 {
333 }
334
336 {
338 }
339
340
341
342
344 {
345 return &m_overlappingPairArray[0];
346 }
347
349 {
350 return &m_overlappingPairArray[0];
351 }
352
354 {
356 }
357
359 {
361 }
362
364 {
365 m_overlapFilterCallback = callback;
366 }
367
368 virtual bool hasDeferredRemoval()
369 {
371 }
372
374 {
375 m_ghostPairCallback = ghostPairCallback;
376 }
377
378 virtual void sortOverlappingPairs(btDispatcher* dispatcher);
379
380
381};
382
383
384
387{
388
390
391public:
392
394 {
395 return &m_overlappingPairArray[0];
396 }
398 {
399 return &m_overlappingPairArray[0];
400 }
402 {
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
422 {
423 }
424
426 {
427 }
428
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
445 {
446 return 0;
447 }
448
449 virtual void* removeOverlappingPair(btBroadphaseProxy* /*proxy0*/,btBroadphaseProxy* /*proxy1*/,btDispatcher* /*dispatcher*/)
450 {
451 return 0;
452 }
453
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
int gRemovePairs
int gFindPairs
int gAddedPairs
btAlignedObjectArray< btBroadphasePair > btBroadphasePairArray
const int BT_NULL_PAIR
#define ATTRIBUTE_ALIGNED16(a)
Definition: btScalar.h:82
#define SIMD_FORCE_INLINE
Definition: btScalar.h:81
void btSwap(T &a, T &b)
Definition: btScalar.h:621
#define btAssert(x)
Definition: btScalar.h:131
int size() const
return the number of elements in the array
The btDispatcher interface class can be used in combination with broadphase to dispatch calculations ...
Definition: btDispatcher.h:76
Hash-space based Pair Cache, thanks to Erin Catto, Box2D, http://www.box2d.org, and Pierre Terdiman,...
const btBroadphasePair * getOverlappingPairArrayPtr() const
btAlignedObjectArray< int > m_next
btBroadphasePairArray m_overlappingPairArray
btOverlapFilterCallback * m_overlapFilterCallback
btBroadphasePair * internalFindPair(btBroadphaseProxy *proxy0, btBroadphaseProxy *proxy1, int hash)
virtual btBroadphasePair * addOverlappingPair(btBroadphaseProxy *proxy0, btBroadphaseProxy *proxy1)
const btBroadphasePairArray & getOverlappingPairArray() const
virtual btBroadphasePair * getOverlappingPairArrayPtr()
bool equalsPair(const btBroadphasePair &pair, int proxyId1, int proxyId2)
void setOverlapFilterCallback(btOverlapFilterCallback *callback)
virtual void setInternalGhostPairCallback(btOverlappingPairCallback *ghostPairCallback)
unsigned int getHash(unsigned int proxyId1, unsigned int proxyId2)
btAlignedObjectArray< int > m_hashTable
btOverlapFilterCallback * getOverlapFilterCallback()
btOverlappingPairCallback * m_ghostPairCallback
btBroadphasePairArray & getOverlappingPairArray()
bool needsBroadphaseCollision(btBroadphaseProxy *proxy0, btBroadphaseProxy *proxy1) const
btNullPairCache skips add/removal of overlapping pairs. Userful for benchmarking and unit testing.
virtual void sortOverlappingPairs(btDispatcher *dispatcher)
virtual void cleanOverlappingPair(btBroadphasePair &, btDispatcher *)
virtual void processAllOverlappingPairs(btOverlapCallback *, btDispatcher *)
btBroadphasePairArray m_overlappingPairArray
virtual void setOverlapFilterCallback(btOverlapFilterCallback *)
virtual void setInternalGhostPairCallback(btOverlappingPairCallback *)
virtual btBroadphasePair * findPair(btBroadphaseProxy *, btBroadphaseProxy *)
virtual int getNumOverlappingPairs() const
virtual void * removeOverlappingPair(btBroadphaseProxy *, btBroadphaseProxy *, btDispatcher *)
virtual void removeOverlappingPairsContainingProxy(btBroadphaseProxy *, btDispatcher *)
virtual bool hasDeferredRemoval()
btBroadphasePairArray & getOverlappingPairArray()
virtual btBroadphasePair * getOverlappingPairArrayPtr()
virtual void cleanProxyFromPairs(btBroadphaseProxy *, btDispatcher *)
virtual btBroadphasePair * addOverlappingPair(btBroadphaseProxy *, btBroadphaseProxy *)
const btBroadphasePair * getOverlappingPairArrayPtr() const
The btOverlappingPairCache provides an interface for overlapping pair management (add,...
virtual btBroadphasePairArray & getOverlappingPairArray()=0
virtual int getNumOverlappingPairs() const =0
virtual void cleanProxyFromPairs(btBroadphaseProxy *proxy, btDispatcher *dispatcher)=0
virtual void setOverlapFilterCallback(btOverlapFilterCallback *callback)=0
virtual btBroadphasePair * getOverlappingPairArrayPtr()=0
virtual void processAllOverlappingPairs(btOverlapCallback *, btDispatcher *dispatcher)=0
virtual btBroadphasePair * findPair(btBroadphaseProxy *proxy0, btBroadphaseProxy *proxy1)=0
virtual void cleanOverlappingPair(btBroadphasePair &pair, btDispatcher *dispatcher)=0
virtual void sortOverlappingPairs(btDispatcher *dispatcher)=0
virtual const btBroadphasePair * getOverlappingPairArrayPtr() const =0
virtual void setInternalGhostPairCallback(btOverlappingPairCallback *ghostPairCallback)=0
virtual bool hasDeferredRemoval()=0
The btOverlappingPairCallback class is an additional optional broadphase user callback for adding/rem...
btSortedOverlappingPairCache maintains the objects with overlapping AABB Typically managed by the Bro...
virtual void processAllOverlappingPairs(btOverlapCallback *, btDispatcher *dispatcher)
virtual void setInternalGhostPairCallback(btOverlappingPairCallback *ghostPairCallback)
btOverlapFilterCallback * getOverlapFilterCallback()
btBroadphasePair * addOverlappingPair(btBroadphaseProxy *proxy0, btBroadphaseProxy *proxy1)
btBroadphasePair * getOverlappingPairArrayPtr()
btOverlapFilterCallback * m_overlapFilterCallback
btBroadphasePair * findPair(btBroadphaseProxy *proxy0, btBroadphaseProxy *proxy1)
this findPair becomes really slow.
bool needsBroadphaseCollision(btBroadphaseProxy *proxy0, btBroadphaseProxy *proxy1) const
void removeOverlappingPairsContainingProxy(btBroadphaseProxy *proxy, btDispatcher *dispatcher)
btOverlappingPairCallback * m_ghostPairCallback
const btBroadphasePair * getOverlappingPairArrayPtr() const
btBroadphasePairArray & getOverlappingPairArray()
void setOverlapFilterCallback(btOverlapFilterCallback *callback)
void cleanOverlappingPair(btBroadphasePair &pair, btDispatcher *dispatcher)
void * removeOverlappingPair(btBroadphaseProxy *proxy0, btBroadphaseProxy *proxy1, btDispatcher *dispatcher)
bool m_hasDeferredRemoval
by default, do the removal during the pair traversal
btBroadphasePairArray m_overlappingPairArray
void cleanProxyFromPairs(btBroadphaseProxy *proxy, btDispatcher *dispatcher)
virtual void sortOverlappingPairs(btDispatcher *dispatcher)
const btBroadphasePairArray & getOverlappingPairArray() const
The btBroadphasePair class contains a pair of aabb-overlapping objects.
btBroadphaseProxy * m_pProxy1
btBroadphaseProxy * m_pProxy0
The btBroadphaseProxy is the main class that can be used with the Bullet broadphases.
virtual bool processOverlap(btBroadphasePair &pair)=0
virtual bool needBroadphaseCollision(btBroadphaseProxy *proxy0, btBroadphaseProxy *proxy1) const =0