dali-physics/third-party/bullet3/src/BulletCollision/BroadphaseCollision/btDbvt.cpp

   1 /*
   2 Bullet Continuous Collision Detection and Physics Library
   3 Copyright (c) 2003-2006 Erwin Coumans  https://bulletphysics.org
   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 */
  15 ///btDbvt implementation by Nathanael Presson
  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 #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
  52 static DBVT_INLINE btScalar size(const btDbvtVolume& a)
  53 {
  54         const btVector3 edges = a.Lengths();
  55         return (edges.x() * edges.y() * edges.z() +
  56                         edges.x() + edges.y() + edges.z());
  57 }
  58
  59 //
  60 static void getmaxdepth(const btDbvtNode* node, int depth, int& maxdepth)
  61 {
  62         if (node->isinternal())
  63         {
  64                 getmaxdepth(node->childs[0], depth + 1, maxdepth);
  65                 getmaxdepth(node->childs[1], depth + 1, maxdepth);
  66         }
  67         else
  68                 maxdepth = btMax(maxdepth, depth);
  69 }
  70
  71 //
  72 static DBVT_INLINE void deletenode(btDbvt* pdbvt,
  73                                                                    btDbvtNode* node)
  74 {
  75         btAlignedFree(pdbvt->m_free);
  76         pdbvt->m_free = node;
  77 }
  78
  79 //
  80 static void recursedeletenode(btDbvt* pdbvt,
  81                                                           btDbvtNode* node)
  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 //
  94 static DBVT_INLINE btDbvtNode* createnode(btDbvt* pdbvt,
  95                                                                                   btDbvtNode* parent,
  96                                                                                   void* data)
  97 {
  98         btDbvtNode* node;
  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 //
 115 static DBVT_INLINE btDbvtNode* createnode(btDbvt* pdbvt,
 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 //
 126 static DBVT_INLINE btDbvtNode* createnode(btDbvt* pdbvt,
 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 //
 299 static btDbvtVolume bounds(btDbvtNode** leaves,
 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 //
 418 static DBVT_INLINE btDbvtNode* sort(btDbvtNode* n, btDbvtNode*& r)
 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 //
 461 btDbvt::btDbvt()
 462 {
 463         m_root = 0;
 464         m_free = 0;
 465         m_lkhd = -1;
 466         m_leaves = 0;
 467         m_opath = 0;
 468 }
 469
 470 //
 471 btDbvt::~btDbvt()
 472 {
 473         clear();
 474 }
 475
 476 //
 477 void btDbvt::clear()
 478 {
 479         if (m_root)
 480                 recursedeletenode(this, m_root);
 481         btAlignedFree(m_free);
 482         m_free = 0;
 483         m_lkhd = -1;
 484         m_stkStack.clear();
 485         m_opath = 0;
 486 }
 487
 488 //
 489 void btDbvt::optimizeBottomUp()
 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 //
 514 void btDbvt::optimizeIncremental(int passes)
 515 {
 516         if (passes < 0) passes = m_leaves;
 517         if (m_root && (passes > 0))
 518         {
 519                 do
 520                 {
 521                         btDbvtNode* node = m_root;
 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 //
 535 btDbvtNode* btDbvt::insert(const btDbvtVolume& volume, void* data)
 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 //
 563 void btDbvt::update(btDbvtNode* leaf, btDbvtVolume& volume)
 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 //
 611 void btDbvt::remove(btDbvtNode* leaf)
 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         {
 649                 btAlignedObjectArray<sStkCLN> stack;
 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 //
 676 int btDbvt::maxdepth(const btDbvtNode* node)
 677 {
 678         int depth = 0;
 679         if (node) getmaxdepth(node, 1, depth);
 680         return (depth);
 681 }
 682
 683 //
 684 int btDbvt::countLeaves(const btDbvtNode* node)
 685 {
 686         if (node->isinternal())
 687                 return (countLeaves(node->childs[0]) + countLeaves(node->childs[1]));
 688         else
 689                 return (1);
 690 }
 691
 692 //
 693 void btDbvt::extractLeaves(const btDbvtNode* node, btAlignedObjectArray<const btDbvtNode*>& leaves)
 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;
 767                 btScalar m_depth;
 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                 }
 789                 btAlignedObjectArray<Node> m_nodes;
 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                 }
 810                 btAlignedObjectArray<Node> m_nodes;
 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);
 943                 btAlignedObjectArray<btDbvtVolume> volumes;
 944                 btAlignedObjectArray<bool> results;
 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);
 969                 btAlignedObjectArray<btDbvtVolume> volumes;
 970                 btAlignedObjectArray<btDbvtVolume> results;
 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];
1030                 btAlignedObjectArray<btTransform> transforms;
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;
1054                 btAlignedObjectArray<btTransform> transforms;
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;
1076                 btAlignedObjectArray<btVector3> rayorg;
1077                 btAlignedObjectArray<btVector3> raydir;
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;
1124                 btAlignedObjectArray<const btDbvtNode*> leaves;
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;
1146                 btAlignedObjectArray<const btDbvtNode*> leaves;
1147                 btAlignedObjectArray<btVector3> vectors;
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);
1192                 btAlignedObjectArray<btDbvtVolume> volumes;
1193                 btAlignedObjectArray<bool> results;
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;
1219                 btAlignedObjectArray<btVector3> vectors;
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;
1244                 btAlignedObjectArray<btVector3> vectors;
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;
1271                 btAlignedObjectArray<btVector3> vectors;
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;
1299                 btAlignedObjectArray<btDbvtNode*> batch;
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);
1324                 btAlignedObjectArray<btDbvtVolume> volumes;
1325                 btAlignedObjectArray<int> results;
1326                 btAlignedObjectArray<int> indices;
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