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