| 649 | // where new node: Nc0==Tn and Tnc is not a leaf anymore and points to Nc0 |
| 650 | |
| 651 | void AABBTree::mergeRuntimeLeaf(AABBTreeRuntimeNode& targetNode, const AABBTreeMergeData& treeParams, PxU32 targetMergeNodeIndex) |
| 652 | { |
| 653 | PX_ASSERT(mParentIndices); |
| 654 | PX_ASSERT(targetNode.isLeaf()); |
| 655 | |
| 656 | // 1. Allocate new nodes/parent, copy all the nodes/parents |
| 657 | // allocate new runtime pool with max combine number of nodes |
| 658 | // we allocate only 1 additional node each merge |
| 659 | AABBTreeRuntimeNode* newRuntimePool = PX_NEW(AABBTreeRuntimeNode)[mTotalNbNodes + treeParams.mNbNodes + 1]; |
| 660 | PxU32* newParentIndices = reinterpret_cast<PxU32*>(PX_ALLOC(sizeof(PxU32)*(mTotalNbNodes + treeParams.mNbNodes + 1), "AABB parent indices")); |
| 661 | |
| 662 | // copy the whole target nodes, we will add the new node at the end together with the merge tree |
| 663 | PxMemCopy(newRuntimePool, mRuntimePool, sizeof(AABBTreeRuntimeNode)*(mTotalNbNodes)); |
| 664 | PxMemCopy(newParentIndices, mParentIndices, sizeof(PxU32)*(mTotalNbNodes)); |
| 665 | |
| 666 | // 2. Create new node at the end, copy the data from target node |
| 667 | PxU32 nodeIndex = mTotalNbNodes; |
| 668 | // copy the targetNode at the end of the new nodes |
| 669 | newRuntimePool[nodeIndex].mBV = targetNode.mBV; |
| 670 | newRuntimePool[nodeIndex].mData = targetNode.mData; |
| 671 | // update the parent information |
| 672 | newParentIndices[nodeIndex] = targetMergeNodeIndex; |
| 673 | |
| 674 | // mark for refit |
| 675 | if (mRefitBitmask.getBits() && mRefitBitmask.isSet(targetMergeNodeIndex)) |
| 676 | { |
| 677 | mRefitBitmask.setBit(nodeIndex); |
| 678 | const PxU32 currentMarkedWord = nodeIndex >> 5; |
| 679 | mRefitHighestSetWord = PxMax(mRefitHighestSetWord, currentMarkedWord); |
| 680 | } |
| 681 | |
| 682 | // swap pointers |
| 683 | PX_DELETE_ARRAY(mRuntimePool); |
| 684 | mRuntimePool = newRuntimePool; |
| 685 | PX_FREE(mParentIndices); |
| 686 | mParentIndices = newParentIndices; |
| 687 | |
| 688 | // 3. Copy the merge tree after the new node, create the parent map for them, update the leaf indices |
| 689 | nodeIndex++; |
| 690 | addRuntimeChilds(nodeIndex, treeParams); |
| 691 | PX_ASSERT(nodeIndex == mTotalNbNodes + 1 + treeParams.mNbNodes); |
| 692 | |
| 693 | // update the parent information for the input tree root node |
| 694 | mParentIndices[mTotalNbNodes + 1] = targetMergeNodeIndex; |
| 695 | |
| 696 | // fix the child information for the target node, was a leaf before |
| 697 | mRuntimePool[targetMergeNodeIndex].mData = mTotalNbNodes << 1; |
| 698 | |
| 699 | // update the total number of nodes |
| 700 | mTotalNbNodes = mTotalNbNodes + 1 + treeParams.mNbNodes; |
| 701 | } |
| 702 | |
| 703 | // Merge tree into targetNode, where target node is not a leaf |
| 704 | // 1. Allocate new nodes/parent, copy the nodes/parents till targetNodePosIndex |