| 559 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
| 560 | |
| 561 | bool AABBPruner::buildStep(bool synchronousCall) |
| 562 | { |
| 563 | PX_PROFILE_ZONE("SceneQuery.prunerBuildStep", mContextID); |
| 564 | |
| 565 | PX_ASSERT(mIncrementalRebuild); |
| 566 | if(mNeedsNewTree) |
| 567 | { |
| 568 | if(mProgress==BUILD_NOT_STARTED) |
| 569 | { |
| 570 | if(!synchronousCall || !prepareBuild()) |
| 571 | return false; |
| 572 | } |
| 573 | else if(mProgress==BUILD_INIT) |
| 574 | { |
| 575 | mNewTree->progressiveBuild(mBuilder, mBuildStats, 0, 0); |
| 576 | mProgress = BUILD_IN_PROGRESS; |
| 577 | mNbCalls = 0; |
| 578 | |
| 579 | // Use a heuristic to estimate the number of work units needed for rebuilding the tree. |
| 580 | // The general idea is to use the number of work units of the previous tree to build the new tree. |
| 581 | // This works fine as long as the number of leaves remains more or less the same for the old and the |
| 582 | // new tree. If that is not the case, this estimate can be way off and the work units per step will |
| 583 | // be either much too small or too large. Hence, in that case we will try to estimate the number of work |
| 584 | // units based on the number of leaves of the new tree as follows: |
| 585 | // |
| 586 | // - Assume new tree with n leaves is perfectly-balanced |
| 587 | // - Compute the depth of perfectly-balanced tree with n leaves |
| 588 | // - Estimate number of working units for the new tree |
| 589 | |
| 590 | const PxU32 depth = Ps::ilog2(mBuilder.mNbPrimitives); // Note: This is the depth without counting the leaf layer |
| 591 | const PxU32 estimatedNbWorkUnits = depth * mBuilder.mNbPrimitives; // Estimated number of work units for new tree |
| 592 | const PxU32 estimatedNbWorkUnitsOld = mAABBTree ? mAABBTree->getTotalPrims() : 0; |
| 593 | if ((estimatedNbWorkUnits <= (estimatedNbWorkUnitsOld << 1)) && (estimatedNbWorkUnits >= (estimatedNbWorkUnitsOld >> 1))) |
| 594 | // The two estimates do not differ by more than a factor 2 |
| 595 | mTotalWorkUnits = estimatedNbWorkUnitsOld; |
| 596 | else |
| 597 | { |
| 598 | mAdaptiveRebuildTerm = 0; |
| 599 | mTotalWorkUnits = estimatedNbWorkUnits; |
| 600 | } |
| 601 | |
| 602 | const PxI32 totalWorkUnits = PxI32(mTotalWorkUnits + (mAdaptiveRebuildTerm * mBuilder.mNbPrimitives)); |
| 603 | mTotalWorkUnits = PxU32(PxMax(totalWorkUnits, 0)); |
| 604 | } |
| 605 | else if(mProgress==BUILD_IN_PROGRESS) |
| 606 | { |
| 607 | mNbCalls++; |
| 608 | const PxU32 Limit = 1 + (mTotalWorkUnits / mRebuildRateHint); |
| 609 | // looks like progressiveRebuild returns 0 when finished |
| 610 | if (!mNewTree->progressiveBuild(mBuilder, mBuildStats, 1, Limit)) |
| 611 | { |
| 612 | // Done |
| 613 | mProgress = BUILD_NEW_MAPPING; |
| 614 | #if PX_DEBUG |
| 615 | mNewTree->validate(); |
| 616 | #endif |
| 617 | } |
| 618 | } |
no test coverage detected