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