Bullet Collision Detection & Physics Library
btDbvt.cpp
Go to the documentation of this file.
1 /*
2 Bullet Continuous Collision Detection and Physics Library
3 Copyright (c) 2003-2006 Erwin Coumans http://continuousphysics.com/Bullet/
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 */
16 
17 #include "btDbvt.h"
18 
19 //
22 
23 //
25 {
27  void Process(const btDbvtNode* n) { nodes.push_back(n); }
28 };
29 
30 //
31 static DBVT_INLINE int indexof(const btDbvtNode* node)
32 {
33  return(node->parent->childs[1]==node);
34 }
35 
36 //
38  const btDbvtVolume& b)
39 {
40 #if (DBVT_MERGE_IMPL==DBVT_IMPL_SSE)
41  ATTRIBUTE_ALIGNED16( char locals[sizeof(btDbvtAabbMm)]);
42  btDbvtVolume* ptr = (btDbvtVolume*) locals;
43  btDbvtVolume& res=*ptr;
44 #else
45  btDbvtVolume res;
46 #endif
47  Merge(a,b,res);
48  return(res);
49 }
50 
51 // volume+edge lengths
53 {
54  const btVector3 edges=a.Lengths();
55  return( edges.x()*edges.y()*edges.z()+
56  edges.x()+edges.y()+edges.z());
57 }
58 
59 //
60 static void getmaxdepth(const btDbvtNode* node,int depth,int& maxdepth)
61 {
62  if(node->isinternal())
63  {
64  getmaxdepth(node->childs[0],depth+1,maxdepth);
65  getmaxdepth(node->childs[1],depth+1,maxdepth);
66  } else maxdepth=btMax(maxdepth,depth);
67 }
68 
69 //
70 static DBVT_INLINE void deletenode( btDbvt* pdbvt,
71  btDbvtNode* node)
72 {
73  btAlignedFree(pdbvt->m_free);
74  pdbvt->m_free=node;
75 }
76 
77 //
78 static void recursedeletenode( btDbvt* pdbvt,
79  btDbvtNode* node)
80 {
81  if(!node->isleaf())
82  {
83  recursedeletenode(pdbvt,node->childs[0]);
84  recursedeletenode(pdbvt,node->childs[1]);
85  }
86  if(node==pdbvt->m_root) pdbvt->m_root=0;
87  deletenode(pdbvt,node);
88 }
89 
90 //
92  btDbvtNode* parent,
93  void* data)
94 {
95  btDbvtNode* node;
96  if(pdbvt->m_free)
97  { node=pdbvt->m_free;pdbvt->m_free=0; }
98  else
99  { node=new(btAlignedAlloc(sizeof(btDbvtNode),16)) btDbvtNode(); }
100  node->parent = parent;
101  node->data = data;
102  node->childs[1] = 0;
103  return(node);
104 }
105 
106 //
108  btDbvtNode* parent,
109  const btDbvtVolume& volume,
110  void* data)
111 {
112  btDbvtNode* node=createnode(pdbvt,parent,data);
113  node->volume=volume;
114  return(node);
115 }
116 
117 //
119  btDbvtNode* parent,
120  const btDbvtVolume& volume0,
121  const btDbvtVolume& volume1,
122  void* data)
123 {
124  btDbvtNode* node=createnode(pdbvt,parent,data);
125  Merge(volume0,volume1,node->volume);
126  return(node);
127 }
128 
129 //
130 static void insertleaf( btDbvt* pdbvt,
131  btDbvtNode* root,
132  btDbvtNode* leaf)
133 {
134  if(!pdbvt->m_root)
135  {
136  pdbvt->m_root = leaf;
137  leaf->parent = 0;
138  }
139  else
140  {
141  if(!root->isleaf())
142  {
143  do {
144  root=root->childs[Select( leaf->volume,
145  root->childs[0]->volume,
146  root->childs[1]->volume)];
147  } while(!root->isleaf());
148  }
149  btDbvtNode* prev=root->parent;
150  btDbvtNode* node=createnode(pdbvt,prev,leaf->volume,root->volume,0);
151  if(prev)
152  {
153  prev->childs[indexof(root)] = node;
154  node->childs[0] = root;root->parent=node;
155  node->childs[1] = leaf;leaf->parent=node;
156  do {
157  if(!prev->volume.Contain(node->volume))
158  Merge(prev->childs[0]->volume,prev->childs[1]->volume,prev->volume);
159  else
160  break;
161  node=prev;
162  } while(0!=(prev=node->parent));
163  }
164  else
165  {
166  node->childs[0] = root;root->parent=node;
167  node->childs[1] = leaf;leaf->parent=node;
168  pdbvt->m_root = node;
169  }
170  }
171 }
172 
173 //
174 static btDbvtNode* removeleaf( btDbvt* pdbvt,
175  btDbvtNode* leaf)
176 {
177  if(leaf==pdbvt->m_root)
178  {
179  pdbvt->m_root=0;
180  return(0);
181  }
182  else
183  {
184  btDbvtNode* parent=leaf->parent;
185  btDbvtNode* prev=parent->parent;
186  btDbvtNode* sibling=parent->childs[1-indexof(leaf)];
187  if(prev)
188  {
189  prev->childs[indexof(parent)]=sibling;
190  sibling->parent=prev;
191  deletenode(pdbvt,parent);
192  while(prev)
193  {
194  const btDbvtVolume pb=prev->volume;
195  Merge(prev->childs[0]->volume,prev->childs[1]->volume,prev->volume);
196  if(NotEqual(pb,prev->volume))
197  {
198  prev=prev->parent;
199  } else break;
200  }
201  return(prev?prev:pdbvt->m_root);
202  }
203  else
204  {
205  pdbvt->m_root=sibling;
206  sibling->parent=0;
207  deletenode(pdbvt,parent);
208  return(pdbvt->m_root);
209  }
210  }
211 }
212 
213 //
214 static void fetchleaves(btDbvt* pdbvt,
215  btDbvtNode* root,
216  tNodeArray& leaves,
217  int depth=-1)
218 {
219  if(root->isinternal()&&depth)
220  {
221  fetchleaves(pdbvt,root->childs[0],leaves,depth-1);
222  fetchleaves(pdbvt,root->childs[1],leaves,depth-1);
223  deletenode(pdbvt,root);
224  }
225  else
226  {
227  leaves.push_back(root);
228  }
229 }
230 
231 //
232 static bool leftOfAxis( const btDbvtNode* node,
233  const btVector3& org,
234  const btVector3& axis)
235 {
236  return btDot(axis, node->volume.Center() - org) <= 0;
237 }
238 
239 
240 // Partitions leaves such that leaves[0, n) are on the
241 // left of axis, and leaves[n, count) are on the right
242 // of axis. returns N.
243 static int split( btDbvtNode** leaves,
244  int count,
245  const btVector3& org,
246  const btVector3& axis)
247 {
248  int begin=0;
249  int end=count;
250  for(;;)
251  {
252  while(begin!=end && leftOfAxis(leaves[begin],org,axis))
253  {
254  ++begin;
255  }
256 
257  if(begin==end)
258  {
259  break;
260  }
261 
262  while(begin!=end && !leftOfAxis(leaves[end-1],org,axis))
263  {
264  --end;
265  }
266 
267  if(begin==end)
268  {
269  break;
270  }
271 
272  // swap out of place nodes
273  --end;
274  btDbvtNode* temp=leaves[begin];
275  leaves[begin]=leaves[end];
276  leaves[end]=temp;
277  ++begin;
278  }
279 
280  return begin;
281 }
282 
283 //
284 static btDbvtVolume bounds( btDbvtNode** leaves,
285  int count)
286 {
287 #if DBVT_MERGE_IMPL==DBVT_IMPL_SSE
288  ATTRIBUTE_ALIGNED16(char locals[sizeof(btDbvtVolume)]);
289  btDbvtVolume* ptr = (btDbvtVolume*) locals;
290  btDbvtVolume& volume=*ptr;
291  volume=leaves[0]->volume;
292 #else
293  btDbvtVolume volume=leaves[0]->volume;
294 #endif
295  for(int i=1,ni=count;i<ni;++i)
296  {
297  Merge(volume,leaves[i]->volume,volume);
298  }
299  return(volume);
300 }
301 
302 //
303 static void bottomup( btDbvt* pdbvt,
304  btDbvtNode** leaves,
305  int count)
306 {
307  while(count>1)
308  {
309  btScalar minsize=SIMD_INFINITY;
310  int minidx[2]={-1,-1};
311  for(int i=0;i<count;++i)
312  {
313  for(int j=i+1;j<count;++j)
314  {
315  const btScalar sz=size(merge(leaves[i]->volume,leaves[j]->volume));
316  if(sz<minsize)
317  {
318  minsize = sz;
319  minidx[0] = i;
320  minidx[1] = j;
321  }
322  }
323  }
324  btDbvtNode* n[] = {leaves[minidx[0]],leaves[minidx[1]]};
325  btDbvtNode* p = createnode(pdbvt,0,n[0]->volume,n[1]->volume,0);
326  p->childs[0] = n[0];
327  p->childs[1] = n[1];
328  n[0]->parent = p;
329  n[1]->parent = p;
330  leaves[minidx[0]] = p;
331  leaves[minidx[1]] = leaves[count-1];
332  --count;
333  }
334 }
335 
336 //
337 static btDbvtNode* topdown(btDbvt* pdbvt,
338  btDbvtNode** leaves,
339  int count,
340  int bu_treshold)
341 {
342  static const btVector3 axis[]={btVector3(1,0,0),
343  btVector3(0,1,0),
344  btVector3(0,0,1)};
345  btAssert(bu_treshold>2);
346  if(count>1)
347  {
348  if(count>bu_treshold)
349  {
350  const btDbvtVolume vol=bounds(leaves,count);
351  const btVector3 org=vol.Center();
352  int partition;
353  int bestaxis=-1;
354  int bestmidp=count;
355  int splitcount[3][2]={{0,0},{0,0},{0,0}};
356  int i;
357  for( i=0;i<count;++i)
358  {
359  const btVector3 x=leaves[i]->volume.Center()-org;
360  for(int j=0;j<3;++j)
361  {
362  ++splitcount[j][btDot(x,axis[j])>0?1:0];
363  }
364  }
365  for( i=0;i<3;++i)
366  {
367  if((splitcount[i][0]>0)&&(splitcount[i][1]>0))
368  {
369  const int midp=(int)btFabs(btScalar(splitcount[i][0]-splitcount[i][1]));
370  if(midp<bestmidp)
371  {
372  bestaxis=i;
373  bestmidp=midp;
374  }
375  }
376  }
377  if(bestaxis>=0)
378  {
379  partition=split(leaves,count,org,axis[bestaxis]);
380  btAssert(partition!=0 && partition!=count);
381  }
382  else
383  {
384  partition=count/2+1;
385  }
386  btDbvtNode* node=createnode(pdbvt,0,vol,0);
387  node->childs[0]=topdown(pdbvt,&leaves[0],partition,bu_treshold);
388  node->childs[1]=topdown(pdbvt,&leaves[partition],count-partition,bu_treshold);
389  node->childs[0]->parent=node;
390  node->childs[1]->parent=node;
391  return(node);
392  }
393  else
394  {
395  bottomup(pdbvt,leaves,count);
396  return(leaves[0]);
397  }
398  }
399  return(leaves[0]);
400 }
401 
402 //
404 {
405  btDbvtNode* p=n->parent;
406  btAssert(n->isinternal());
407  if(p>n)
408  {
409  const int i=indexof(n);
410  const int j=1-i;
411  btDbvtNode* s=p->childs[j];
412  btDbvtNode* q=p->parent;
413  btAssert(n==p->childs[i]);
414  if(q) q->childs[indexof(p)]=n; else r=n;
415  s->parent=n;
416  p->parent=n;
417  n->parent=q;
418  p->childs[0]=n->childs[0];
419  p->childs[1]=n->childs[1];
420  n->childs[0]->parent=p;
421  n->childs[1]->parent=p;
422  n->childs[i]=p;
423  n->childs[j]=s;
424  btSwap(p->volume,n->volume);
425  return(p);
426  }
427  return(n);
428 }
429 
430 #if 0
431 static DBVT_INLINE btDbvtNode* walkup(btDbvtNode* n,int count)
432 {
433  while(n&&(count--)) n=n->parent;
434  return(n);
435 }
436 #endif
437 
438 //
439 // Api
440 //
441 
442 //
444 {
445  m_root = 0;
446  m_free = 0;
447  m_lkhd = -1;
448  m_leaves = 0;
449  m_opath = 0;
450 }
451 
452 //
454 {
455  clear();
456 }
457 
458 //
460 {
461  if(m_root)
462  recursedeletenode(this,m_root);
463  btAlignedFree(m_free);
464  m_free=0;
465  m_lkhd = -1;
466  m_stkStack.clear();
467  m_opath = 0;
468 
469 }
470 
471 //
473 {
474  if(m_root)
475  {
476  tNodeArray leaves;
477  leaves.reserve(m_leaves);
478  fetchleaves(this,m_root,leaves);
479  bottomup(this,&leaves[0],leaves.size());
480  m_root=leaves[0];
481  }
482 }
483 
484 //
485 void btDbvt::optimizeTopDown(int bu_treshold)
486 {
487  if(m_root)
488  {
489  tNodeArray leaves;
490  leaves.reserve(m_leaves);
491  fetchleaves(this,m_root,leaves);
492  m_root=topdown(this,&leaves[0],leaves.size(),bu_treshold);
493  }
494 }
495 
496 //
498 {
499  if(passes<0) passes=m_leaves;
500  if(m_root&&(passes>0))
501  {
502  do {
503  btDbvtNode* node=m_root;
504  unsigned bit=0;
505  while(node->isinternal())
506  {
507  node=sort(node,m_root)->childs[(m_opath>>bit)&1];
508  bit=(bit+1)&(sizeof(unsigned)*8-1);
509  }
510  update(node);
511  ++m_opath;
512  } while(--passes);
513  }
514 }
515 
516 //
517 btDbvtNode* btDbvt::insert(const btDbvtVolume& volume,void* data)
518 {
519  btDbvtNode* leaf=createnode(this,0,volume,data);
520  insertleaf(this,m_root,leaf);
521  ++m_leaves;
522  return(leaf);
523 }
524 
525 //
526 void btDbvt::update(btDbvtNode* leaf,int lookahead)
527 {
528  btDbvtNode* root=removeleaf(this,leaf);
529  if(root)
530  {
531  if(lookahead>=0)
532  {
533  for(int i=0;(i<lookahead)&&root->parent;++i)
534  {
535  root=root->parent;
536  }
537  } else root=m_root;
538  }
539  insertleaf(this,root,leaf);
540 }
541 
542 //
544 {
545  btDbvtNode* root=removeleaf(this,leaf);
546  if(root)
547  {
548  if(m_lkhd>=0)
549  {
550  for(int i=0;(i<m_lkhd)&&root->parent;++i)
551  {
552  root=root->parent;
553  }
554  } else root=m_root;
555  }
556  leaf->volume=volume;
557  insertleaf(this,root,leaf);
558 }
559 
560 //
561 bool btDbvt::update(btDbvtNode* leaf,btDbvtVolume& volume,const btVector3& velocity,btScalar margin)
562 {
563  if(leaf->volume.Contain(volume)) return(false);
564  volume.Expand(btVector3(margin,margin,margin));
565  volume.SignedExpand(velocity);
566  update(leaf,volume);
567  return(true);
568 }
569 
570 //
571 bool btDbvt::update(btDbvtNode* leaf,btDbvtVolume& volume,const btVector3& velocity)
572 {
573  if(leaf->volume.Contain(volume)) return(false);
574  volume.SignedExpand(velocity);
575  update(leaf,volume);
576  return(true);
577 }
578 
579 //
580 bool btDbvt::update(btDbvtNode* leaf,btDbvtVolume& volume,btScalar margin)
581 {
582  if(leaf->volume.Contain(volume)) return(false);
583  volume.Expand(btVector3(margin,margin,margin));
584  update(leaf,volume);
585  return(true);
586 }
587 
588 //
590 {
591  removeleaf(this,leaf);
592  deletenode(this,leaf);
593  --m_leaves;
594 }
595 
596 //
597 void btDbvt::write(IWriter* iwriter) const
598 {
600  nodes.nodes.reserve(m_leaves*2);
601  enumNodes(m_root,nodes);
602  iwriter->Prepare(m_root,nodes.nodes.size());
603  for(int i=0;i<nodes.nodes.size();++i)
604  {
605  const btDbvtNode* n=nodes.nodes[i];
606  int p=-1;
607  if(n->parent) p=nodes.nodes.findLinearSearch(n->parent);
608  if(n->isinternal())
609  {
610  const int c0=nodes.nodes.findLinearSearch(n->childs[0]);
611  const int c1=nodes.nodes.findLinearSearch(n->childs[1]);
612  iwriter->WriteNode(n,i,p,c0,c1);
613  }
614  else
615  {
616  iwriter->WriteLeaf(n,i,p);
617  }
618  }
619 }
620 
621 //
622 void btDbvt::clone(btDbvt& dest,IClone* iclone) const
623 {
624  dest.clear();
625  if(m_root!=0)
626  {
628  stack.reserve(m_leaves);
629  stack.push_back(sStkCLN(m_root,0));
630  do {
631  const int i=stack.size()-1;
632  const sStkCLN e=stack[i];
633  btDbvtNode* n=createnode(&dest,e.parent,e.node->volume,e.node->data);
634  stack.pop_back();
635  if(e.parent!=0)
636  e.parent->childs[i&1]=n;
637  else
638  dest.m_root=n;
639  if(e.node->isinternal())
640  {
641  stack.push_back(sStkCLN(e.node->childs[0],n));
642  stack.push_back(sStkCLN(e.node->childs[1],n));
643  }
644  else
645  {
646  iclone->CloneLeaf(n);
647  }
648  } while(stack.size()>0);
649  }
650 }
651 
652 //
653 int btDbvt::maxdepth(const btDbvtNode* node)
654 {
655  int depth=0;
656  if(node) getmaxdepth(node,1,depth);
657  return(depth);
658 }
659 
660 //
662 {
663  if(node->isinternal())
664  return(countLeaves(node->childs[0])+countLeaves(node->childs[1]));
665  else
666  return(1);
667 }
668 
669 //
671 {
672  if(node->isinternal())
673  {
674  extractLeaves(node->childs[0],leaves);
675  extractLeaves(node->childs[1],leaves);
676  }
677  else
678  {
679  leaves.push_back(node);
680  }
681 }
682 
683 //
684 #if DBVT_ENABLE_BENCHMARK
685 
686 #include <stdio.h>
687 #include <stdlib.h>
688 #include "LinearMath/btQuickProf.h"
689 
690 /*
691 q6600,2.4ghz
692 
693 /Ox /Ob2 /Oi /Ot /I "." /I "..\.." /I "..\..\src" /D "NDEBUG" /D "_LIB" /D "_WINDOWS" /D "_CRT_SECURE_NO_DEPRECATE" /D "_CRT_NONSTDC_NO_DEPRECATE" /D "WIN32"
694 /GF /FD /MT /GS- /Gy /arch:SSE2 /Zc:wchar_t- /Fp"..\..\out\release8\build\libbulletcollision\libbulletcollision.pch"
695 /Fo"..\..\out\release8\build\libbulletcollision\\"
696 /Fd"..\..\out\release8\build\libbulletcollision\bulletcollision.pdb"
697 /W3 /nologo /c /Wp64 /Zi /errorReport:prompt
698 
699 Benchmarking dbvt...
700 World scale: 100.000000
701 Extents base: 1.000000
702 Extents range: 4.000000
703 Leaves: 8192
704 sizeof(btDbvtVolume): 32 bytes
705 sizeof(btDbvtNode): 44 bytes
706 [1] btDbvtVolume intersections: 3499 ms (-1%)
707 [2] btDbvtVolume merges: 1934 ms (0%)
708 [3] btDbvt::collideTT: 5485 ms (-21%)
709 [4] btDbvt::collideTT self: 2814 ms (-20%)
710 [5] btDbvt::collideTT xform: 7379 ms (-1%)
711 [6] btDbvt::collideTT xform,self: 7270 ms (-2%)
712 [7] btDbvt::rayTest: 6314 ms (0%),(332143 r/s)
713 [8] insert/remove: 2093 ms (0%),(1001983 ir/s)
714 [9] updates (teleport): 1879 ms (-3%),(1116100 u/s)
715 [10] updates (jitter): 1244 ms (-4%),(1685813 u/s)
716 [11] optimize (incremental): 2514 ms (0%),(1668000 o/s)
717 [12] btDbvtVolume notequal: 3659 ms (0%)
718 [13] culling(OCL+fullsort): 2218 ms (0%),(461 t/s)
719 [14] culling(OCL+qsort): 3688 ms (5%),(2221 t/s)
720 [15] culling(KDOP+qsort): 1139 ms (-1%),(7192 t/s)
721 [16] insert/remove batch(256): 5092 ms (0%),(823704 bir/s)
722 [17] btDbvtVolume select: 3419 ms (0%)
723 */
724 
725 struct btDbvtBenchmark
726 {
727  struct NilPolicy : btDbvt::ICollide
728  {
729  NilPolicy() : m_pcount(0),m_depth(-SIMD_INFINITY),m_checksort(true) {}
730  void Process(const btDbvtNode*,const btDbvtNode*) { ++m_pcount; }
731  void Process(const btDbvtNode*) { ++m_pcount; }
732  void Process(const btDbvtNode*,btScalar depth)
733  {
734  ++m_pcount;
735  if(m_checksort)
736  { if(depth>=m_depth) m_depth=depth; else printf("wrong depth: %f (should be >= %f)\r\n",depth,m_depth); }
737  }
738  int m_pcount;
739  btScalar m_depth;
740  bool m_checksort;
741  };
742  struct P14 : btDbvt::ICollide
743  {
744  struct Node
745  {
746  const btDbvtNode* leaf;
747  btScalar depth;
748  };
749  void Process(const btDbvtNode* leaf,btScalar depth)
750  {
751  Node n;
752  n.leaf = leaf;
753  n.depth = depth;
754  }
755  static int sortfnc(const Node& a,const Node& b)
756  {
757  if(a.depth<b.depth) return(+1);
758  if(a.depth>b.depth) return(-1);
759  return(0);
760  }
762  };
763  struct P15 : btDbvt::ICollide
764  {
765  struct Node
766  {
767  const btDbvtNode* leaf;
768  btScalar depth;
769  };
770  void Process(const btDbvtNode* leaf)
771  {
772  Node n;
773  n.leaf = leaf;
774  n.depth = dot(leaf->volume.Center(),m_axis);
775  }
776  static int sortfnc(const Node& a,const Node& b)
777  {
778  if(a.depth<b.depth) return(+1);
779  if(a.depth>b.depth) return(-1);
780  return(0);
781  }
783  btVector3 m_axis;
784  };
785  static btScalar RandUnit()
786  {
787  return(rand()/(btScalar)RAND_MAX);
788  }
789  static btVector3 RandVector3()
790  {
791  return(btVector3(RandUnit(),RandUnit(),RandUnit()));
792  }
793  static btVector3 RandVector3(btScalar cs)
794  {
795  return(RandVector3()*cs-btVector3(cs,cs,cs)/2);
796  }
797  static btDbvtVolume RandVolume(btScalar cs,btScalar eb,btScalar es)
798  {
799  return(btDbvtVolume::FromCE(RandVector3(cs),btVector3(eb,eb,eb)+RandVector3()*es));
800  }
801  static btTransform RandTransform(btScalar cs)
802  {
803  btTransform t;
804  t.setOrigin(RandVector3(cs));
805  t.setRotation(btQuaternion(RandUnit()*SIMD_PI*2,RandUnit()*SIMD_PI*2,RandUnit()*SIMD_PI*2).normalized());
806  return(t);
807  }
808  static void RandTree(btScalar cs,btScalar eb,btScalar es,int leaves,btDbvt& dbvt)
809  {
810  dbvt.clear();
811  for(int i=0;i<leaves;++i)
812  {
813  dbvt.insert(RandVolume(cs,eb,es),0);
814  }
815  }
816 };
817 
818 void btDbvt::benchmark()
819 {
820  static const btScalar cfgVolumeCenterScale = 100;
821  static const btScalar cfgVolumeExentsBase = 1;
822  static const btScalar cfgVolumeExentsScale = 4;
823  static const int cfgLeaves = 8192;
824  static const bool cfgEnable = true;
825 
826  //[1] btDbvtVolume intersections
827  bool cfgBenchmark1_Enable = cfgEnable;
828  static const int cfgBenchmark1_Iterations = 8;
829  static const int cfgBenchmark1_Reference = 3499;
830  //[2] btDbvtVolume merges
831  bool cfgBenchmark2_Enable = cfgEnable;
832  static const int cfgBenchmark2_Iterations = 4;
833  static const int cfgBenchmark2_Reference = 1945;
834  //[3] btDbvt::collideTT
835  bool cfgBenchmark3_Enable = cfgEnable;
836  static const int cfgBenchmark3_Iterations = 512;
837  static const int cfgBenchmark3_Reference = 5485;
838  //[4] btDbvt::collideTT self
839  bool cfgBenchmark4_Enable = cfgEnable;
840  static const int cfgBenchmark4_Iterations = 512;
841  static const int cfgBenchmark4_Reference = 2814;
842  //[5] btDbvt::collideTT xform
843  bool cfgBenchmark5_Enable = cfgEnable;
844  static const int cfgBenchmark5_Iterations = 512;
845  static const btScalar cfgBenchmark5_OffsetScale = 2;
846  static const int cfgBenchmark5_Reference = 7379;
847  //[6] btDbvt::collideTT xform,self
848  bool cfgBenchmark6_Enable = cfgEnable;
849  static const int cfgBenchmark6_Iterations = 512;
850  static const btScalar cfgBenchmark6_OffsetScale = 2;
851  static const int cfgBenchmark6_Reference = 7270;
852  //[7] btDbvt::rayTest
853  bool cfgBenchmark7_Enable = cfgEnable;
854  static const int cfgBenchmark7_Passes = 32;
855  static const int cfgBenchmark7_Iterations = 65536;
856  static const int cfgBenchmark7_Reference = 6307;
857  //[8] insert/remove
858  bool cfgBenchmark8_Enable = cfgEnable;
859  static const int cfgBenchmark8_Passes = 32;
860  static const int cfgBenchmark8_Iterations = 65536;
861  static const int cfgBenchmark8_Reference = 2105;
862  //[9] updates (teleport)
863  bool cfgBenchmark9_Enable = cfgEnable;
864  static const int cfgBenchmark9_Passes = 32;
865  static const int cfgBenchmark9_Iterations = 65536;
866  static const int cfgBenchmark9_Reference = 1879;
867  //[10] updates (jitter)
868  bool cfgBenchmark10_Enable = cfgEnable;
869  static const btScalar cfgBenchmark10_Scale = cfgVolumeCenterScale/10000;
870  static const int cfgBenchmark10_Passes = 32;
871  static const int cfgBenchmark10_Iterations = 65536;
872  static const int cfgBenchmark10_Reference = 1244;
873  //[11] optimize (incremental)
874  bool cfgBenchmark11_Enable = cfgEnable;
875  static const int cfgBenchmark11_Passes = 64;
876  static const int cfgBenchmark11_Iterations = 65536;
877  static const int cfgBenchmark11_Reference = 2510;
878  //[12] btDbvtVolume notequal
879  bool cfgBenchmark12_Enable = cfgEnable;
880  static const int cfgBenchmark12_Iterations = 32;
881  static const int cfgBenchmark12_Reference = 3677;
882  //[13] culling(OCL+fullsort)
883  bool cfgBenchmark13_Enable = cfgEnable;
884  static const int cfgBenchmark13_Iterations = 1024;
885  static const int cfgBenchmark13_Reference = 2231;
886  //[14] culling(OCL+qsort)
887  bool cfgBenchmark14_Enable = cfgEnable;
888  static const int cfgBenchmark14_Iterations = 8192;
889  static const int cfgBenchmark14_Reference = 3500;
890  //[15] culling(KDOP+qsort)
891  bool cfgBenchmark15_Enable = cfgEnable;
892  static const int cfgBenchmark15_Iterations = 8192;
893  static const int cfgBenchmark15_Reference = 1151;
894  //[16] insert/remove batch
895  bool cfgBenchmark16_Enable = cfgEnable;
896  static const int cfgBenchmark16_BatchCount = 256;
897  static const int cfgBenchmark16_Passes = 16384;
898  static const int cfgBenchmark16_Reference = 5138;
899  //[17] select
900  bool cfgBenchmark17_Enable = cfgEnable;
901  static const int cfgBenchmark17_Iterations = 4;
902  static const int cfgBenchmark17_Reference = 3390;
903 
904  btClock wallclock;
905  printf("Benchmarking dbvt...\r\n");
906  printf("\tWorld scale: %f\r\n",cfgVolumeCenterScale);
907  printf("\tExtents base: %f\r\n",cfgVolumeExentsBase);
908  printf("\tExtents range: %f\r\n",cfgVolumeExentsScale);
909  printf("\tLeaves: %u\r\n",cfgLeaves);
910  printf("\tsizeof(btDbvtVolume): %u bytes\r\n",sizeof(btDbvtVolume));
911  printf("\tsizeof(btDbvtNode): %u bytes\r\n",sizeof(btDbvtNode));
912  if(cfgBenchmark1_Enable)
913  {// Benchmark 1
914  srand(380843);
917  volumes.resize(cfgLeaves);
918  results.resize(cfgLeaves);
919  for(int i=0;i<cfgLeaves;++i)
920  {
921  volumes[i]=btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale);
922  }
923  printf("[1] btDbvtVolume intersections: ");
924  wallclock.reset();
925  for(int i=0;i<cfgBenchmark1_Iterations;++i)
926  {
927  for(int j=0;j<cfgLeaves;++j)
928  {
929  for(int k=0;k<cfgLeaves;++k)
930  {
931  results[k]=Intersect(volumes[j],volumes[k]);
932  }
933  }
934  }
935  const int time=(int)wallclock.getTimeMilliseconds();
936  printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark1_Reference)*100/time);
937  }
938  if(cfgBenchmark2_Enable)
939  {// Benchmark 2
940  srand(380843);
943  volumes.resize(cfgLeaves);
944  results.resize(cfgLeaves);
945  for(int i=0;i<cfgLeaves;++i)
946  {
947  volumes[i]=btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale);
948  }
949  printf("[2] btDbvtVolume merges: ");
950  wallclock.reset();
951  for(int i=0;i<cfgBenchmark2_Iterations;++i)
952  {
953  for(int j=0;j<cfgLeaves;++j)
954  {
955  for(int k=0;k<cfgLeaves;++k)
956  {
957  Merge(volumes[j],volumes[k],results[k]);
958  }
959  }
960  }
961  const int time=(int)wallclock.getTimeMilliseconds();
962  printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark2_Reference)*100/time);
963  }
964  if(cfgBenchmark3_Enable)
965  {// Benchmark 3
966  srand(380843);
967  btDbvt dbvt[2];
968  btDbvtBenchmark::NilPolicy policy;
969  btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt[0]);
970  btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt[1]);
971  dbvt[0].optimizeTopDown();
972  dbvt[1].optimizeTopDown();
973  printf("[3] btDbvt::collideTT: ");
974  wallclock.reset();
975  for(int i=0;i<cfgBenchmark3_Iterations;++i)
976  {
977  btDbvt::collideTT(dbvt[0].m_root,dbvt[1].m_root,policy);
978  }
979  const int time=(int)wallclock.getTimeMilliseconds();
980  printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark3_Reference)*100/time);
981  }
982  if(cfgBenchmark4_Enable)
983  {// Benchmark 4
984  srand(380843);
985  btDbvt dbvt;
986  btDbvtBenchmark::NilPolicy policy;
987  btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
988  dbvt.optimizeTopDown();
989  printf("[4] btDbvt::collideTT self: ");
990  wallclock.reset();
991  for(int i=0;i<cfgBenchmark4_Iterations;++i)
992  {
993  btDbvt::collideTT(dbvt.m_root,dbvt.m_root,policy);
994  }
995  const int time=(int)wallclock.getTimeMilliseconds();
996  printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark4_Reference)*100/time);
997  }
998  if(cfgBenchmark5_Enable)
999  {// Benchmark 5
1000  srand(380843);
1001  btDbvt dbvt[2];
1003  btDbvtBenchmark::NilPolicy policy;
1004  transforms.resize(cfgBenchmark5_Iterations);
1005  for(int i=0;i<transforms.size();++i)
1006  {
1007  transforms[i]=btDbvtBenchmark::RandTransform(cfgVolumeCenterScale*cfgBenchmark5_OffsetScale);
1008  }
1009  btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt[0]);
1010  btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt[1]);
1011  dbvt[0].optimizeTopDown();
1012  dbvt[1].optimizeTopDown();
1013  printf("[5] btDbvt::collideTT xform: ");
1014  wallclock.reset();
1015  for(int i=0;i<cfgBenchmark5_Iterations;++i)
1016  {
1017  btDbvt::collideTT(dbvt[0].m_root,dbvt[1].m_root,transforms[i],policy);
1018  }
1019  const int time=(int)wallclock.getTimeMilliseconds();
1020  printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark5_Reference)*100/time);
1021  }
1022  if(cfgBenchmark6_Enable)
1023  {// Benchmark 6
1024  srand(380843);
1025  btDbvt dbvt;
1027  btDbvtBenchmark::NilPolicy policy;
1028  transforms.resize(cfgBenchmark6_Iterations);
1029  for(int i=0;i<transforms.size();++i)
1030  {
1031  transforms[i]=btDbvtBenchmark::RandTransform(cfgVolumeCenterScale*cfgBenchmark6_OffsetScale);
1032  }
1033  btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1034  dbvt.optimizeTopDown();
1035  printf("[6] btDbvt::collideTT xform,self: ");
1036  wallclock.reset();
1037  for(int i=0;i<cfgBenchmark6_Iterations;++i)
1038  {
1039  btDbvt::collideTT(dbvt.m_root,dbvt.m_root,transforms[i],policy);
1040  }
1041  const int time=(int)wallclock.getTimeMilliseconds();
1042  printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark6_Reference)*100/time);
1043  }
1044  if(cfgBenchmark7_Enable)
1045  {// Benchmark 7
1046  srand(380843);
1047  btDbvt dbvt;
1050  btDbvtBenchmark::NilPolicy policy;
1051  rayorg.resize(cfgBenchmark7_Iterations);
1052  raydir.resize(cfgBenchmark7_Iterations);
1053  for(int i=0;i<rayorg.size();++i)
1054  {
1055  rayorg[i]=btDbvtBenchmark::RandVector3(cfgVolumeCenterScale*2);
1056  raydir[i]=btDbvtBenchmark::RandVector3(cfgVolumeCenterScale*2);
1057  }
1058  btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1059  dbvt.optimizeTopDown();
1060  printf("[7] btDbvt::rayTest: ");
1061  wallclock.reset();
1062  for(int i=0;i<cfgBenchmark7_Passes;++i)
1063  {
1064  for(int j=0;j<cfgBenchmark7_Iterations;++j)
1065  {
1066  btDbvt::rayTest(dbvt.m_root,rayorg[j],rayorg[j]+raydir[j],policy);
1067  }
1068  }
1069  const int time=(int)wallclock.getTimeMilliseconds();
1070  unsigned rays=cfgBenchmark7_Passes*cfgBenchmark7_Iterations;
1071  printf("%u ms (%i%%),(%u r/s)\r\n",time,(time-cfgBenchmark7_Reference)*100/time,(rays*1000)/time);
1072  }
1073  if(cfgBenchmark8_Enable)
1074  {// Benchmark 8
1075  srand(380843);
1076  btDbvt dbvt;
1077  btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1078  dbvt.optimizeTopDown();
1079  printf("[8] insert/remove: ");
1080  wallclock.reset();
1081  for(int i=0;i<cfgBenchmark8_Passes;++i)
1082  {
1083  for(int j=0;j<cfgBenchmark8_Iterations;++j)
1084  {
1085  dbvt.remove(dbvt.insert(btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale),0));
1086  }
1087  }
1088  const int time=(int)wallclock.getTimeMilliseconds();
1089  const int ir=cfgBenchmark8_Passes*cfgBenchmark8_Iterations;
1090  printf("%u ms (%i%%),(%u ir/s)\r\n",time,(time-cfgBenchmark8_Reference)*100/time,ir*1000/time);
1091  }
1092  if(cfgBenchmark9_Enable)
1093  {// Benchmark 9
1094  srand(380843);
1095  btDbvt dbvt;
1097  btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1098  dbvt.optimizeTopDown();
1099  dbvt.extractLeaves(dbvt.m_root,leaves);
1100  printf("[9] updates (teleport): ");
1101  wallclock.reset();
1102  for(int i=0;i<cfgBenchmark9_Passes;++i)
1103  {
1104  for(int j=0;j<cfgBenchmark9_Iterations;++j)
1105  {
1106  dbvt.update(const_cast<btDbvtNode*>(leaves[rand()%cfgLeaves]),
1107  btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale));
1108  }
1109  }
1110  const int time=(int)wallclock.getTimeMilliseconds();
1111  const int up=cfgBenchmark9_Passes*cfgBenchmark9_Iterations;
1112  printf("%u ms (%i%%),(%u u/s)\r\n",time,(time-cfgBenchmark9_Reference)*100/time,up*1000/time);
1113  }
1114  if(cfgBenchmark10_Enable)
1115  {// Benchmark 10
1116  srand(380843);
1117  btDbvt dbvt;
1120  vectors.resize(cfgBenchmark10_Iterations);
1121  for(int i=0;i<vectors.size();++i)
1122  {
1123  vectors[i]=(btDbvtBenchmark::RandVector3()*2-btVector3(1,1,1))*cfgBenchmark10_Scale;
1124  }
1125  btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1126  dbvt.optimizeTopDown();
1127  dbvt.extractLeaves(dbvt.m_root,leaves);
1128  printf("[10] updates (jitter): ");
1129  wallclock.reset();
1130 
1131  for(int i=0;i<cfgBenchmark10_Passes;++i)
1132  {
1133  for(int j=0;j<cfgBenchmark10_Iterations;++j)
1134  {
1135  const btVector3& d=vectors[j];
1136  btDbvtNode* l=const_cast<btDbvtNode*>(leaves[rand()%cfgLeaves]);
1138  dbvt.update(l,v);
1139  }
1140  }
1141  const int time=(int)wallclock.getTimeMilliseconds();
1142  const int up=cfgBenchmark10_Passes*cfgBenchmark10_Iterations;
1143  printf("%u ms (%i%%),(%u u/s)\r\n",time,(time-cfgBenchmark10_Reference)*100/time,up*1000/time);
1144  }
1145  if(cfgBenchmark11_Enable)
1146  {// Benchmark 11
1147  srand(380843);
1148  btDbvt dbvt;
1149  btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1150  dbvt.optimizeTopDown();
1151  printf("[11] optimize (incremental): ");
1152  wallclock.reset();
1153  for(int i=0;i<cfgBenchmark11_Passes;++i)
1154  {
1155  dbvt.optimizeIncremental(cfgBenchmark11_Iterations);
1156  }
1157  const int time=(int)wallclock.getTimeMilliseconds();
1158  const int op=cfgBenchmark11_Passes*cfgBenchmark11_Iterations;
1159  printf("%u ms (%i%%),(%u o/s)\r\n",time,(time-cfgBenchmark11_Reference)*100/time,op/time*1000);
1160  }
1161  if(cfgBenchmark12_Enable)
1162  {// Benchmark 12
1163  srand(380843);
1166  volumes.resize(cfgLeaves);
1167  results.resize(cfgLeaves);
1168  for(int i=0;i<cfgLeaves;++i)
1169  {
1170  volumes[i]=btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale);
1171  }
1172  printf("[12] btDbvtVolume notequal: ");
1173  wallclock.reset();
1174  for(int i=0;i<cfgBenchmark12_Iterations;++i)
1175  {
1176  for(int j=0;j<cfgLeaves;++j)
1177  {
1178  for(int k=0;k<cfgLeaves;++k)
1179  {
1180  results[k]=NotEqual(volumes[j],volumes[k]);
1181  }
1182  }
1183  }
1184  const int time=(int)wallclock.getTimeMilliseconds();
1185  printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark12_Reference)*100/time);
1186  }
1187  if(cfgBenchmark13_Enable)
1188  {// Benchmark 13
1189  srand(380843);
1190  btDbvt dbvt;
1192  btDbvtBenchmark::NilPolicy policy;
1193  vectors.resize(cfgBenchmark13_Iterations);
1194  for(int i=0;i<vectors.size();++i)
1195  {
1196  vectors[i]=(btDbvtBenchmark::RandVector3()*2-btVector3(1,1,1)).normalized();
1197  }
1198  btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1199  dbvt.optimizeTopDown();
1200  printf("[13] culling(OCL+fullsort): ");
1201  wallclock.reset();
1202  for(int i=0;i<cfgBenchmark13_Iterations;++i)
1203  {
1204  static const btScalar offset=0;
1205  policy.m_depth=-SIMD_INFINITY;
1206  dbvt.collideOCL(dbvt.m_root,&vectors[i],&offset,vectors[i],1,policy);
1207  }
1208  const int time=(int)wallclock.getTimeMilliseconds();
1209  const int t=cfgBenchmark13_Iterations;
1210  printf("%u ms (%i%%),(%u t/s)\r\n",time,(time-cfgBenchmark13_Reference)*100/time,(t*1000)/time);
1211  }
1212  if(cfgBenchmark14_Enable)
1213  {// Benchmark 14
1214  srand(380843);
1215  btDbvt dbvt;
1217  btDbvtBenchmark::P14 policy;
1218  vectors.resize(cfgBenchmark14_Iterations);
1219  for(int i=0;i<vectors.size();++i)
1220  {
1221  vectors[i]=(btDbvtBenchmark::RandVector3()*2-btVector3(1,1,1)).normalized();
1222  }
1223  btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1224  dbvt.optimizeTopDown();
1225  policy.m_nodes.reserve(cfgLeaves);
1226  printf("[14] culling(OCL+qsort): ");
1227  wallclock.reset();
1228  for(int i=0;i<cfgBenchmark14_Iterations;++i)
1229  {
1230  static const btScalar offset=0;
1231  policy.m_nodes.resize(0);
1232  dbvt.collideOCL(dbvt.m_root,&vectors[i],&offset,vectors[i],1,policy,false);
1233  policy.m_nodes.quickSort(btDbvtBenchmark::P14::sortfnc);
1234  }
1235  const int time=(int)wallclock.getTimeMilliseconds();
1236  const int t=cfgBenchmark14_Iterations;
1237  printf("%u ms (%i%%),(%u t/s)\r\n",time,(time-cfgBenchmark14_Reference)*100/time,(t*1000)/time);
1238  }
1239  if(cfgBenchmark15_Enable)
1240  {// Benchmark 15
1241  srand(380843);
1242  btDbvt dbvt;
1244  btDbvtBenchmark::P15 policy;
1245  vectors.resize(cfgBenchmark15_Iterations);
1246  for(int i=0;i<vectors.size();++i)
1247  {
1248  vectors[i]=(btDbvtBenchmark::RandVector3()*2-btVector3(1,1,1)).normalized();
1249  }
1250  btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1251  dbvt.optimizeTopDown();
1252  policy.m_nodes.reserve(cfgLeaves);
1253  printf("[15] culling(KDOP+qsort): ");
1254  wallclock.reset();
1255  for(int i=0;i<cfgBenchmark15_Iterations;++i)
1256  {
1257  static const btScalar offset=0;
1258  policy.m_nodes.resize(0);
1259  policy.m_axis=vectors[i];
1260  dbvt.collideKDOP(dbvt.m_root,&vectors[i],&offset,1,policy);
1261  policy.m_nodes.quickSort(btDbvtBenchmark::P15::sortfnc);
1262  }
1263  const int time=(int)wallclock.getTimeMilliseconds();
1264  const int t=cfgBenchmark15_Iterations;
1265  printf("%u ms (%i%%),(%u t/s)\r\n",time,(time-cfgBenchmark15_Reference)*100/time,(t*1000)/time);
1266  }
1267  if(cfgBenchmark16_Enable)
1268  {// Benchmark 16
1269  srand(380843);
1270  btDbvt dbvt;
1272  btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1273  dbvt.optimizeTopDown();
1274  batch.reserve(cfgBenchmark16_BatchCount);
1275  printf("[16] insert/remove batch(%u): ",cfgBenchmark16_BatchCount);
1276  wallclock.reset();
1277  for(int i=0;i<cfgBenchmark16_Passes;++i)
1278  {
1279  for(int j=0;j<cfgBenchmark16_BatchCount;++j)
1280  {
1281  batch.push_back(dbvt.insert(btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale),0));
1282  }
1283  for(int j=0;j<cfgBenchmark16_BatchCount;++j)
1284  {
1285  dbvt.remove(batch[j]);
1286  }
1287  batch.resize(0);
1288  }
1289  const int time=(int)wallclock.getTimeMilliseconds();
1290  const int ir=cfgBenchmark16_Passes*cfgBenchmark16_BatchCount;
1291  printf("%u ms (%i%%),(%u bir/s)\r\n",time,(time-cfgBenchmark16_Reference)*100/time,int(ir*1000.0/time));
1292  }
1293  if(cfgBenchmark17_Enable)
1294  {// Benchmark 17
1295  srand(380843);
1297  btAlignedObjectArray<int> results;
1298  btAlignedObjectArray<int> indices;
1299  volumes.resize(cfgLeaves);
1300  results.resize(cfgLeaves);
1301  indices.resize(cfgLeaves);
1302  for(int i=0;i<cfgLeaves;++i)
1303  {
1304  indices[i]=i;
1305  volumes[i]=btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale);
1306  }
1307  for(int i=0;i<cfgLeaves;++i)
1308  {
1309  btSwap(indices[i],indices[rand()%cfgLeaves]);
1310  }
1311  printf("[17] btDbvtVolume select: ");
1312  wallclock.reset();
1313  for(int i=0;i<cfgBenchmark17_Iterations;++i)
1314  {
1315  for(int j=0;j<cfgLeaves;++j)
1316  {
1317  for(int k=0;k<cfgLeaves;++k)
1318  {
1319  const int idx=indices[k];
1320  results[idx]=Select(volumes[idx],volumes[j],volumes[k]);
1321  }
1322  }
1323  }
1324  const int time=(int)wallclock.getTimeMilliseconds();
1325  printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark17_Reference)*100/time);
1326  }
1327  printf("\r\n\r\n");
1328 }
1329 #endif
void setOrigin(const btVector3 &origin)
Set the translational element.
Definition: btTransform.h:150
static DBVT_PREFIX void collideKDOP(const btDbvtNode *root, const btVector3 *normals, const btScalar *offsets, int count, DBVT_IPOLICY)
Definition: btDbvt.h:1134
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()
Definition: btDbvt.h:295
~btDbvt()
Definition: btDbvt.cpp:453
DBVT_INLINE bool isleaf() const
Definition: btDbvt.h:182
static DBVT_PREFIX void collideOCL(const btDbvtNode *root, const btVector3 *normals, const btScalar *offsets, const btVector3 &sortaxis, int count, DBVT_IPOLICY, bool fullsort=true)
Definition: btDbvt.h:1189
The btAlignedObjectArray template class uses a subset of the stl::vector interface for its methods It...
static void fetchleaves(btDbvt *pdbvt, btDbvtNode *root, tNodeArray &leaves, int depth=-1)
Definition: btDbvt.cpp:214
void * data
Definition: btDbvt.h:187
static bool leftOfAxis(const btDbvtNode *node, const btVector3 &org, const btVector3 &axis)
Definition: btDbvt.cpp:232
static void getmaxdepth(const btDbvtNode *node, int depth, int &maxdepth)
Definition: btDbvt.cpp:60
static void recursedeletenode(btDbvt *pdbvt, btDbvtNode *node)
Definition: btDbvt.cpp:78
static int split(btDbvtNode **leaves, int count, const btVector3 &org, const btVector3 &axis)
Definition: btDbvt.cpp:243
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
Definition: btDbvt.cpp:52
#define btAssert(x)
Definition: btScalar.h:131
The btDbvt class implements a fast dynamic bounding volume tree based on axis aligned bounding boxes ...
Definition: btDbvt.h:198
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
btDbvtNode * m_root
Definition: btDbvt.h:262
virtual void WriteNode(const btDbvtNode *, int index, int parent, int child0, int child1)=0
void reset()
Resets the initial reference time.
static DBVT_PREFIX void rayTest(const btDbvtNode *root, const btVector3 &rayFrom, const btVector3 &rayTo, DBVT_IPOLICY)
rayTest is a re-entrant ray test, and can be called in parallel as long as the btAlignedAlloc is thre...
Definition: btDbvt.h:1060
static btDbvtNode * topdown(btDbvt *pdbvt, btDbvtNode **leaves, int count, int bu_treshold)
Definition: btDbvt.cpp:337
DBVT_INLINE int Select(const btDbvtAabbMm &o, const btDbvtAabbMm &a, const btDbvtAabbMm &b)
Definition: btDbvt.h:588
DBVT_INLINE bool isinternal() const
Definition: btDbvt.h:183
tConstNodeArray nodes
Definition: btDbvt.cpp:26
void Process(const btDbvtNode *n)
Definition: btDbvt.cpp:27
const btScalar & x() const
Return the x value.
Definition: btVector3.h:587
void update(btDbvtNode *leaf, int lookahead=-1)
Definition: btDbvt.cpp:526
#define SIMD_PI
Definition: btScalar.h:504
const btDbvtNode * node
Definition: btDbvt.h:224
btAlignedObjectArray< const btDbvtNode * > tConstNodeArray
Definition: btDbvt.cpp:21
#define SIMD_INFINITY
Definition: btScalar.h:522
static int countLeaves(const btDbvtNode *node)
Definition: btDbvt.cpp:661
void clear()
Definition: btDbvt.cpp:459
int size() const
return the number of elements in the array
void optimizeIncremental(int passes)
Definition: btDbvt.cpp:497
static DBVT_INLINE btDbvtNode * createnode(btDbvt *pdbvt, btDbvtNode *parent, void *data)
Definition: btDbvt.cpp:91
static btDbvtAabbMm FromCE(const btVector3 &c, const btVector3 &e)
Definition: btDbvt.h:411
static DBVT_INLINE btDbvtVolume merge(const btDbvtVolume &a, const btDbvtVolume &b)
Definition: btDbvt.cpp:37
btDbvtNode * childs[2]
Definition: btDbvt.h:186
void btSwap(T &a, T &b)
Definition: btScalar.h:621
static int maxdepth(const btDbvtNode *node)
Definition: btDbvt.cpp:653
static btDbvtAabbMm FromMM(const btVector3 &mi, const btVector3 &mx)
Definition: btDbvt.h:425
DBVT_INLINE btVector3 Lengths() const
Definition: btDbvt.h:134
static void insertleaf(btDbvt *pdbvt, btDbvtNode *root, btDbvtNode *leaf)
Definition: btDbvt.cpp:130
#define btAlignedFree(ptr)
void setRotation(const btQuaternion &q)
Set the rotational element by btQuaternion.
Definition: btTransform.h:165
DBVT_INLINE btVector3 Center() const
Definition: btDbvt.h:133
DBVT_INLINE void Expand(const btVector3 &e)
Definition: btDbvt.h:459
void optimizeTopDown(int bu_treshold=128)
Definition: btDbvt.cpp:485
const btScalar & y() const
Return the y value.
Definition: btVector3.h:589
btVector3 can be used to represent 3D points and vectors.
Definition: btVector3.h:83
#define ATTRIBUTE_ALIGNED16(a)
Definition: btScalar.h:82
DBVT_INLINE const btVector3 & Maxs() const
Definition: btDbvt.h:137
unsigned long long int getTimeMilliseconds()
Returns the time in ms since the last call to reset or since the btClock was created.
The btTransform class supports rigid transforms with only translation and rotation and no scaling/she...
Definition: btTransform.h:34
void write(IWriter *iwriter) const
Definition: btDbvt.cpp:597
virtual void Prepare(const btDbvtNode *root, int numnodes)=0
static void clear(T &value)
btDbvt()
Definition: btDbvt.cpp:443
void resize(int newsize, const T &fillData=T())
btDbvtVolume volume
Definition: btDbvt.h:180
int findLinearSearch(const T &key) const
virtual void WriteLeaf(const btDbvtNode *, int index, int parent)=0
static btDbvtNode * removeleaf(btDbvt *pdbvt, btDbvtNode *leaf)
Definition: btDbvt.cpp:174
const T & btMax(const T &a, const T &b)
Definition: btMinMax.h:29
#define DBVT_INLINE
Definition: btDbvt.h:55
static void extractLeaves(const btDbvtNode *node, btAlignedObjectArray< const btDbvtNode * > &leaves)
Definition: btDbvt.cpp:670
DBVT_INLINE bool Intersect(const btDbvtAabbMm &a, const btDbvtAabbMm &b)
Definition: btDbvt.h:534
#define btAlignedAlloc(size, alignment)
static btDbvtVolume bounds(btDbvtNode **leaves, int count)
Definition: btDbvt.cpp:284
static DBVT_INLINE int indexof(const btDbvtNode *node)
Definition: btDbvt.cpp:31
btScalar dot(const btQuaternion &q1, const btQuaternion &q2)
Calculate the dot product between two quaternions.
Definition: btQuaternion.h:898
btAlignedObjectArray< btDbvtNode * > tNodeArray
btDbvt implementation by Nathanael Presson
Definition: btDbvt.cpp:20
DBVT_PREFIX void collideTT(const btDbvtNode *root0, const btDbvtNode *root1, DBVT_IPOLICY)
Definition: btDbvt.h:738
The btQuaternion implements quaternion to perform linear algebra rotations in combination with btMatr...
Definition: btQuaternion.h:55
btScalar btDot(const btVector3 &v1, const btVector3 &v2)
Return the dot product between two vectors.
Definition: btVector3.h:903
static DBVT_INLINE void deletenode(btDbvt *pdbvt, btDbvtNode *node)
Definition: btDbvt.cpp:70
void optimizeBottomUp()
Definition: btDbvt.cpp:472
DBVT_INLINE bool Contain(const btDbvtAabbMm &a) const
Definition: btDbvt.h:473
DBVT_INLINE const btVector3 & Mins() const
Definition: btDbvt.h:136
DBVT_INLINE void SignedExpand(const btVector3 &e)
Definition: btDbvt.h:465
static DBVT_INLINE btDbvtNode * sort(btDbvtNode *n, btDbvtNode *&r)
Definition: btDbvt.cpp:403
void clone(btDbvt &dest, IClone *iclone=0) const
Definition: btDbvt.cpp:622
void remove(btDbvtNode *leaf)
Definition: btDbvt.cpp:589
static void bottomup(btDbvt *pdbvt, btDbvtNode **leaves, int count)
Definition: btDbvt.cpp:303
float btScalar
The btScalar type abstracts floating point numbers, to easily switch between double and single floati...
Definition: btScalar.h:292
btDbvtNode * m_free
Definition: btDbvt.h:263
virtual void CloneLeaf(btDbvtNode *)
Definition: btDbvt.h:252
btDbvtNode * parent
Definition: btDbvt.h:225
DBVT_INLINE bool NotEqual(const btDbvtAabbMm &a, const btDbvtAabbMm &b)
Definition: btDbvt.h:690
btDbvtNode * parent
Definition: btDbvt.h:181
btScalar btFabs(btScalar x)
Definition: btScalar.h:475
const btScalar & z() const
Return the z value.
Definition: btVector3.h:591