Merge tree into targetNode, where target node is not a leaf 1. Allocate new nodes/parent, copy the nodes/parents till targetNodePosIndex 2. Create new node , copy the data from target node 3. Copy the rest of the target tree nodes/parents at the end -> targetNodePosIndex + 1 + treeParams.mNbNodes 4. Copy the merge tree after the new node, create the parent map for them, update the leaf indices 5.
| 712 | // Merged tree: ...Tn->...->Nc0,R1->Rc0,Rc1...,Tc0,Tc1... |
| 713 | // where new node: Nc0->...->Tc0,Tc1 |
| 714 | void AABBTree::mergeRuntimeNode(AABBTreeRuntimeNode& targetNode, const AABBTreeMergeData& treeParams, PxU32 targetMergeNodeIndex) |
| 715 | { |
| 716 | PX_ASSERT(mParentIndices); |
| 717 | PX_ASSERT(!targetNode.isLeaf()); |
| 718 | |
| 719 | // Get the target node child pos, this is where we insert the new node and the input tree |
| 720 | const PxU32 targetNodePosIndex = targetNode.getPosIndex(); |
| 721 | |
| 722 | // 1. Allocate new nodes/parent, copy the nodes/parents till targetNodePosIndex |
| 723 | // allocate new runtime pool with max combine number of nodes |
| 724 | // we allocate only 1 additional node each merge |
| 725 | AABBTreeRuntimeNode* newRuntimePool = PX_NEW(AABBTreeRuntimeNode)[mTotalNbNodes + treeParams.mNbNodes + 1]; |
| 726 | PxU32* newParentIndices = reinterpret_cast<PxU32*>(PX_ALLOC(sizeof(PxU32)*(mTotalNbNodes + treeParams.mNbNodes + 1), "AABB parent indices")); |
| 727 | // copy the untouched part of the nodes and parents |
| 728 | PxMemCopy(newRuntimePool, mRuntimePool, sizeof(AABBTreeRuntimeNode)*(targetNodePosIndex)); |
| 729 | PxMemCopy(newParentIndices, mParentIndices, sizeof(PxU32)*(targetNodePosIndex)); |
| 730 | |
| 731 | PxU32 nodeIndex = targetNodePosIndex; |
| 732 | // 2. Create new node , copy the data from target node |
| 733 | newRuntimePool[nodeIndex].mBV = targetNode.mBV; |
| 734 | newRuntimePool[nodeIndex].mData = ((targetNode.mData >> 1) + 1 + treeParams.mNbNodes) << 1; |
| 735 | // update parent information |
| 736 | newParentIndices[nodeIndex] = targetMergeNodeIndex; |
| 737 | |
| 738 | // handle mark for refit |
| 739 | if(mRefitBitmask.getBits() && mRefitBitmask.isSet(targetMergeNodeIndex)) |
| 740 | { |
| 741 | mRefitBitmask.setBit(nodeIndex); |
| 742 | const PxU32 currentMarkedWord = nodeIndex >> 5; |
| 743 | mRefitHighestSetWord = PxMax(mRefitHighestSetWord, currentMarkedWord); |
| 744 | } |
| 745 | |
| 746 | // 3. Copy the rest of the target tree nodes/parents at the end -> targetNodePosIndex + 1 + treeParams.mNbNodes |
| 747 | if(mTotalNbNodes - targetNodePosIndex) |
| 748 | { |
| 749 | PX_ASSERT(mTotalNbNodes - targetNodePosIndex > 0); |
| 750 | PxMemCopy(newRuntimePool + targetNodePosIndex + 1 + treeParams.mNbNodes, mRuntimePool + targetNodePosIndex, sizeof(AABBTreeRuntimeNode)*(mTotalNbNodes - targetNodePosIndex)); |
| 751 | PxMemCopy(newParentIndices + targetNodePosIndex + 1 + treeParams.mNbNodes, mParentIndices + targetNodePosIndex, sizeof(PxU32)*(mTotalNbNodes - targetNodePosIndex)); |
| 752 | } |
| 753 | // swap the pointers, release the old memory |
| 754 | PX_DELETE_ARRAY(mRuntimePool); |
| 755 | mRuntimePool = newRuntimePool; |
| 756 | PX_FREE(mParentIndices); |
| 757 | mParentIndices = newParentIndices; |
| 758 | |
| 759 | // 4. Copy the merge tree after the new node, create the parent map for them, update the leaf indices |
| 760 | nodeIndex++; |
| 761 | addRuntimeChilds(nodeIndex, treeParams); |
| 762 | PX_ASSERT(nodeIndex == targetNodePosIndex + 1 + treeParams.mNbNodes); |
| 763 | // update the total number of nodes |
| 764 | mTotalNbNodes = mTotalNbNodes + 1 + treeParams.mNbNodes; |
| 765 | |
| 766 | // update the parent information for the input tree root node |
| 767 | mParentIndices[targetNodePosIndex + 1] = targetMergeNodeIndex; |
| 768 | |
| 769 | // 5. Go through the nodes copied at the end and fix the parents/childs |
| 770 | for (PxU32 i = targetNodePosIndex + 1 + treeParams.mNbNodes; i < mTotalNbNodes; i++) |
| 771 | { |