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