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