/////////////////////////////////////////////////////////////// main SAH sort routine
| 542 | //////////////////////////////////////////////////////////////////// |
| 543 | // main SAH sort routine |
| 544 | void sort4(PxU32* permute, PxU32 clusterSize, |
| 545 | Array<RTreeNodeNQ>& resultTree, PxU32& maxLevels, PxU32 level = 0, RTreeNodeNQ* parentNode = NULL) |
| 546 | { |
| 547 | PX_UNUSED(parentNode); |
| 548 | |
| 549 | if(level == 0) |
| 550 | maxLevels = 1; |
| 551 | else |
| 552 | maxLevels = PxMax(maxLevels, level+1); |
| 553 | |
| 554 | PxU32 splitPos[RTREE_N]; |
| 555 | for(PxU32 j = 0; j < RTREE_N; j++) |
| 556 | splitPos[j] = j+1; |
| 557 | |
| 558 | if(clusterSize >= RTREE_N) |
| 559 | { |
| 560 | // split into RTREE_N number of regions via RTREE_N-1 subsequent splits |
| 561 | // each split is represented as a current interval |
| 562 | // we iterate over currently active intervals and compute it's surface area |
| 563 | // then we split the interval with maximum surface area |
| 564 | // AP scaffold: possible optimization - seems like computeSA can be cached for unchanged intervals |
| 565 | InlineArray<Interval, 1024> splits; |
| 566 | splits.pushBack(Interval(0, clusterSize)); |
| 567 | for(PxU32 iSplit = 0; iSplit < RTREE_N-1; iSplit++) |
| 568 | { |
| 569 | PxF32 maxSAH = -FLT_MAX; |
| 570 | PxU32 maxSplit = 0xFFFFffff; |
| 571 | for(PxU32 i = 0; i < splits.size(); i++) |
| 572 | { |
| 573 | if(splits[i].count == 1) |
| 574 | continue; |
| 575 | PxF32 SAH = computeSA(permute, splits[i])*splits[i].count; |
| 576 | if(SAH > maxSAH) |
| 577 | { |
| 578 | maxSAH = SAH; |
| 579 | maxSplit = i; |
| 580 | } |
| 581 | } |
| 582 | PX_ASSERT(maxSplit != 0xFFFFffff); |
| 583 | |
| 584 | // maxSplit is now the index of the interval in splits array with maximum surface area |
| 585 | // we now split it into 2 using the split() function |
| 586 | Interval old = splits[maxSplit]; |
| 587 | PX_ASSERT(old.count > 1); |
| 588 | PxU32 splitLocal = split(permute+old.start, old.count); // relative split pos |
| 589 | |
| 590 | PX_ASSERT(splitLocal >= 1); |
| 591 | PX_ASSERT(old.count-splitLocal >= 1); |
| 592 | splits.pushBack(Interval(old.start, splitLocal)); |
| 593 | splits.pushBack(Interval(old.start+splitLocal, old.count-splitLocal)); |
| 594 | splits.replaceWithLast(maxSplit); |
| 595 | splitPos[iSplit] = old.start+splitLocal; |
| 596 | } |
| 597 | |
| 598 | // verification code, make sure split counts add up to clusterSize |
| 599 | PX_ASSERT(splits.size() == RTREE_N); |
| 600 | PxU32 sum = 0; |
| 601 | for(PxU32 j = 0; j < RTREE_N; j++) |
no test coverage detected