Bullet Collision Detection & Physics Library
btDbvtBroadphase.cpp
Go to the documentation of this file.
1 /*
2 Bullet Continuous Collision Detection and Physics Library
3 Copyright (c) 2003-2009 Erwin Coumans http://bulletphysics.org
4 
5 This software is provided 'as-is', without any express or implied warranty.
6 In no event will the authors be held liable for any damages arising from the use of this software.
7 Permission is granted to anyone to use this software for any purpose,
8 including commercial applications, and to alter it and redistribute it freely,
9 subject to the following restrictions:
10 
11 1. 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.
12 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
13 3. This notice may not be removed or altered from any source distribution.
14 */
15 
17 
18 #include "btDbvtBroadphase.h"
19 #include "LinearMath/btThreads.h"
20 
21 //
22 // Profiling
23 //
24 
25 #if DBVT_BP_PROFILE||DBVT_BP_ENABLE_BENCHMARK
26 #include <stdio.h>
27 #endif
28 
29 #if DBVT_BP_PROFILE
30 struct ProfileScope
31 {
32  __forceinline ProfileScope(btClock& clock,unsigned long& value) :
33  m_clock(&clock),m_value(&value),m_base(clock.getTimeMicroseconds())
34  {
35  }
36  __forceinline ~ProfileScope()
37  {
38  (*m_value)+=m_clock->getTimeMicroseconds()-m_base;
39  }
40  btClock* m_clock;
41  unsigned long* m_value;
42  unsigned long m_base;
43 };
44 #define SPC(_value_) ProfileScope spc_scope(m_clock,_value_)
45 #else
46 #define SPC(_value_)
47 #endif
48 
49 //
50 // Helpers
51 //
52 
53 //
54 template <typename T>
55 static inline void listappend(T* item,T*& list)
56 {
57  item->links[0]=0;
58  item->links[1]=list;
59  if(list) list->links[0]=item;
60  list=item;
61 }
62 
63 //
64 template <typename T>
65 static inline void listremove(T* item,T*& list)
66 {
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];
69 }
70 
71 //
72 template <typename T>
73 static inline int listcount(T* root)
74 {
75  int n=0;
76  while(root) { ++n;root=root->links[1]; }
77  return(n);
78 }
79 
80 //
81 template <typename T>
82 static inline void clear(T& value)
83 {
84  static const struct ZeroDummy : T {} zerodummy;
85  value=zerodummy;
86 }
87 
88 //
89 // Colliders
90 //
91 
92 /* Tree collider */
94 {
98  void Process(const btDbvtNode* na,const btDbvtNode* nb)
99  {
100  if(na!=nb)
101  {
102  btDbvtProxy* pa=(btDbvtProxy*)na->data;
103  btDbvtProxy* pb=(btDbvtProxy*)nb->data;
104 #if DBVT_BP_SORTPAIRS
105  if(pa->m_uniqueId>pb->m_uniqueId)
106  btSwap(pa,pb);
107 #endif
109  ++pbp->m_newpairs;
110  }
111  }
112  void Process(const btDbvtNode* n)
113  {
114  Process(n,proxy->leaf);
115  }
116 };
117 
118 //
119 // btDbvtBroadphase
120 //
121 
122 //
124 {
125  m_deferedcollide = false;
126  m_needcleanup = true;
127  m_releasepaircache = (paircache!=0)?false:true;
128  m_prediction = 0;
129  m_stageCurrent = 0;
130  m_fixedleft = 0;
131  m_fupdates = 1;
132  m_dupdates = 0;
133  m_cupdates = 10;
134  m_newpairs = 1;
135  m_updates_call = 0;
136  m_updates_done = 0;
137  m_updates_ratio = 0;
138  m_paircache = paircache? paircache : new(btAlignedAlloc(sizeof(btHashedOverlappingPairCache),16)) btHashedOverlappingPairCache();
139  m_gid = 0;
140  m_pid = 0;
141  m_cid = 0;
142  for(int i=0;i<=STAGECOUNT;++i)
143  {
144  m_stageRoots[i]=0;
145  }
146 #if BT_THREADSAFE
148 #else
150 #endif
151 #if DBVT_BP_PROFILE
152  clear(m_profiling);
153 #endif
154 }
155 
156 //
158 {
159  if(m_releasepaircache)
160  {
163  }
164 }
165 
166 //
168  const btVector3& aabbMax,
169  int /*shapeType*/,
170  void* userPtr,
171  int collisionFilterGroup,
172  int collisionFilterMask,
173  btDispatcher* /*dispatcher*/)
174 {
175  btDbvtProxy* proxy=new(btAlignedAlloc(sizeof(btDbvtProxy),16)) btDbvtProxy( aabbMin,aabbMax,userPtr,
176  collisionFilterGroup,
177  collisionFilterMask);
178 
179  btDbvtAabbMm aabb = btDbvtVolume::FromMM(aabbMin,aabbMax);
180 
181  //bproxy->aabb = btDbvtVolume::FromMM(aabbMin,aabbMax);
182  proxy->stage = m_stageCurrent;
183  proxy->m_uniqueId = ++m_gid;
184  proxy->leaf = m_sets[0].insert(aabb,proxy);
186  if(!m_deferedcollide)
187  {
188  btDbvtTreeCollider collider(this);
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);
192  }
193  return(proxy);
194 }
195 
196 //
198  btDispatcher* dispatcher)
199 {
200  btDbvtProxy* proxy=(btDbvtProxy*)absproxy;
201  if(proxy->stage==STAGECOUNT)
202  m_sets[1].remove(proxy->leaf);
203  else
204  m_sets[0].remove(proxy->leaf);
205  listremove(proxy,m_stageRoots[proxy->stage]);
207  btAlignedFree(proxy);
208  m_needcleanup=true;
209 }
210 
211 void btDbvtBroadphase::getAabb(btBroadphaseProxy* absproxy,btVector3& aabbMin, btVector3& aabbMax ) const
212 {
213  btDbvtProxy* proxy=(btDbvtProxy*)absproxy;
214  aabbMin = proxy->m_aabbMin;
215  aabbMax = proxy->m_aabbMax;
216 }
217 
219 {
222  :m_rayCallback(orgCallback)
223  {
224  }
225  void Process(const btDbvtNode* leaf)
226  {
227  btDbvtProxy* proxy=(btDbvtProxy*)leaf->data;
228  m_rayCallback.process(proxy);
229  }
230 };
231 
232 void btDbvtBroadphase::rayTest(const btVector3& rayFrom,const btVector3& rayTo, btBroadphaseRayCallback& rayCallback,const btVector3& aabbMin,const btVector3& aabbMax)
233 {
234  BroadphaseRayTester callback(rayCallback);
236 #if BT_THREADSAFE
237  // for this function to be threadsafe, each thread must have a separate copy
238  // of this stack. This could be thread-local static to avoid dynamic allocations,
239  // instead of just a local.
240  int threadIndex = btGetCurrentThreadIndex();
242  if (threadIndex < m_rayTestStacks.size())
243  {
244  // use per-thread preallocated stack if possible to avoid dynamic allocations
245  stack = &m_rayTestStacks[threadIndex];
246  }
247  else
248  {
249  stack = &localStack;
250  }
251 #endif
252 
253  m_sets[0].rayTestInternal( m_sets[0].m_root,
254  rayFrom,
255  rayTo,
256  rayCallback.m_rayDirectionInverse,
257  rayCallback.m_signs,
258  rayCallback.m_lambda_max,
259  aabbMin,
260  aabbMax,
261  *stack,
262  callback);
263 
264  m_sets[1].rayTestInternal( m_sets[1].m_root,
265  rayFrom,
266  rayTo,
267  rayCallback.m_rayDirectionInverse,
268  rayCallback.m_signs,
269  rayCallback.m_lambda_max,
270  aabbMin,
271  aabbMax,
272  *stack,
273  callback);
274 
275 }
276 
277 
279 {
282  :m_aabbCallback(orgCallback)
283  {
284  }
285  void Process(const btDbvtNode* leaf)
286  {
287  btDbvtProxy* proxy=(btDbvtProxy*)leaf->data;
288  m_aabbCallback.process(proxy);
289  }
290 };
291 
292 void btDbvtBroadphase::aabbTest(const btVector3& aabbMin,const btVector3& aabbMax,btBroadphaseAabbCallback& aabbCallback)
293 {
294  BroadphaseAabbTester callback(aabbCallback);
295 
297  //process all children, that overlap with the given AABB bounds
298  m_sets[0].collideTV(m_sets[0].m_root,bounds,callback);
299  m_sets[1].collideTV(m_sets[1].m_root,bounds,callback);
300 
301 }
302 
303 
304 
305 //
307  const btVector3& aabbMin,
308  const btVector3& aabbMax,
309  btDispatcher* /*dispatcher*/)
310 {
311  btDbvtProxy* proxy=(btDbvtProxy*)absproxy;
313 #if DBVT_BP_PREVENTFALSEUPDATE
314  if(NotEqual(aabb,proxy->leaf->volume))
315 #endif
316  {
317  bool docollide=false;
318  if(proxy->stage==STAGECOUNT)
319  {/* fixed -> dynamic set */
320  m_sets[1].remove(proxy->leaf);
321  proxy->leaf=m_sets[0].insert(aabb,proxy);
322  docollide=true;
323  }
324  else
325  {/* dynamic set */
326  ++m_updates_call;
327  if(Intersect(proxy->leaf->volume,aabb))
328  {/* Moving */
329 
330  const btVector3 delta=aabbMin-proxy->m_aabbMin;
331  btVector3 velocity(((proxy->m_aabbMax-proxy->m_aabbMin)/2)*m_prediction);
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];
335  if (
336 #ifdef DBVT_BP_MARGIN
337  m_sets[0].update(proxy->leaf,aabb,velocity,DBVT_BP_MARGIN)
338 #else
339  m_sets[0].update(proxy->leaf,aabb,velocity)
340 #endif
341  )
342  {
343  ++m_updates_done;
344  docollide=true;
345  }
346  }
347  else
348  {/* Teleporting */
349  m_sets[0].update(proxy->leaf,aabb);
350  ++m_updates_done;
351  docollide=true;
352  }
353  }
354  listremove(proxy,m_stageRoots[proxy->stage]);
355  proxy->m_aabbMin = aabbMin;
356  proxy->m_aabbMax = aabbMax;
357  proxy->stage = m_stageCurrent;
359  if(docollide)
360  {
361  m_needcleanup=true;
362  if(!m_deferedcollide)
363  {
364  btDbvtTreeCollider collider(this);
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);
367  }
368  }
369  }
370 }
371 
372 
373 //
375  const btVector3& aabbMin,
376  const btVector3& aabbMax,
377  btDispatcher* /*dispatcher*/)
378 {
379  btDbvtProxy* proxy=(btDbvtProxy*)absproxy;
381  bool docollide=false;
382  if(proxy->stage==STAGECOUNT)
383  {/* fixed -> dynamic set */
384  m_sets[1].remove(proxy->leaf);
385  proxy->leaf=m_sets[0].insert(aabb,proxy);
386  docollide=true;
387  }
388  else
389  {/* dynamic set */
390  ++m_updates_call;
391  /* Teleporting */
392  m_sets[0].update(proxy->leaf,aabb);
393  ++m_updates_done;
394  docollide=true;
395  }
396  listremove(proxy,m_stageRoots[proxy->stage]);
397  proxy->m_aabbMin = aabbMin;
398  proxy->m_aabbMax = aabbMax;
399  proxy->stage = m_stageCurrent;
401  if(docollide)
402  {
403  m_needcleanup=true;
404  if(!m_deferedcollide)
405  {
406  btDbvtTreeCollider collider(this);
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);
409  }
410  }
411 }
412 
413 //
415 {
416  collide(dispatcher);
417 #if DBVT_BP_PROFILE
418  if(0==(m_pid%DBVT_BP_PROFILING_RATE))
419  {
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));
432  clear(m_profiling);
433  m_clock.reset();
434  }
435 #endif
436 
437  performDeferredRemoval(dispatcher);
438 
439 }
440 
442 {
443 
445  {
446 
447  btBroadphasePairArray& overlappingPairArray = m_paircache->getOverlappingPairArray();
448 
449  //perform a sort, to find duplicates and to sort 'invalid' pairs to the end
450  overlappingPairArray.quickSort(btBroadphasePairSortPredicate());
451 
452  int invalidPair = 0;
453 
454 
455  int i;
456 
457  btBroadphasePair previousPair;
458  previousPair.m_pProxy0 = 0;
459  previousPair.m_pProxy1 = 0;
460  previousPair.m_algorithm = 0;
461 
462 
463  for (i=0;i<overlappingPairArray.size();i++)
464  {
465 
466  btBroadphasePair& pair = overlappingPairArray[i];
467 
468  bool isDuplicate = (pair == previousPair);
469 
470  previousPair = pair;
471 
472  bool needsRemoval = false;
473 
474  if (!isDuplicate)
475  {
476  //important to perform AABB check that is consistent with the broadphase
477  btDbvtProxy* pa=(btDbvtProxy*)pair.m_pProxy0;
478  btDbvtProxy* pb=(btDbvtProxy*)pair.m_pProxy1;
479  bool hasOverlap = Intersect(pa->leaf->volume,pb->leaf->volume);
480 
481  if (hasOverlap)
482  {
483  needsRemoval = false;
484  } else
485  {
486  needsRemoval = true;
487  }
488  } else
489  {
490  //remove duplicate
491  needsRemoval = true;
492  //should have no algorithm
493  btAssert(!pair.m_algorithm);
494  }
495 
496  if (needsRemoval)
497  {
498  m_paircache->cleanOverlappingPair(pair,dispatcher);
499 
500  pair.m_pProxy0 = 0;
501  pair.m_pProxy1 = 0;
502  invalidPair++;
503  }
504 
505  }
506 
507  //perform a sort, to sort 'invalid' pairs to the end
508  overlappingPairArray.quickSort(btBroadphasePairSortPredicate());
509  overlappingPairArray.resize(overlappingPairArray.size() - invalidPair);
510  }
511 }
512 
513 //
515 {
516  /*printf("---------------------------------------------------------\n");
517  printf("m_sets[0].m_leaves=%d\n",m_sets[0].m_leaves);
518  printf("m_sets[1].m_leaves=%d\n",m_sets[1].m_leaves);
519  printf("numPairs = %d\n",getOverlappingPairCache()->getNumOverlappingPairs());
520  {
521  int i;
522  for (i=0;i<getOverlappingPairCache()->getNumOverlappingPairs();i++)
523  {
524  printf("pair[%d]=(%d,%d),",i,getOverlappingPairCache()->getOverlappingPairArray()[i].m_pProxy0->getUid(),
525  getOverlappingPairCache()->getOverlappingPairArray()[i].m_pProxy1->getUid());
526  }
527  printf("\n");
528  }
529 */
530 
531 
532 
533  SPC(m_profiling.m_total);
534  /* optimize */
535  m_sets[0].optimizeIncremental(1+(m_sets[0].m_leaves*m_dupdates)/100);
536  if(m_fixedleft)
537  {
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);
541  }
542  /* dynamic -> fixed set */
545  if(current)
546  {
547 #if DBVT_BP_ACCURATESLEEPING
548  btDbvtTreeCollider collider(this);
549 #endif
550  do {
551  btDbvtProxy* next=current->links[1];
552  listremove(current,m_stageRoots[current->stage]);
554 #if DBVT_BP_ACCURATESLEEPING
556  collider.proxy=current;
557  btDbvt::collideTV(m_sets[0].m_root,current->aabb,collider);
558  btDbvt::collideTV(m_sets[1].m_root,current->aabb,collider);
559 #endif
560  m_sets[0].remove(current->leaf);
562  current->leaf = m_sets[1].insert(curAabb,current);
563  current->stage = STAGECOUNT;
564  current = next;
565  } while(current);
567  m_needcleanup=true;
568  }
569  /* collide dynamics */
570  {
571  btDbvtTreeCollider collider(this);
572  if(m_deferedcollide)
573  {
574  SPC(m_profiling.m_fdcollide);
575  m_sets[0].collideTTpersistentStack(m_sets[0].m_root,m_sets[1].m_root,collider);
576  }
577  if(m_deferedcollide)
578  {
579  SPC(m_profiling.m_ddcollide);
580  m_sets[0].collideTTpersistentStack(m_sets[0].m_root,m_sets[0].m_root,collider);
581  }
582  }
583  /* clean up */
584  if(m_needcleanup)
585  {
586  SPC(m_profiling.m_cleanup);
588  if(pairs.size()>0)
589  {
590 
591  int ni=btMin(pairs.size(),btMax<int>(m_newpairs,(pairs.size()*m_cupdates)/100));
592  for(int i=0;i<ni;++i)
593  {
594  btBroadphasePair& p=pairs[(m_cid+i)%pairs.size()];
597  if(!Intersect(pa->leaf->volume,pb->leaf->volume))
598  {
599 #if DBVT_BP_SORTPAIRS
600  if(pa->m_uniqueId>pb->m_uniqueId)
601  btSwap(pa,pb);
602 #endif
603  m_paircache->removeOverlappingPair(pa,pb,dispatcher);
604  --ni;--i;
605  }
606  }
607  if(pairs.size()>0) m_cid=(m_cid+ni)%pairs.size(); else m_cid=0;
608  }
609  }
610  ++m_pid;
611  m_newpairs=1;
612  m_needcleanup=false;
613  if(m_updates_call>0)
615  else
616  { m_updates_ratio=0; }
617  m_updates_done/=2;
618  m_updates_call/=2;
619 }
620 
621 //
623 {
624  m_sets[0].optimizeTopDown();
625  m_sets[1].optimizeTopDown();
626 }
627 
628 //
630 {
631  return(m_paircache);
632 }
633 
634 //
636 {
637  return(m_paircache);
638 }
639 
640 //
642 {
643 
645 
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);
649  else
651  else if(!m_sets[1].empty()) bounds=m_sets[1].m_root->volume;
652  else
654  aabbMin=bounds.Mins();
655  aabbMax=bounds.Maxs();
656 }
657 
659 {
660 
661  int totalObjects = m_sets[0].m_leaves + m_sets[1].m_leaves;
662  if (!totalObjects)
663  {
664  //reset internal dynamic tree data structures
665  m_sets[0].clear();
666  m_sets[1].clear();
667 
668  m_deferedcollide = false;
669  m_needcleanup = true;
670  m_stageCurrent = 0;
671  m_fixedleft = 0;
672  m_fupdates = 1;
673  m_dupdates = 0;
674  m_cupdates = 10;
675  m_newpairs = 1;
676  m_updates_call = 0;
677  m_updates_done = 0;
678  m_updates_ratio = 0;
679 
680  m_gid = 0;
681  m_pid = 0;
682  m_cid = 0;
683  for(int i=0;i<=STAGECOUNT;++i)
684  {
685  m_stageRoots[i]=0;
686  }
687  }
688 }
689 
690 //
692 {}
693 
694 //
695 #if DBVT_BP_ENABLE_BENCHMARK
696 
697 struct btBroadphaseBenchmark
698 {
699  struct Experiment
700  {
701  const char* name;
702  int object_count;
703  int update_count;
704  int spawn_count;
705  int iterations;
706  btScalar speed;
707  btScalar amplitude;
708  };
709  struct Object
710  {
711  btVector3 center;
712  btVector3 extents;
713  btBroadphaseProxy* proxy;
714  btScalar time;
715  void update(btScalar speed,btScalar amplitude,btBroadphaseInterface* pbi)
716  {
717  time += speed;
718  center[0] = btCos(time*(btScalar)2.17)*amplitude+
719  btSin(time)*amplitude/2;
720  center[1] = btCos(time*(btScalar)1.38)*amplitude+
721  btSin(time)*amplitude;
722  center[2] = btSin(time*(btScalar)0.777)*amplitude;
723  pbi->setAabb(proxy,center-extents,center+extents,0);
724  }
725  };
726  static int UnsignedRand(int range=RAND_MAX-1) { return(rand()%(range+1)); }
727  static btScalar UnitRand() { return(UnsignedRand(16384)/(btScalar)16384); }
728  static void OutputTime(const char* name,btClock& c,unsigned count=0)
729  {
730  const unsigned long us=c.getTimeMicroseconds();
731  const unsigned long ms=(us+500)/1000;
732  const btScalar sec=us/(btScalar)(1000*1000);
733  if(count>0)
734  printf("%s : %u us (%u ms), %.2f/s\r\n",name,us,ms,count/sec);
735  else
736  printf("%s : %u us (%u ms)\r\n",name,us,ms);
737  }
738 };
739 
741 {
742  static const btBroadphaseBenchmark::Experiment experiments[]=
743  {
744  {"1024o.10%",1024,10,0,8192,(btScalar)0.005,(btScalar)100},
745  /*{"4096o.10%",4096,10,0,8192,(btScalar)0.005,(btScalar)100},
746  {"8192o.10%",8192,10,0,8192,(btScalar)0.005,(btScalar)100},*/
747  };
748  static const int nexperiments=sizeof(experiments)/sizeof(experiments[0]);
750  btClock wallclock;
751  /* Begin */
752  for(int iexp=0;iexp<nexperiments;++iexp)
753  {
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);
766  srand(180673);
767  /* Create objects */
768  wallclock.reset();
769  objects.reserve(object_count);
770  for(int i=0;i<object_count;++i)
771  {
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);
781  objects.push_back(po);
782  }
783  btBroadphaseBenchmark::OutputTime("\tInitialization",wallclock);
784  /* First update */
785  wallclock.reset();
786  for(int i=0;i<objects.size();++i)
787  {
788  objects[i]->update(speed,amplitude,pbi);
789  }
790  btBroadphaseBenchmark::OutputTime("\tFirst update",wallclock);
791  /* Updates */
792  wallclock.reset();
793  for(int i=0;i<experiment.iterations;++i)
794  {
795  for(int j=0;j<update_count;++j)
796  {
797  objects[j]->update(speed,amplitude,pbi);
798  }
800  }
801  btBroadphaseBenchmark::OutputTime("\tUpdate",wallclock,experiment.iterations);
802  /* Clean up */
803  wallclock.reset();
804  for(int i=0;i<objects.size();++i)
805  {
806  pbi->destroyProxy(objects[i]->proxy,0);
807  delete objects[i];
808  }
809  objects.resize(0);
810  btBroadphaseBenchmark::OutputTime("\tRelease",wallclock);
811  }
812 
813 }
814 #else
816 {}
817 #endif
818 
819 #if DBVT_BP_PROFILE
820 #undef SPC
821 #endif
822 
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)
Definition: btDbvt.h:667
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
Definition: btDbvt.h:136
virtual void cleanOverlappingPair(btBroadphasePair &pair, btDispatcher *dispatcher)=0
btBroadphaseRayCallback & m_rayCallback
static void listappend(T *item, T *&list)
virtual void resetPool(btDispatcher *dispatcher)
reset broadphase internal structures, to ensure determinism/reproducability
virtual bool hasDeferredRemoval()=0
btScalar btSin(btScalar x)
Definition: btScalar.h:477
void * data
Definition: btDbvt.h:187
btOverlappingPairCache * m_paircache
void Process(const btDbvtNode *na, const btDbvtNode *nb)
#define btAssert(x)
Definition: btScalar.h:131
btDbvtNode * insert(const btDbvtVolume &box, void *data)
Definition: btDbvt.cpp:517
The btClock is a portable basic clock that measures accurate time in seconds, use for profiling.
Definition: btQuickprof.h:24
The btDbvtBroadphase implements a broadphase using two dynamic AABB bounding volume hierarchies/trees...
btDbvtNode * m_root
Definition: btDbvt.h:262
void reset()
Resets the initial reference time.
void performDeferredRemoval(btDispatcher *dispatcher)
void collide(btDispatcher *dispatcher)
btDbvtNode * leaf
btDbvtProxy * links[2]
#define DBVT_BP_MARGIN
const unsigned int BT_MAX_THREAD_COUNT
Definition: btThreads.h:31
DBVT_INLINE const btVector3 & Maxs() const
Definition: btDbvt.h:137
The btOverlappingPairCache provides an interface for overlapping pair management (add,...
void Process(const btDbvtNode *leaf)
void update(btDbvtNode *leaf, int lookahead=-1)
Definition: btDbvt.cpp:526
btDbvtProxy * m_stageRoots[STAGECOUNT+1]
btDbvtBroadphase(btOverlappingPairCache *paircache=0)
void Process(const btDbvtNode *n)
void clear()
Definition: btDbvt.cpp:459
virtual void setAabb(btBroadphaseProxy *proxy, const btVector3 &aabbMin, const btVector3 &aabbMax, btDispatcher *dispatcher)
void optimizeIncremental(int passes)
Definition: btDbvt.cpp:497
virtual btBroadphasePairArray & getOverlappingPairArray()=0
#define SPC(_value_)
btDbvtBroadphase implementation by Nathanael Presson
virtual btOverlappingPairCache * getOverlappingPairCache()
void btSwap(T &a, T &b)
Definition: btScalar.h:621
static btDbvtAabbMm FromMM(const btVector3 &mi, const btVector3 &mx)
Definition: btDbvt.h:425
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
Definition: btDbvt.h:935
static int listcount(T *root)
virtual void printStats()
virtual void removeOverlappingPairsContainingProxy(btBroadphaseProxy *proxy0, btDispatcher *dispatcher)=0
static btDbvtAabbMm FromCR(const btVector3 &c, btScalar r)
Definition: btDbvt.h:419
The btBroadphaseInterface class provides an interface to detect aabb-overlapping object pairs.
virtual int getNumOverlappingPairs() const =0
void optimizeTopDown(int bu_treshold=128)
Definition: btDbvt.cpp:485
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.
Definition: btVector3.h:83
#define ATTRIBUTE_ALIGNED16(a)
Definition: btScalar.h:82
DBVT_PREFIX void collideTTpersistentStack(const btDbvtNode *root0, const btDbvtNode *root1, DBVT_IPOLICY)
Definition: btDbvt.h:803
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())
btDbvtVolume volume
Definition: btDbvt.h:180
btAlignedObjectArray< btAlignedObjectArray< const btDbvtNode * > > m_rayTestStacks
btScalar m_updates_ratio
btVector3 m_rayDirectionInverse
added some cached data to accelerate ray-AABB tests
DBVT_INLINE bool Intersect(const btDbvtAabbMm &a, const btDbvtAabbMm &b)
Definition: btDbvt.h:534
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)
Definition: btDbvt.cpp:284
virtual void calculateOverlappingPairs(btDispatcher *dispatcher)
calculateOverlappingPairs is optional: incremental algorithms (sweep and prune) might do it during th...
unsigned int btGetCurrentThreadIndex()
Definition: btThreads.cpp:304
btDbvtBroadphase * pbp
The btDispatcher interface class can be used in combination with broadphase to dispatch calculations ...
Definition: btDispatcher.h:75
const T & btMin(const T &a, const T &b)
Definition: btMinMax.h:23
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,...
void remove(btDbvtNode *leaf)
Definition: btDbvt.cpp:589
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...
Definition: btScalar.h:292
void quickSort(const L &CompareFunc)
virtual void * removeOverlappingPair(btBroadphaseProxy *proxy0, btBroadphaseProxy *proxy1, btDispatcher *dispatcher)=0
int m_leaves
Definition: btDbvt.h:265
btScalar btCos(btScalar x)
Definition: btScalar.h:476
DBVT_PREFIX void rayTestInternal(const btDbvtNode *root, const btVector3 &rayFrom, const btVector3 &rayTo, const btVector3 &rayDirectionInverse, unsigned int signs[3], btScalar lambda_max, const btVector3 &aabbMin, const btVector3 &aabbMax, btAlignedObjectArray< const btDbvtNode * > &stack, DBVT_IPOLICY) const
rayTestInternal is faster than rayTest, because it uses a persistent stack (to reduce dynamic memory ...
Definition: btDbvt.h:1007
DBVT_INLINE bool NotEqual(const btDbvtAabbMm &a, const btDbvtAabbMm &b)
Definition: btDbvt.h:690
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.