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