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 //
20 typedef btAlignedObjectArray<btDbvtNode*> tNodeArray;
21 typedef btAlignedObjectArray<const btDbvtNode*> tConstNodeArray;
22 
23 //
24 struct btDbvtNodeEnumerator : btDbvt::ICollide
25 {
26  tConstNodeArray nodes;
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 //
37 static DBVT_INLINE btDbvtVolume merge( const btDbvtVolume& a,
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
52 static DBVT_INLINE btScalar size(const btDbvtVolume& a)
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 //
91 static DBVT_INLINE btDbvtNode* createnode( btDbvt* pdbvt,
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 //
107 static DBVT_INLINE btDbvtNode* createnode( btDbvt* pdbvt,
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 //
118 static DBVT_INLINE btDbvtNode* createnode( btDbvt* pdbvt,
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 //
403 static DBVT_INLINE btDbvtNode* sort(btDbvtNode* n,btDbvtNode*& r)
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 //
443 btDbvt::btDbvt()
444 {
445  m_root = 0;
446  m_free = 0;
447  m_lkhd = -1;
448  m_leaves = 0;
449  m_opath = 0;
450 }
451 
452 //
453 btDbvt::~btDbvt()
454 {
455  clear();
456 }
457 
458 //
459 void btDbvt::clear()
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 //
472 void btDbvt::optimizeBottomUp()
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 //
497 void btDbvt::optimizeIncremental(int passes)
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 //
543 void btDbvt::update(btDbvtNode* leaf,btDbvtVolume& volume)
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 //
589 void btDbvt::remove(btDbvtNode* leaf)
590 {
591  removeleaf(this,leaf);
592  deletenode(this,leaf);
593  --m_leaves;
594 }
595 
596 //
597 void btDbvt::write(IWriter* iwriter) const
598 {
599  btDbvtNodeEnumerator nodes;
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  {
627  btAlignedObjectArray<sStkCLN> stack;
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 //
661 int btDbvt::countLeaves(const btDbvtNode* node)
662 {
663  if(node->isinternal())
664  return(countLeaves(node->childs[0])+countLeaves(node->childs[1]));
665  else
666  return(1);
667 }
668 
669 //
670 void btDbvt::extractLeaves(const btDbvtNode* node,btAlignedObjectArray<const btDbvtNode*>& leaves)
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  }
761  btAlignedObjectArray<Node> m_nodes;
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  }
782  btAlignedObjectArray<Node> m_nodes;
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);
915  btAlignedObjectArray<btDbvtVolume> volumes;
916  btAlignedObjectArray<bool> results;
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);
941  btAlignedObjectArray<btDbvtVolume> volumes;
942  btAlignedObjectArray<btDbvtVolume> results;
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];
1002  btAlignedObjectArray<btTransform> transforms;
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;
1026  btAlignedObjectArray<btTransform> transforms;
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;
1048  btAlignedObjectArray<btVector3> rayorg;
1049  btAlignedObjectArray<btVector3> raydir;
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;
1096  btAlignedObjectArray<const btDbvtNode*> leaves;
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;
1118  btAlignedObjectArray<const btDbvtNode*> leaves;
1119  btAlignedObjectArray<btVector3> vectors;
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]);
1137  btDbvtVolume v=btDbvtVolume::FromMM(l->volume.Mins()+d,l->volume.Maxs()+d);
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);
1164  btAlignedObjectArray<btDbvtVolume> volumes;
1165  btAlignedObjectArray<bool> results;
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;
1191  btAlignedObjectArray<btVector3> vectors;
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;
1216  btAlignedObjectArray<btVector3> vectors;
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;
1243  btAlignedObjectArray<btVector3> vectors;
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;
1271  btAlignedObjectArray<btDbvtNode*> batch;
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);
1296  btAlignedObjectArray<btDbvtVolume> volumes;
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
btDbvt::optimizeIncremental
void optimizeIncremental(int passes)
Definition: btDbvt.cpp:497
btDbvt::optimizeTopDown
void optimizeTopDown(int bu_treshold=128)
Definition: btDbvt.cpp:485
btDbvt::clear
void clear()
Definition: btDbvt.cpp:459
btDbvt::collideKDOP
static DBVT_PREFIX void collideKDOP(const btDbvtNode *root, const btVector3 *normals, const btScalar *offsets, int count, DBVT_IPOLICY)
Definition: btDbvt.h:1134
btDbvt::IClone::CloneLeaf
virtual void CloneLeaf(btDbvtNode *)
Definition: btDbvt.h:252
DBVT_INLINE
#define DBVT_INLINE
Definition: btDbvt.h:55
btDbvt::sStkCLN::node
const btDbvtNode * node
Definition: btDbvt.h:224
btDbvt::sStkCLN
Definition: btDbvt.h:222
btDbvt::collideTT
DBVT_PREFIX void collideTT(const btDbvtNode *root0, const btDbvtNode *root1, DBVT_IPOLICY)
Definition: btDbvt.h:738
btDbvtAabbMm::Expand
DBVT_INLINE void Expand(const btVector3 &e)
Definition: btDbvt.h:459
btDbvtAabbMm::Contain
DBVT_INLINE bool Contain(const btDbvtAabbMm &a) const
Definition: btDbvt.h:473
btAlignedFree
#define btAlignedFree(ptr)
Definition: btAlignedAllocator.h:48
dot
btScalar dot(const btQuaternion &q1, const btQuaternion &q2)
Calculate the dot product between two quaternions.
Definition: btQuaternion.h:878
recursedeletenode
static void recursedeletenode(btDbvt *pdbvt, btDbvtNode *node)
Definition: btDbvt.cpp:78
btQuaternion
The btQuaternion implements quaternion to perform linear algebra rotations in combination with btMatr...
Definition: btQuaternion.h:55
fetchleaves
static void fetchleaves(btDbvt *pdbvt, btDbvtNode *root, tNodeArray &leaves, int depth=-1)
Definition: btDbvt.cpp:214
btScalar
float btScalar
The btScalar type abstracts floating point numbers, to easily switch between double and single floati...
Definition: btScalar.h:292
btDbvtAabbMm::Lengths
DBVT_INLINE btVector3 Lengths() const
Definition: btDbvt.h:134
indexof
static DBVT_INLINE int indexof(const btDbvtNode *node)
Definition: btDbvt.cpp:31
btDbvtNodeEnumerator::nodes
tConstNodeArray nodes
Definition: btDbvt.cpp:26
btDbvt::m_free
btDbvtNode * m_free
Definition: btDbvt.h:263
insertleaf
static void insertleaf(btDbvt *pdbvt, btDbvtNode *root, btDbvtNode *leaf)
Definition: btDbvt.cpp:130
btAlignedObjectArray::findLinearSearch
int findLinearSearch(const T &key) const
Definition: btAlignedObjectArray.h:463
btDbvtAabbMm::Maxs
const DBVT_INLINE btVector3 & Maxs() const
Definition: btDbvt.h:137
getmaxdepth
static void getmaxdepth(const btDbvtNode *node, int depth, int &maxdepth)
Definition: btDbvt.cpp:60
btDbvt::countLeaves
static int countLeaves(const btDbvtNode *node)
Definition: btDbvt.cpp:661
btDbvt::extractLeaves
static void extractLeaves(const btDbvtNode *node, btAlignedObjectArray< const btDbvtNode * > &leaves)
Definition: btDbvt.cpp:670
SIMD_PI
#define SIMD_PI
Definition: btScalar.h:504
btDbvt::sStkCLN::parent
btDbvtNode * parent
Definition: btDbvt.h:225
btAlignedAlloc
#define btAlignedAlloc(size, alignment)
Definition: btAlignedAllocator.h:47
merge
static DBVT_INLINE btDbvtVolume merge(const btDbvtVolume &a, const btDbvtVolume &b)
Definition: btDbvt.cpp:37
btDbvt::optimizeBottomUp
void optimizeBottomUp()
Definition: btDbvt.cpp:472
deletenode
static DBVT_INLINE void deletenode(btDbvt *pdbvt, btDbvtNode *node)
Definition: btDbvt.cpp:70
btDbvt::~btDbvt
~btDbvt()
Definition: btDbvt.cpp:453
btDbvt::IWriter
Definition: btDbvt.h:241
btDbvt::rayTest
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
btDbvtNode::data
void * data
Definition: btDbvt.h:187
btMax
const T & btMax(const T &a, const T &b)
Definition: btMinMax.h:29
btDbvt::collideOCL
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
btVector3::y
const btScalar & y() const
Return the y value.
Definition: btVector3.h:589
btDbvt::update
void update(btDbvtNode *leaf, int lookahead=-1)
Definition: btDbvt.cpp:526
btAssert
#define btAssert(x)
Definition: btScalar.h:131
btDbvt::m_leaves
int m_leaves
Definition: btDbvt.h:265
btClock::getTimeMilliseconds
unsigned long long int getTimeMilliseconds()
Returns the time in ms since the last call to reset or since the btClock was created.
Definition: btQuickprof.cpp:143
btFabs
btScalar btFabs(btScalar x)
Definition: btScalar.h:475
removeleaf
static btDbvtNode * removeleaf(btDbvt *pdbvt, btDbvtNode *leaf)
Definition: btDbvt.cpp:174
sort
static DBVT_INLINE btDbvtNode * sort(btDbvtNode *n, btDbvtNode *&r)
Definition: btDbvt.cpp:403
btDbvt
The btDbvt class implements a fast dynamic bounding volume tree based on axis aligned bounding boxes ...
Definition: btDbvt.h:198
btDbvt::maxdepth
static int maxdepth(const btDbvtNode *node)
Definition: btDbvt.cpp:653
tNodeArray
btAlignedObjectArray< btDbvtNode * > tNodeArray
btDbvt implementation by Nathanael Presson
Definition: btDbvt.cpp:20
bounds
static btDbvtVolume bounds(btDbvtNode **leaves, int count)
Definition: btDbvt.cpp:284
btDbvt::clone
void clone(btDbvt &dest, IClone *iclone=0) const
Definition: btDbvt.cpp:622
leftOfAxis
static bool leftOfAxis(const btDbvtNode *node, const btVector3 &org, const btVector3 &axis)
Definition: btDbvt.cpp:232
btAlignedObjectArray::resize
void resize(int newsize, const T &fillData=T())
Definition: btAlignedObjectArray.h:218
btTransform::setRotation
void setRotation(const btQuaternion &q)
Set the rotational element by btQuaternion.
Definition: btTransform.h:165
btDbvtNode::childs
btDbvtNode * childs[2]
Definition: btDbvt.h:186
btDbvtAabbMm::Mins
const DBVT_INLINE btVector3 & Mins() const
Definition: btDbvt.h:136
btDbvt::m_opath
unsigned m_opath
Definition: btDbvt.h:266
btAlignedObjectArray::pop_back
void pop_back()
Definition: btAlignedObjectArray.h:199
topdown
static btDbvtNode * topdown(btDbvt *pdbvt, btDbvtNode **leaves, int count, int bu_treshold)
Definition: btDbvt.cpp:337
btTransform
The btTransform class supports rigid transforms with only translation and rotation and no scaling/she...
Definition: btTransform.h:34
btDbvt::IWriter::WriteLeaf
virtual void WriteLeaf(const btDbvtNode *, int index, int parent)=0
btDbvt::btDbvt
btDbvt()
Definition: btDbvt.cpp:443
Intersect
DBVT_INLINE bool Intersect(const btDbvtAabbMm &a, const btDbvtAabbMm &b)
Definition: btDbvt.h:534
btDbvtNode::volume
btDbvtVolume volume
Definition: btDbvt.h:180
SIMD_INFINITY
#define SIMD_INFINITY
Definition: btScalar.h:522
split
static int split(btDbvtNode **leaves, int count, const btVector3 &org, const btVector3 &axis)
Definition: btDbvt.cpp:243
btVector3
btVector3 can be used to represent 3D points and vectors.
Definition: btVector3.h:83
btDbvt::IWriter::WriteNode
virtual void WriteNode(const btDbvtNode *, int index, int parent, int child0, int child1)=0
btDbvtAabbMm::FromMM
static btDbvtAabbMm FromMM(const btVector3 &mi, const btVector3 &mx)
Definition: btDbvt.h:425
NotEqual
DBVT_INLINE bool NotEqual(const btDbvtAabbMm &a, const btDbvtAabbMm &b)
Definition: btDbvt.h:690
btDbvt::m_stkStack
btAlignedObjectArray< sStkNN > m_stkStack
Definition: btDbvt.h:269
btDbvt::IWriter::Prepare
virtual void Prepare(const btDbvtNode *root, int numnodes)=0
btDbvtNodeEnumerator
Definition: btDbvt.cpp:24
ATTRIBUTE_ALIGNED16
#define ATTRIBUTE_ALIGNED16(a)
Definition: btScalar.h:82
btAlignedObjectArray
The btAlignedObjectArray template class uses a subset of the stl::vector interface for its methods It...
Definition: btAlignedObjectArray.h:53
btSwap
void btSwap(T &a, T &b)
Definition: btScalar.h:621
btDbvt::m_root
btDbvtNode * m_root
Definition: btDbvt.h:262
Merge
DBVT_INLINE void Merge(const btDbvtAabbMm &a, const btDbvtAabbMm &b, btDbvtAabbMm &r)
Definition: btDbvt.h:667
Select
DBVT_INLINE int Select(const btDbvtAabbMm &o, const btDbvtAabbMm &a, const btDbvtAabbMm &b)
Definition: btDbvt.h:588
btClock::reset
void reset()
Resets the initial reference time.
Definition: btQuickprof.cpp:119
btDbvtNodeEnumerator::Process
void Process(const btDbvtNode *n)
Definition: btDbvt.cpp:27
btDbvt::benchmark
static void benchmark()
Definition: btDbvt.h:295
btDbvtNode::isinternal
DBVT_INLINE bool isinternal() const
Definition: btDbvt.h:183
btDot
btScalar btDot(const btVector3 &v1, const btVector3 &v2)
Return the dot product between two vectors.
Definition: btVector3.h:901
btVector3::x
const btScalar & x() const
Return the x value.
Definition: btVector3.h:587
btDbvt::IClone
Definition: btDbvt.h:249
btClock
The btClock is a portable basic clock that measures accurate time in seconds, use for profiling.
Definition: btQuickprof.h:24
btAlignedObjectArray::reserve
void reserve(int _Count)
Definition: btAlignedObjectArray.h:298
btDbvtAabbMm::SignedExpand
DBVT_INLINE void SignedExpand(const btVector3 &e)
Definition: btDbvt.h:465
btDbvtNode::isleaf
DBVT_INLINE bool isleaf() const
Definition: btDbvt.h:182
btDbvtAabbMm
Definition: btDbvt.h:131
btDbvt::insert
btDbvtNode * insert(const btDbvtVolume &box, void *data)
Definition: btDbvt.cpp:517
btDbvt::enumNodes
static DBVT_PREFIX void enumNodes(const btDbvtNode *root, DBVT_IPOLICY)
Definition: btDbvt.h:707
btDbvt::ICollide
Definition: btDbvt.h:231
btAlignedObjectArray::push_back
void push_back(const T &_Val)
Definition: btAlignedObjectArray.h:274
tConstNodeArray
btAlignedObjectArray< const btDbvtNode * > tConstNodeArray
Definition: btDbvt.cpp:21
createnode
static DBVT_INLINE btDbvtNode * createnode(btDbvt *pdbvt, btDbvtNode *parent, void *data)
Definition: btDbvt.cpp:91
btDbvt::remove
void remove(btDbvtNode *leaf)
Definition: btDbvt.cpp:589
btDbvtNode
Definition: btDbvt.h:178
btDbvtAabbMm::Center
DBVT_INLINE btVector3 Center() const
Definition: btDbvt.h:133
btTransform::setOrigin
void setOrigin(const btVector3 &origin)
Set the translational element.
Definition: btTransform.h:150
btDbvt::write
void write(IWriter *iwriter) const
Definition: btDbvt.cpp:597
btDbvtNode::parent
btDbvtNode * parent
Definition: btDbvt.h:181
size
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
Definition: btDbvt.cpp:52
btDbvtAabbMm::FromCE
static btDbvtAabbMm FromCE(const btVector3 &c, const btVector3 &e)
Definition: btDbvt.h:411
bottomup
static void bottomup(btDbvt *pdbvt, btDbvtNode **leaves, int count)
Definition: btDbvt.cpp:303
btDbvt.h
btVector3::z
const btScalar & z() const
Return the z value.
Definition: btVector3.h:591
btDbvt::m_lkhd
int m_lkhd
Definition: btDbvt.h:264
btAlignedObjectArray::size
int size() const
return the number of elements in the array
Definition: btAlignedObjectArray.h:155
Generated by   doxygen 1.8.17