24 #if DBVT_BP_PROFILE||DBVT_BP_ENABLE_BENCHMARK 31 __forceinline ProfileScope(
btClock& clock,
unsigned long& value) :
32 m_clock(&clock),m_value(&value),m_base(clock.getTimeMicroseconds())
35 __forceinline ~ProfileScope()
37 (*m_value)+=m_clock->getTimeMicroseconds()-m_base;
40 unsigned long* m_value;
43 #define SPC(_value_) ProfileScope spc_scope(m_clock,_value_) 58 if(list) list->links[0]=item;
66 if(item->links[0]) item->links[0]->links[1]=item->links[1];
else list=item->links[1];
67 if(item->links[1]) item->links[1]->links[0]=item->links[0];
75 while(root) { ++n;root=root->links[1]; }
81 static inline void clear(T& value)
83 static const struct ZeroDummy : T {} zerodummy;
103 #if DBVT_BP_SORTPAIRS 113 Process(n,proxy->
leaf);
124 m_deferedcollide =
false;
125 m_needcleanup =
true;
126 m_releasepaircache = (paircache!=0)?
false:
true;
141 for(
int i=0;i<=STAGECOUNT;++i)
153 if(m_releasepaircache)
155 m_paircache->~btOverlappingPairCache();
165 short int collisionFilterGroup,
166 short int collisionFilterMask,
171 collisionFilterGroup,
172 collisionFilterMask);
177 proxy->
stage = m_stageCurrent;
179 proxy->
leaf = m_sets[0].insert(aabb,proxy);
180 listappend(proxy,m_stageRoots[m_stageCurrent]);
181 if(!m_deferedcollide)
184 collider.
proxy=proxy;
185 m_sets[0].collideTV(m_sets[0].m_root,aabb,collider);
186 m_sets[1].collideTV(m_sets[1].m_root,aabb,collider);
196 if(proxy->
stage==STAGECOUNT)
197 m_sets[1].remove(proxy->
leaf);
199 m_sets[0].remove(proxy->
leaf);
201 m_paircache->removeOverlappingPairsContainingProxy(proxy,dispatcher);
217 :m_rayCallback(orgCallback)
231 m_sets[0].rayTestInternal( m_sets[0].m_root,
241 m_sets[1].rayTestInternal( m_sets[1].m_root,
258 :m_aabbCallback(orgCallback)
274 m_sets[0].collideTV(m_sets[0].m_root,
bounds,callback);
275 m_sets[1].collideTV(m_sets[1].m_root,
bounds,callback);
289 #if DBVT_BP_PREVENTFALSEUPDATE 293 bool docollide=
false;
294 if(proxy->
stage==STAGECOUNT)
296 m_sets[1].remove(proxy->
leaf);
297 proxy->
leaf=m_sets[0].insert(aabb,proxy);
308 if(delta[0]<0) velocity[0]=-velocity[0];
309 if(delta[1]<0) velocity[1]=-velocity[1];
310 if(delta[2]<0) velocity[2]=-velocity[2];
315 m_sets[0].update(proxy->
leaf,aabb,velocity)
325 m_sets[0].update(proxy->
leaf,aabb);
333 proxy->
stage = m_stageCurrent;
334 listappend(proxy,m_stageRoots[m_stageCurrent]);
338 if(!m_deferedcollide)
341 m_sets[1].collideTTpersistentStack(m_sets[1].m_root,proxy->
leaf,collider);
342 m_sets[0].collideTTpersistentStack(m_sets[0].m_root,proxy->
leaf,collider);
357 bool docollide=
false;
358 if(proxy->
stage==STAGECOUNT)
360 m_sets[1].remove(proxy->
leaf);
361 proxy->
leaf=m_sets[0].insert(aabb,proxy);
368 m_sets[0].update(proxy->
leaf,aabb);
375 proxy->
stage = m_stageCurrent;
376 listappend(proxy,m_stageRoots[m_stageCurrent]);
380 if(!m_deferedcollide)
383 m_sets[1].collideTTpersistentStack(m_sets[1].m_root,proxy->
leaf,collider);
384 m_sets[0].collideTTpersistentStack(m_sets[0].m_root,proxy->
leaf,collider);
394 if(0==(m_pid%DBVT_BP_PROFILING_RATE))
396 printf(
"fixed(%u) dynamics(%u) pairs(%u)\r\n",m_sets[1].m_leaves,m_sets[0].m_leaves,m_paircache->getNumOverlappingPairs());
397 unsigned int total=m_profiling.m_total;
398 if(total<=0) total=1;
399 printf(
"ddcollide: %u%% (%uus)\r\n",(50+m_profiling.m_ddcollide*100)/total,m_profiling.m_ddcollide/DBVT_BP_PROFILING_RATE);
400 printf(
"fdcollide: %u%% (%uus)\r\n",(50+m_profiling.m_fdcollide*100)/total,m_profiling.m_fdcollide/DBVT_BP_PROFILING_RATE);
401 printf(
"cleanup: %u%% (%uus)\r\n",(50+m_profiling.m_cleanup*100)/total,m_profiling.m_cleanup/DBVT_BP_PROFILING_RATE);
402 printf(
"total: %uus\r\n",total/DBVT_BP_PROFILING_RATE);
403 const unsigned long sum=m_profiling.m_ddcollide+
404 m_profiling.m_fdcollide+
405 m_profiling.m_cleanup;
406 printf(
"leaked: %u%% (%uus)\r\n",100-((50+sum*100)/total),(total-sum)/DBVT_BP_PROFILING_RATE);
407 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));
413 performDeferredRemoval(dispatcher);
420 if (m_paircache->hasDeferredRemoval())
439 for (i=0;i<overlappingPairArray.
size();i++)
444 bool isDuplicate = (pair == previousPair);
448 bool needsRemoval =
false;
459 needsRemoval =
false;
474 m_paircache->cleanOverlappingPair(pair,dispatcher);
485 overlappingPairArray.
resize(overlappingPairArray.
size() - invalidPair);
509 SPC(m_profiling.m_total);
511 m_sets[0].optimizeIncremental(1+(m_sets[0].m_leaves*m_dupdates)/100);
514 const int count=1+(m_sets[1].m_leaves*m_fupdates)/100;
515 m_sets[1].optimizeIncremental(1+(m_sets[1].m_leaves*m_fupdates)/100);
516 m_fixedleft=btMax<int>(0,m_fixedleft-count);
519 m_stageCurrent=(m_stageCurrent+1)%STAGECOUNT;
528 #if DBVT_BP_ACCURATESLEEPING 529 m_paircache->removeOverlappingPairsContainingProxy(current,dispatcher);
530 collider.
proxy=current;
534 m_sets[0].remove(current->
leaf);
536 current->
leaf = m_sets[1].insert(curAabb,current);
537 current->
stage = STAGECOUNT;
540 m_fixedleft=m_sets[1].m_leaves;
548 SPC(m_profiling.m_fdcollide);
549 m_sets[0].collideTTpersistentStack(m_sets[0].m_root,m_sets[1].m_root,collider);
553 SPC(m_profiling.m_ddcollide);
554 m_sets[0].collideTTpersistentStack(m_sets[0].m_root,m_sets[0].m_root,collider);
560 SPC(m_profiling.m_cleanup);
565 int ni=
btMin(pairs.
size(),btMax<int>(m_newpairs,(pairs.
size()*m_cupdates)/100));
566 for(
int i=0;i<ni;++i)
573 #if DBVT_BP_SORTPAIRS 577 m_paircache->removeOverlappingPair(pa,pb,dispatcher);
581 if(pairs.
size()>0) m_cid=(m_cid+ni)%pairs.
size();
else m_cid=0;
588 { m_updates_ratio=m_updates_done/(
btScalar)m_updates_call; }
590 { m_updates_ratio=0; }
598 m_sets[0].optimizeTopDown();
599 m_sets[1].optimizeTopDown();
620 if(!m_sets[0].empty())
621 if(!m_sets[1].empty())
Merge( m_sets[0].m_root->volume,
622 m_sets[1].m_root->volume,
bounds);
624 bounds=m_sets[0].m_root->volume;
625 else if(!m_sets[1].empty())
bounds=m_sets[1].m_root->volume;
635 int totalObjects = m_sets[0].m_leaves + m_sets[1].m_leaves;
642 m_deferedcollide =
false;
643 m_needcleanup =
true;
657 for(
int i=0;i<=STAGECOUNT;++i)
669 #if DBVT_BP_ENABLE_BENCHMARK 671 struct btBroadphaseBenchmark
693 btSin(time)*amplitude/2;
695 btSin(time)*amplitude;
697 pbi->
setAabb(proxy,center-extents,center+extents,0);
700 static int UnsignedRand(
int range=RAND_MAX-1) {
return(rand()%(range+1)); }
702 static void OutputTime(
const char* name,
btClock& c,
unsigned count=0)
705 const unsigned long ms=(us+500)/1000;
708 printf(
"%s : %u us (%u ms), %.2f/s\r\n",name,us,ms,count/sec);
710 printf(
"%s : %u us (%u ms)\r\n",name,us,ms);
716 static const btBroadphaseBenchmark::Experiment experiments[]=
722 static const int nexperiments=
sizeof(experiments)/
sizeof(experiments[0]);
726 for(
int iexp=0;iexp<nexperiments;++iexp)
728 const btBroadphaseBenchmark::Experiment& experiment=experiments[iexp];
729 const int object_count=experiment.object_count;
730 const int update_count=(object_count*experiment.update_count)/100;
731 const int spawn_count=(object_count*experiment.spawn_count)/100;
732 const btScalar speed=experiment.speed;
733 const btScalar amplitude=experiment.amplitude;
734 printf(
"Experiment #%u '%s':\r\n",iexp,experiment.name);
735 printf(
"\tObjects: %u\r\n",object_count);
736 printf(
"\tUpdate: %u\r\n",update_count);
737 printf(
"\tSpawn: %u\r\n",spawn_count);
738 printf(
"\tSpeed: %f\r\n",speed);
739 printf(
"\tAmplitude: %f\r\n",amplitude);
744 for(
int i=0;i<object_count;++i)
746 btBroadphaseBenchmark::Object* po=
new btBroadphaseBenchmark::Object();
747 po->center[0]=btBroadphaseBenchmark::UnitRand()*50;
748 po->center[1]=btBroadphaseBenchmark::UnitRand()*50;
749 po->center[2]=btBroadphaseBenchmark::UnitRand()*50;
750 po->extents[0]=btBroadphaseBenchmark::UnitRand()*2+2;
751 po->extents[1]=btBroadphaseBenchmark::UnitRand()*2+2;
752 po->extents[2]=btBroadphaseBenchmark::UnitRand()*2+2;
753 po->time=btBroadphaseBenchmark::UnitRand()*2000;
754 po->proxy=pbi->
createProxy(po->center-po->extents,po->center+po->extents,0,po,1,1,0,0);
757 btBroadphaseBenchmark::OutputTime(
"\tInitialization",wallclock);
760 for(
int i=0;i<objects.
size();++i)
762 objects[i]->update(speed,amplitude,pbi);
764 btBroadphaseBenchmark::OutputTime(
"\tFirst update",wallclock);
767 for(
int i=0;i<experiment.iterations;++i)
769 for(
int j=0;j<update_count;++j)
771 objects[j]->update(speed,amplitude,pbi);
775 btBroadphaseBenchmark::OutputTime(
"\tUpdate",wallclock,experiment.iterations);
778 for(
int i=0;i<objects.
size();++i)
784 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)
btBroadphaseProxy * createProxy(const btVector3 &aabbMin, const btVector3 &aabbMax, int shapeType, void *userPtr, short int collisionFilterGroup, short int collisionFilterMask, btDispatcher *dispatcher, void *multiSapProxy)
static void benchmark(btBroadphaseInterface *)
virtual void getBroadphaseAabb(btVector3 &aabbMin, btVector3 &aabbMax) const
getAabb returns the axis aligned bounding box in the 'global' coordinate frame will add some transfor...
DBVT_INLINE const btVector3 & Mins() const
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)
unsigned long int getTimeMicroseconds()
Returns the time in us since the last call to reset or since the Clock was created.
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)
DBVT_INLINE const btVector3 & Maxs() const
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)
virtual void setAabb(btBroadphaseProxy *proxy, const btVector3 &aabbMin, const btVector3 &aabbMax, btDispatcher *dispatcher)
#define SPC(_value_)
btDbvtBroadphase implementation by Nathanael Presson
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))
virtual btBroadphaseProxy * createProxy(const btVector3 &aabbMin, const btVector3 &aabbMax, int shapeType, void *userPtr, short int collisionFilterGroup, short int collisionFilterMask, btDispatcher *dispatcher, void *multiSapProxy)=0
static void listremove(T *item, T *&list)
#define btAlignedFree(ptr)
DBVT_PREFIX void collideTV(const btDbvtNode *root, const btDbvtVolume &volume, DBVT_IPOLICY) const
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
int size() const
return the number of elements in the array
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)
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)
virtual void calculateOverlappingPairs(btDispatcher *dispatcher)
calculateOverlappingPairs is optional: incremental algorithms (sweep and prune) might do it during th...
The btDispatcher interface class can be used in combination with broadphase to dispatch calculations ...
const T & btMin(const T &a, const T &b)
BroadphaseAabbTester(btBroadphaseAabbCallback &orgCallback)
virtual void destroyProxy(btBroadphaseProxy *proxy, btDispatcher *dispatcher)=0
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)
static btDbvtVolume bounds(const tNodeArray &leaves)
DBVT_INLINE bool NotEqual(const btDbvtAabbMm &a, const btDbvtAabbMm &b)
void Process(const btDbvtNode *leaf)
virtual void getAabb(btBroadphaseProxy *proxy, btVector3 &aabbMin, btVector3 &aabbMax) const
The btBroadphasePair class contains a pair of aabb-overlapping objects.