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
20#include "btBroadphaseProxy.h"
22
24class btDispatcher;
25
27
29{
31 {
32 }
33 //return true for deletion of the pair
34 virtual bool processOverlap(btBroadphasePair& pair) = 0;
35};
36
38{
40 {
41 }
42 // return true when pairs need collision
43 virtual bool needBroadphaseCollision(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1) const = 0;
44};
45
46const int BT_NULL_PAIR = 0xffffffff;
47
51{
52public:
53 virtual ~btOverlappingPairCache() {} // this is needed so we can get to the derived class destructor
54
56
57 virtual const btBroadphasePair* getOverlappingPairArrayPtr() const = 0;
58
60
61 virtual void cleanOverlappingPair(btBroadphasePair& pair, btDispatcher* dispatcher) = 0;
62
63 virtual int getNumOverlappingPairs() const = 0;
64
65 virtual void cleanProxyFromPairs(btBroadphaseProxy* proxy, btDispatcher* dispatcher) = 0;
66
68
70
71 virtual void processAllOverlappingPairs(btOverlapCallback* callback, btDispatcher* dispatcher, const struct btDispatcherInfo& /*dispatchInfo*/)
72 {
73 processAllOverlappingPairs(callback, dispatcher);
74 }
76
77 virtual bool hasDeferredRemoval() = 0;
78
79 virtual void setInternalGhostPairCallback(btOverlappingPairCallback* ghostPairCallback) = 0;
80
81 virtual void sortOverlappingPairs(btDispatcher* dispatcher) = 0;
82};
83
85
88{
91
92protected:
96
97public:
99
102
103 void removeOverlappingPairsContainingProxy(btBroadphaseProxy * proxy, btDispatcher * dispatcher);
104
105 virtual void* removeOverlappingPair(btBroadphaseProxy * proxy0, btBroadphaseProxy * proxy1, btDispatcher * dispatcher);
106
108 {
109 if (m_overlapFilterCallback)
110 return m_overlapFilterCallback->needBroadphaseCollision(proxy0, proxy1);
111
112 bool collides = (proxy0->m_collisionFilterGroup & proxy1->m_collisionFilterMask) != 0;
113 collides = collides && (proxy1->m_collisionFilterGroup & proxy0->m_collisionFilterMask);
114
115 return collides;
116 }
117
118 // Add a pair and return the new pair. If the pair already exists,
119 // no new pair is created and the old one is returned.
121 {
122 if (!needsBroadphaseCollision(proxy0, proxy1))
123 return 0;
124
125 return internalAddPair(proxy0, proxy1);
126 }
127
128 void cleanProxyFromPairs(btBroadphaseProxy * proxy, btDispatcher * dispatcher);
129
130 virtual void processAllOverlappingPairs(btOverlapCallback*, btDispatcher * dispatcher);
131
132 virtual void processAllOverlappingPairs(btOverlapCallback * callback, btDispatcher * dispatcher, const struct btDispatcherInfo& dispatchInfo);
133
135 {
136 return &m_overlappingPairArray[0];
137 }
138
140 {
141 return &m_overlappingPairArray[0];
142 }
143
145 {
146 return m_overlappingPairArray;
147 }
148
150 {
151 return m_overlappingPairArray;
152 }
153
154 void cleanOverlappingPair(btBroadphasePair & pair, btDispatcher * dispatcher);
155
156 btBroadphasePair* findPair(btBroadphaseProxy * proxy0, btBroadphaseProxy * proxy1);
157
158 int GetCount() const { return m_overlappingPairArray.size(); }
159 // btBroadphasePair* GetPairs() { return m_pairs; }
160
162 {
163 return m_overlapFilterCallback;
164 }
165
167 {
168 m_overlapFilterCallback = callback;
169 }
170
172 {
173 return m_overlappingPairArray.size();
174 }
175
176private:
177 btBroadphasePair* internalAddPair(btBroadphaseProxy * proxy0, btBroadphaseProxy * proxy1);
178
179 void growTables();
180
181 SIMD_FORCE_INLINE bool equalsPair(const btBroadphasePair& pair, int proxyId1, int proxyId2)
182 {
183 return pair.m_pProxy0->getUid() == proxyId1 && pair.m_pProxy1->getUid() == proxyId2;
184 }
185
186 /*
187 // Thomas Wang's hash, see: http://www.concentric.net/~Ttwang/tech/inthash.htm
188 // This assumes proxyId1 and proxyId2 are 16-bit.
189 SIMD_FORCE_INLINE int getHash(int proxyId1, int proxyId2)
190 {
191 int key = (proxyId2 << 16) | proxyId1;
192 key = ~key + (key << 15);
193 key = key ^ (key >> 12);
194 key = key + (key << 2);
195 key = key ^ (key >> 4);
196 key = key * 2057;
197 key = key ^ (key >> 16);
198 return key;
199 }
200 */
201
202 SIMD_FORCE_INLINE unsigned int getHash(unsigned int proxyId1, unsigned int proxyId2)
203 {
204 unsigned int key = proxyId1 | (proxyId2 << 16);
205 // Thomas Wang's hash
206
207 key += ~(key << 15);
208 key ^= (key >> 10);
209 key += (key << 3);
210 key ^= (key >> 6);
211 key += ~(key << 11);
212 key ^= (key >> 16);
213 return key;
214 }
215
217 {
218 int proxyId1 = proxy0->getUid();
219 int proxyId2 = proxy1->getUid();
220#if 0 // wrong, 'equalsPair' use unsorted uids, copy-past devil striked again. Nat.
221 if (proxyId1 > proxyId2)
222 btSwap(proxyId1, proxyId2);
223#endif
224
225 int index = m_hashTable[hash];
226
227 while (index != BT_NULL_PAIR && equalsPair(m_overlappingPairArray[index], proxyId1, proxyId2) == false)
228 {
229 index = m_next[index];
230 }
231
232 if (index == BT_NULL_PAIR)
233 {
234 return NULL;
235 }
236
237 btAssert(index < m_overlappingPairArray.size());
238
239 return &m_overlappingPairArray[index];
240 }
241
242 virtual bool hasDeferredRemoval()
243 {
244 return false;
245 }
246
248 {
249 m_ghostPairCallback = ghostPairCallback;
250 }
251
252 virtual void sortOverlappingPairs(btDispatcher * dispatcher);
253};
254
258{
259protected:
260 //avoid brute-force finding all the time
262
263 //during the dispatch, check that user doesn't destroy/create proxy
265
268
269 //if set, use the callback instead of the built in filter in needBroadphaseCollision
271
273
274public:
277
279
280 void* removeOverlappingPair(btBroadphaseProxy* proxy0, btBroadphaseProxy* proxy1, btDispatcher* dispatcher);
281
282 void cleanOverlappingPair(btBroadphasePair& pair, btDispatcher* dispatcher);
283
285
287
288 void cleanProxyFromPairs(btBroadphaseProxy* proxy, btDispatcher* dispatcher);
289
291
293 {
295 return m_overlapFilterCallback->needBroadphaseCollision(proxy0, proxy1);
296
297 bool collides = (proxy0->m_collisionFilterGroup & proxy1->m_collisionFilterMask) != 0;
298 collides = collides && (proxy1->m_collisionFilterGroup & proxy0->m_collisionFilterMask);
299
300 return collides;
301 }
302
304 {
306 }
307
309 {
311 }
312
314 {
315 return &m_overlappingPairArray[0];
316 }
317
319 {
320 return &m_overlappingPairArray[0];
321 }
322
324 {
326 }
327
329 {
331 }
332
334 {
335 m_overlapFilterCallback = callback;
336 }
337
338 virtual bool hasDeferredRemoval()
339 {
341 }
342
344 {
345 m_ghostPairCallback = ghostPairCallback;
346 }
347
348 virtual void sortOverlappingPairs(btDispatcher* dispatcher);
349};
350
353{
355
356public:
358 {
359 return &m_overlappingPairArray[0];
360 }
362 {
363 return &m_overlappingPairArray[0];
364 }
366 {
368 }
369
370 virtual void cleanOverlappingPair(btBroadphasePair& /*pair*/, btDispatcher* /*dispatcher*/)
371 {
372 }
373
374 virtual int getNumOverlappingPairs() const
375 {
376 return 0;
377 }
378
379 virtual void cleanProxyFromPairs(btBroadphaseProxy* /*proxy*/, btDispatcher* /*dispatcher*/)
380 {
381 }
382
384 {
385 }
386
388 {
389 }
390
392 {
393 return 0;
394 }
395
396 virtual bool hasDeferredRemoval()
397 {
398 return true;
399 }
400
401 virtual void setInternalGhostPairCallback(btOverlappingPairCallback* /* ghostPairCallback */)
402 {
403 }
404
406 {
407 return 0;
408 }
409
410 virtual void* removeOverlappingPair(btBroadphaseProxy* /*proxy0*/, btBroadphaseProxy* /*proxy1*/, btDispatcher* /*dispatcher*/)
411 {
412 return 0;
413 }
414
416 {
417 }
418
419 virtual void sortOverlappingPairs(btDispatcher* dispatcher)
420 {
421 (void)dispatcher;
422 }
423};
424
425#endif //BT_OVERLAPPING_PAIR_CACHE_H
btAlignedObjectArray< btBroadphasePair > btBroadphasePairArray
const int BT_NULL_PAIR
#define ATTRIBUTE_ALIGNED16(a)
Definition: btScalar.h:99
#define SIMD_FORCE_INLINE
Definition: btScalar.h:98
void btSwap(T &a, T &b)
Definition: btScalar.h:643
#define btAssert(x)
Definition: btScalar.h:153
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:77
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
virtual void processAllOverlappingPairs(btOverlapCallback *callback, btDispatcher *dispatcher, const struct btDispatcherInfo &)
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