25 #if DBVT_BP_PROFILE||DBVT_BP_ENABLE_BENCHMARK 32 __forceinline ProfileScope(
btClock& clock,
unsigned long& value) :
33 m_clock(&clock),m_value(&value),m_base(clock.getTimeMicroseconds())
36 __forceinline ~ProfileScope()
38 (*m_value)+=m_clock->getTimeMicroseconds()-m_base;
41 unsigned long* m_value;
44 #define SPC(_value_) ProfileScope spc_scope(m_clock,_value_) 59 if(list) list->links[0]=item;
67 if(item->links[0]) item->links[0]->links[1]=item->links[1];
else list=item->links[1];
68 if(item->links[1]) item->links[1]->links[0]=item->links[0];
76 while(root) { ++n;root=root->links[1]; }
82 static inline void clear(T& value)
84 static const struct ZeroDummy : T {} zerodummy;
104 #if DBVT_BP_SORTPAIRS 114 Process(n,proxy->
leaf);
125 m_deferedcollide =
false;
126 m_needcleanup =
true;
127 m_releasepaircache = (paircache!=0)?
false:
true;
142 for(
int i=0;i<=STAGECOUNT;++i)
149 m_rayTestStacks.resize(1);
159 if(m_releasepaircache)
161 m_paircache->~btOverlappingPairCache();
171 int collisionFilterGroup,
172 int collisionFilterMask,
176 collisionFilterGroup,
177 collisionFilterMask);
182 proxy->
stage = m_stageCurrent;
184 proxy->
leaf = m_sets[0].insert(aabb,proxy);
185 listappend(proxy,m_stageRoots[m_stageCurrent]);
186 if(!m_deferedcollide)
189 collider.
proxy=proxy;
190 m_sets[0].collideTV(m_sets[0].m_root,aabb,collider);
191 m_sets[1].collideTV(m_sets[1].m_root,aabb,collider);
201 if(proxy->
stage==STAGECOUNT)
202 m_sets[1].remove(proxy->
leaf);
204 m_sets[0].remove(proxy->
leaf);
206 m_paircache->removeOverlappingPairsContainingProxy(proxy,dispatcher);
222 :m_rayCallback(orgCallback)
242 if (threadIndex < m_rayTestStacks.size())
245 stack = &m_rayTestStacks[threadIndex];
253 m_sets[0].rayTestInternal( m_sets[0].m_root,
264 m_sets[1].rayTestInternal( m_sets[1].m_root,
282 :m_aabbCallback(orgCallback)
298 m_sets[0].collideTV(m_sets[0].m_root,
bounds,callback);
299 m_sets[1].collideTV(m_sets[1].m_root,
bounds,callback);
313 #if DBVT_BP_PREVENTFALSEUPDATE 317 bool docollide=
false;
318 if(proxy->
stage==STAGECOUNT)
320 m_sets[1].remove(proxy->
leaf);
321 proxy->
leaf=m_sets[0].insert(aabb,proxy);
332 if(delta[0]<0) velocity[0]=-velocity[0];
333 if(delta[1]<0) velocity[1]=-velocity[1];
334 if(delta[2]<0) velocity[2]=-velocity[2];
346 m_sets[0].update(proxy->
leaf,aabb);
354 proxy->
stage = m_stageCurrent;
355 listappend(proxy,m_stageRoots[m_stageCurrent]);
359 if(!m_deferedcollide)
362 m_sets[1].collideTTpersistentStack(m_sets[1].m_root,proxy->
leaf,collider);
363 m_sets[0].collideTTpersistentStack(m_sets[0].m_root,proxy->
leaf,collider);
378 bool docollide=
false;
379 if(proxy->
stage==STAGECOUNT)
381 m_sets[1].remove(proxy->
leaf);
382 proxy->
leaf=m_sets[0].insert(aabb,proxy);
389 m_sets[0].update(proxy->
leaf,aabb);
396 proxy->
stage = m_stageCurrent;
397 listappend(proxy,m_stageRoots[m_stageCurrent]);
401 if(!m_deferedcollide)
404 m_sets[1].collideTTpersistentStack(m_sets[1].m_root,proxy->
leaf,collider);
405 m_sets[0].collideTTpersistentStack(m_sets[0].m_root,proxy->
leaf,collider);
415 if(0==(m_pid%DBVT_BP_PROFILING_RATE))
417 printf(
"fixed(%u) dynamics(%u) pairs(%u)\r\n",m_sets[1].m_leaves,m_sets[0].m_leaves,m_paircache->getNumOverlappingPairs());
418 unsigned int total=m_profiling.m_total;
419 if(total<=0) total=1;
420 printf(
"ddcollide: %u%% (%uus)\r\n",(50+m_profiling.m_ddcollide*100)/total,m_profiling.m_ddcollide/DBVT_BP_PROFILING_RATE);
421 printf(
"fdcollide: %u%% (%uus)\r\n",(50+m_profiling.m_fdcollide*100)/total,m_profiling.m_fdcollide/DBVT_BP_PROFILING_RATE);
422 printf(
"cleanup: %u%% (%uus)\r\n",(50+m_profiling.m_cleanup*100)/total,m_profiling.m_cleanup/DBVT_BP_PROFILING_RATE);
423 printf(
"total: %uus\r\n",total/DBVT_BP_PROFILING_RATE);
424 const unsigned long sum=m_profiling.m_ddcollide+
425 m_profiling.m_fdcollide+
426 m_profiling.m_cleanup;
427 printf(
"leaked: %u%% (%uus)\r\n",100-((50+sum*100)/total),(total-sum)/DBVT_BP_PROFILING_RATE);
428 printf(
"job counts: %u%%\r\n",(m_profiling.m_jobcount*100)/((m_sets[0].m_leaves+m_sets[1].m_leaves)*DBVT_BP_PROFILING_RATE));
434 performDeferredRemoval(dispatcher);
441 if (m_paircache->hasDeferredRemoval())
460 for (i=0;i<overlappingPairArray.
size();i++)
465 bool isDuplicate = (pair == previousPair);
469 bool needsRemoval =
false;
480 needsRemoval =
false;
495 m_paircache->cleanOverlappingPair(pair,dispatcher);
506 overlappingPairArray.
resize(overlappingPairArray.
size() - invalidPair);
530 SPC(m_profiling.m_total);
532 m_sets[0].optimizeIncremental(1+(m_sets[0].m_leaves*m_dupdates)/100);
535 const int count=1+(m_sets[1].m_leaves*m_fupdates)/100;
536 m_sets[1].optimizeIncremental(1+(m_sets[1].m_leaves*m_fupdates)/100);
537 m_fixedleft=btMax<int>(0,m_fixedleft-count);
540 m_stageCurrent=(m_stageCurrent+1)%STAGECOUNT;
544 #if DBVT_BP_ACCURATESLEEPING 551 #if DBVT_BP_ACCURATESLEEPING 552 m_paircache->removeOverlappingPairsContainingProxy(current,dispatcher);
553 collider.
proxy=current;
557 m_sets[0].remove(current->
leaf);
559 current->
leaf = m_sets[1].insert(curAabb,current);
560 current->
stage = STAGECOUNT;
563 m_fixedleft=m_sets[1].m_leaves;
571 SPC(m_profiling.m_fdcollide);
572 m_sets[0].collideTTpersistentStack(m_sets[0].m_root,m_sets[1].m_root,collider);
576 SPC(m_profiling.m_ddcollide);
577 m_sets[0].collideTTpersistentStack(m_sets[0].m_root,m_sets[0].m_root,collider);
583 SPC(m_profiling.m_cleanup);
588 int ni=
btMin(pairs.
size(),btMax<int>(m_newpairs,(pairs.
size()*m_cupdates)/100));
589 for(
int i=0;i<ni;++i)
596 #if DBVT_BP_SORTPAIRS 600 m_paircache->removeOverlappingPair(pa,pb,dispatcher);
604 if(pairs.
size()>0) m_cid=(m_cid+ni)%pairs.
size();
else m_cid=0;
611 { m_updates_ratio=m_updates_done/(
btScalar)m_updates_call; }
613 { m_updates_ratio=0; }
621 m_sets[0].optimizeTopDown();
622 m_sets[1].optimizeTopDown();
643 if(!m_sets[0].empty())
644 if(!m_sets[1].empty())
Merge( m_sets[0].m_root->volume,
645 m_sets[1].m_root->volume,
bounds);
647 bounds=m_sets[0].m_root->volume;
648 else if(!m_sets[1].empty())
bounds=m_sets[1].m_root->volume;
658 int totalObjects = m_sets[0].m_leaves + m_sets[1].m_leaves;
665 m_deferedcollide =
false;
666 m_needcleanup =
true;
680 for(
int i=0;i<=STAGECOUNT;++i)
692 #if DBVT_BP_ENABLE_BENCHMARK 694 struct btBroadphaseBenchmark
716 btSin(time)*amplitude/2;
718 btSin(time)*amplitude;
720 pbi->
setAabb(proxy,center-extents,center+extents,0);
723 static int UnsignedRand(
int range=RAND_MAX-1) {
return(rand()%(range+1)); }
725 static void OutputTime(
const char* name,
btClock& c,
unsigned count=0)
728 const unsigned long ms=(us+500)/1000;
731 printf(
"%s : %u us (%u ms), %.2f/s\r\n",name,us,ms,count/sec);
733 printf(
"%s : %u us (%u ms)\r\n",name,us,ms);
739 static const btBroadphaseBenchmark::Experiment experiments[]=
745 static const int nexperiments=
sizeof(experiments)/
sizeof(experiments[0]);
749 for(
int iexp=0;iexp<nexperiments;++iexp)
751 const btBroadphaseBenchmark::Experiment& experiment=experiments[iexp];
752 const int object_count=experiment.object_count;
753 const int update_count=(object_count*experiment.update_count)/100;
754 const int spawn_count=(object_count*experiment.spawn_count)/100;
755 const btScalar speed=experiment.speed;
756 const btScalar amplitude=experiment.amplitude;
757 printf(
"Experiment #%u '%s':\r\n",iexp,experiment.name);
758 printf(
"\tObjects: %u\r\n",object_count);
759 printf(
"\tUpdate: %u\r\n",update_count);
760 printf(
"\tSpawn: %u\r\n",spawn_count);
761 printf(
"\tSpeed: %f\r\n",speed);
762 printf(
"\tAmplitude: %f\r\n",amplitude);
767 for(
int i=0;i<object_count;++i)
769 btBroadphaseBenchmark::Object* po=
new btBroadphaseBenchmark::Object();
770 po->center[0]=btBroadphaseBenchmark::UnitRand()*50;
771 po->center[1]=btBroadphaseBenchmark::UnitRand()*50;
772 po->center[2]=btBroadphaseBenchmark::UnitRand()*50;
773 po->extents[0]=btBroadphaseBenchmark::UnitRand()*2+2;
774 po->extents[1]=btBroadphaseBenchmark::UnitRand()*2+2;
775 po->extents[2]=btBroadphaseBenchmark::UnitRand()*2+2;
776 po->time=btBroadphaseBenchmark::UnitRand()*2000;
777 po->proxy=pbi->
createProxy(po->center-po->extents,po->center+po->extents,0,po,1,1,0,0);
780 btBroadphaseBenchmark::OutputTime(
"\tInitialization",wallclock);
783 for(
int i=0;i<objects.
size();++i)
785 objects[i]->update(speed,amplitude,pbi);
787 btBroadphaseBenchmark::OutputTime(
"\tFirst update",wallclock);
790 for(
int i=0;i<experiment.iterations;++i)
792 for(
int j=0;j<update_count;++j)
794 objects[j]->update(speed,amplitude,pbi);
798 btBroadphaseBenchmark::OutputTime(
"\tUpdate",wallclock,experiment.iterations);
801 for(
int i=0;i<objects.
size();++i)
807 btBroadphaseBenchmark::OutputTime(
"\tRelease",wallclock);
virtual void aabbTest(const btVector3 &aabbMin, const btVector3 &aabbMax, btBroadphaseAabbCallback &callback)
static T sum(const btAlignedObjectArray< T > &items)
DBVT_INLINE void Merge(const btDbvtAabbMm &a, const btDbvtAabbMm &b, btDbvtAabbMm &r)
void push_back(const T &_Val)
static void benchmark(btBroadphaseInterface *)
btBroadphaseRayCallback & m_rayCallback
static void listappend(T *item, T *&list)
virtual void resetPool(btDispatcher *dispatcher)
reset broadphase internal structures, to ensure determinism/reproducability
btScalar btSin(btScalar x)
btOverlappingPairCache * m_paircache
void Process(const btDbvtNode *na, const btDbvtNode *nb)
The btClock is a portable basic clock that measures accurate time in seconds, use for profiling...
The btDbvtBroadphase implements a broadphase using two dynamic AABB bounding volume hierarchies/trees...
void reset()
Resets the initial reference time.
void performDeferredRemoval(btDispatcher *dispatcher)
void collide(btDispatcher *dispatcher)
const unsigned int BT_MAX_THREAD_COUNT
The btOverlappingPairCache provides an interface for overlapping pair management (add, remove, storage), used by the btBroadphaseInterface broadphases.
void Process(const btDbvtNode *leaf)
btDbvtBroadphase(btOverlappingPairCache *paircache=0)
void Process(const btDbvtNode *n)
int size() const
return the number of elements in the array
virtual void setAabb(btBroadphaseProxy *proxy, const btVector3 &aabbMin, const btVector3 &aabbMax, btDispatcher *dispatcher)
virtual btOverlappingPairCache * getOverlappingPairCache()
static btDbvtAabbMm FromMM(const btVector3 &mi, const btVector3 &mx)
virtual void destroyProxy(btBroadphaseProxy *proxy, btDispatcher *dispatcher)
virtual void rayTest(const btVector3 &rayFrom, const btVector3 &rayTo, btBroadphaseRayCallback &rayCallback, const btVector3 &aabbMin=btVector3(0, 0, 0), const btVector3 &aabbMax=btVector3(0, 0, 0))
static void listremove(T *item, T *&list)
#define btAlignedFree(ptr)
virtual btBroadphaseProxy * createProxy(const btVector3 &aabbMin, const btVector3 &aabbMax, int shapeType, void *userPtr, int collisionFilterGroup, int collisionFilterMask, btDispatcher *dispatcher)=0
unsigned long long int getTimeMicroseconds()
Returns the time in us since the last call to reset or since the Clock was created.
static int listcount(T *root)
virtual void printStats()
static btDbvtAabbMm FromCR(const btVector3 &c, btScalar r)
The btBroadphaseInterface class provides an interface to detect aabb-overlapping object pairs...
The btBroadphaseProxy is the main class that can be used with the Bullet broadphases.
btBroadphaseProxy * m_pProxy1
btCollisionAlgorithm * m_algorithm
btVector3 can be used to represent 3D points and vectors.
#define ATTRIBUTE_ALIGNED16(a)
virtual bool process(const btBroadphaseProxy *proxy)=0
DBVT_INLINE const btVector3 & Maxs() const
btBroadphaseAabbCallback & m_aabbCallback
btBroadphaseProxy * m_pProxy0
void setAabbForceUpdate(btBroadphaseProxy *absproxy, const btVector3 &aabbMin, const btVector3 &aabbMax, btDispatcher *)
this setAabbForceUpdate is similar to setAabb but always forces the aabb update.
btDbvtTreeCollider(btDbvtBroadphase *p)
BroadphaseRayTester(btBroadphaseRayCallback &orgCallback)
virtual btBroadphasePair * addOverlappingPair(btBroadphaseProxy *proxy0, btBroadphaseProxy *proxy1)=0
static void clear(T &value)
virtual void getBroadphaseAabb(btVector3 &aabbMin, btVector3 &aabbMax) const
getAabb returns the axis aligned bounding box in the 'global' coordinate frame will add some transfor...
void resize(int newsize, const T &fillData=T())
btVector3 m_rayDirectionInverse
added some cached data to accelerate ray-AABB tests
DBVT_INLINE bool Intersect(const btDbvtAabbMm &a, const btDbvtAabbMm &b)
virtual void setAabb(btBroadphaseProxy *proxy, const btVector3 &aabbMin, const btVector3 &aabbMax, btDispatcher *dispatcher)=0
#define btAlignedAlloc(size, alignment)
static btDbvtVolume bounds(btDbvtNode **leaves, int count)
virtual void calculateOverlappingPairs(btDispatcher *dispatcher)
calculateOverlappingPairs is optional: incremental algorithms (sweep and prune) might do it during th...
unsigned int btGetCurrentThreadIndex()
virtual void getAabb(btBroadphaseProxy *proxy, btVector3 &aabbMin, btVector3 &aabbMax) const
btScalar gDbvtMargin
btDbvtBroadphase implementation by Nathanael Presson
DBVT_INLINE const btVector3 & Mins() const
The btDispatcher interface class can be used in combination with broadphase to dispatch calculations ...
const T & btMin(const T &a, const T &b)
DBVT_PREFIX void collideTV(const btDbvtNode *root, const btDbvtVolume &volume, DBVT_IPOLICY) const
BroadphaseAabbTester(btBroadphaseAabbCallback &orgCallback)
virtual void destroyProxy(btBroadphaseProxy *proxy, btDispatcher *dispatcher)=0
btBroadphaseProxy * createProxy(const btVector3 &aabbMin, const btVector3 &aabbMax, int shapeType, void *userPtr, int collisionFilterGroup, int collisionFilterMask, btDispatcher *dispatcher)
Hash-space based Pair Cache, thanks to Erin Catto, Box2D, http://www.box2d.org, and Pierre Terdiman...
virtual void calculateOverlappingPairs(btDispatcher *dispatcher)=0
calculateOverlappingPairs is optional: incremental algorithms (sweep and prune) might do it during th...
float btScalar
The btScalar type abstracts floating point numbers, to easily switch between double and single floati...
void quickSort(const L &CompareFunc)
btScalar btCos(btScalar x)
DBVT_INLINE bool NotEqual(const btDbvtAabbMm &a, const btDbvtAabbMm &b)
void Process(const btDbvtNode *leaf)
The btBroadphasePair class contains a pair of aabb-overlapping objects.