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];
339 m_sets[0].update(proxy->
leaf,aabb,velocity)
349 m_sets[0].update(proxy->
leaf,aabb);
357 proxy->
stage = m_stageCurrent;
358 listappend(proxy,m_stageRoots[m_stageCurrent]);
362 if(!m_deferedcollide)
365 m_sets[1].collideTTpersistentStack(m_sets[1].m_root,proxy->
leaf,collider);
366 m_sets[0].collideTTpersistentStack(m_sets[0].m_root,proxy->
leaf,collider);
381 bool docollide=
false;
382 if(proxy->
stage==STAGECOUNT)
384 m_sets[1].remove(proxy->
leaf);
385 proxy->
leaf=m_sets[0].insert(aabb,proxy);
392 m_sets[0].update(proxy->
leaf,aabb);
399 proxy->
stage = m_stageCurrent;
400 listappend(proxy,m_stageRoots[m_stageCurrent]);
404 if(!m_deferedcollide)
407 m_sets[1].collideTTpersistentStack(m_sets[1].m_root,proxy->
leaf,collider);
408 m_sets[0].collideTTpersistentStack(m_sets[0].m_root,proxy->
leaf,collider);
418 if(0==(m_pid%DBVT_BP_PROFILING_RATE))
420 printf(
"fixed(%u) dynamics(%u) pairs(%u)\r\n",m_sets[1].m_leaves,m_sets[0].m_leaves,m_paircache->getNumOverlappingPairs());
421 unsigned int total=m_profiling.m_total;
422 if(total<=0) total=1;
423 printf(
"ddcollide: %u%% (%uus)\r\n",(50+m_profiling.m_ddcollide*100)/total,m_profiling.m_ddcollide/DBVT_BP_PROFILING_RATE);
424 printf(
"fdcollide: %u%% (%uus)\r\n",(50+m_profiling.m_fdcollide*100)/total,m_profiling.m_fdcollide/DBVT_BP_PROFILING_RATE);
425 printf(
"cleanup: %u%% (%uus)\r\n",(50+m_profiling.m_cleanup*100)/total,m_profiling.m_cleanup/DBVT_BP_PROFILING_RATE);
426 printf(
"total: %uus\r\n",total/DBVT_BP_PROFILING_RATE);
427 const unsigned long sum=m_profiling.m_ddcollide+
428 m_profiling.m_fdcollide+
429 m_profiling.m_cleanup;
430 printf(
"leaked: %u%% (%uus)\r\n",100-((50+sum*100)/total),(total-sum)/DBVT_BP_PROFILING_RATE);
431 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));
437 performDeferredRemoval(dispatcher);
444 if (m_paircache->hasDeferredRemoval())
463 for (i=0;i<overlappingPairArray.
size();i++)
468 bool isDuplicate = (pair == previousPair);
472 bool needsRemoval =
false;
483 needsRemoval =
false;
498 m_paircache->cleanOverlappingPair(pair,dispatcher);
509 overlappingPairArray.
resize(overlappingPairArray.
size() - invalidPair);
533 SPC(m_profiling.m_total);
535 m_sets[0].optimizeIncremental(1+(m_sets[0].m_leaves*m_dupdates)/100);
538 const int count=1+(m_sets[1].m_leaves*m_fupdates)/100;
539 m_sets[1].optimizeIncremental(1+(m_sets[1].m_leaves*m_fupdates)/100);
540 m_fixedleft=btMax<int>(0,m_fixedleft-count);
543 m_stageCurrent=(m_stageCurrent+1)%STAGECOUNT;
547 #if DBVT_BP_ACCURATESLEEPING 554 #if DBVT_BP_ACCURATESLEEPING 555 m_paircache->removeOverlappingPairsContainingProxy(current,dispatcher);
556 collider.
proxy=current;
560 m_sets[0].remove(current->
leaf);
562 current->
leaf = m_sets[1].insert(curAabb,current);
563 current->
stage = STAGECOUNT;
566 m_fixedleft=m_sets[1].m_leaves;
574 SPC(m_profiling.m_fdcollide);
575 m_sets[0].collideTTpersistentStack(m_sets[0].m_root,m_sets[1].m_root,collider);
579 SPC(m_profiling.m_ddcollide);
580 m_sets[0].collideTTpersistentStack(m_sets[0].m_root,m_sets[0].m_root,collider);
586 SPC(m_profiling.m_cleanup);
591 int ni=
btMin(pairs.
size(),btMax<int>(m_newpairs,(pairs.
size()*m_cupdates)/100));
592 for(
int i=0;i<ni;++i)
599 #if DBVT_BP_SORTPAIRS 603 m_paircache->removeOverlappingPair(pa,pb,dispatcher);
607 if(pairs.
size()>0) m_cid=(m_cid+ni)%pairs.
size();
else m_cid=0;
614 { m_updates_ratio=m_updates_done/(
btScalar)m_updates_call; }
616 { m_updates_ratio=0; }
624 m_sets[0].optimizeTopDown();
625 m_sets[1].optimizeTopDown();
646 if(!m_sets[0].empty())
647 if(!m_sets[1].empty())
Merge( m_sets[0].m_root->volume,
648 m_sets[1].m_root->volume,
bounds);
650 bounds=m_sets[0].m_root->volume;
651 else if(!m_sets[1].empty())
bounds=m_sets[1].m_root->volume;
661 int totalObjects = m_sets[0].m_leaves + m_sets[1].m_leaves;
668 m_deferedcollide =
false;
669 m_needcleanup =
true;
683 for(
int i=0;i<=STAGECOUNT;++i)
695 #if DBVT_BP_ENABLE_BENCHMARK 697 struct btBroadphaseBenchmark
719 btSin(time)*amplitude/2;
721 btSin(time)*amplitude;
723 pbi->
setAabb(proxy,center-extents,center+extents,0);
726 static int UnsignedRand(
int range=RAND_MAX-1) {
return(rand()%(range+1)); }
728 static void OutputTime(
const char* name,
btClock& c,
unsigned count=0)
731 const unsigned long ms=(us+500)/1000;
734 printf(
"%s : %u us (%u ms), %.2f/s\r\n",name,us,ms,count/sec);
736 printf(
"%s : %u us (%u ms)\r\n",name,us,ms);
742 static const btBroadphaseBenchmark::Experiment experiments[]=
748 static const int nexperiments=
sizeof(experiments)/
sizeof(experiments[0]);
752 for(
int iexp=0;iexp<nexperiments;++iexp)
754 const btBroadphaseBenchmark::Experiment& experiment=experiments[iexp];
755 const int object_count=experiment.object_count;
756 const int update_count=(object_count*experiment.update_count)/100;
757 const int spawn_count=(object_count*experiment.spawn_count)/100;
758 const btScalar speed=experiment.speed;
759 const btScalar amplitude=experiment.amplitude;
760 printf(
"Experiment #%u '%s':\r\n",iexp,experiment.name);
761 printf(
"\tObjects: %u\r\n",object_count);
762 printf(
"\tUpdate: %u\r\n",update_count);
763 printf(
"\tSpawn: %u\r\n",spawn_count);
764 printf(
"\tSpeed: %f\r\n",speed);
765 printf(
"\tAmplitude: %f\r\n",amplitude);
770 for(
int i=0;i<object_count;++i)
772 btBroadphaseBenchmark::Object* po=
new btBroadphaseBenchmark::Object();
773 po->center[0]=btBroadphaseBenchmark::UnitRand()*50;
774 po->center[1]=btBroadphaseBenchmark::UnitRand()*50;
775 po->center[2]=btBroadphaseBenchmark::UnitRand()*50;
776 po->extents[0]=btBroadphaseBenchmark::UnitRand()*2+2;
777 po->extents[1]=btBroadphaseBenchmark::UnitRand()*2+2;
778 po->extents[2]=btBroadphaseBenchmark::UnitRand()*2+2;
779 po->time=btBroadphaseBenchmark::UnitRand()*2000;
780 po->proxy=pbi->
createProxy(po->center-po->extents,po->center+po->extents,0,po,1,1,0,0);
783 btBroadphaseBenchmark::OutputTime(
"\tInitialization",wallclock);
786 for(
int i=0;i<objects.
size();++i)
788 objects[i]->update(speed,amplitude,pbi);
790 btBroadphaseBenchmark::OutputTime(
"\tFirst update",wallclock);
793 for(
int i=0;i<experiment.iterations;++i)
795 for(
int j=0;j<update_count;++j)
797 objects[j]->update(speed,amplitude,pbi);
801 btBroadphaseBenchmark::OutputTime(
"\tUpdate",wallclock,experiment.iterations);
804 for(
int i=0;i<objects.
size();++i)
810 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 *)
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)
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
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))
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.
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)
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()
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
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)
virtual void getAabb(btBroadphaseProxy *proxy, btVector3 &aabbMin, btVector3 &aabbMax) const
The btBroadphasePair class contains a pair of aabb-overlapping objects.