Method mergeTree

physx/source/scenequery/src/SqAABBTree.cpp:837–917

Merge the input tree into current tree. Traverse the tree and find the smallest node, where the whole new tree fits. When we find the node we create one new node pointing to the original children and the to the input tree root.

// Traverse the tree and find the smallest node, where the whole new tree fits. When we find the node 
// we create one new node pointing to the original children and the to the input tree root.
void AABBTree::mergeTree(const AABBTreeMergeData& treeParams)
{ 
	// allocate new indices buffer 	
	PxU32* newIndices = reinterpret_cast<PxU32*>(PX_ALLOC(sizeof(PxU32)*(mNbIndices + treeParams.mNbIndices), "AABB tree indices"));
	PxMemCopy(newIndices, mIndices, sizeof(PxU32)*mNbIndices);
	PX_FREE(mIndices);
	mIndices = newIndices;
	mTotalPrims += treeParams.mNbIndices;

	// copy the new indices, re-index using the provided indicesOffset. Note that indicesOffset 
	// must be provided, as original mNbIndices can be different than indicesOffset dues to object releases.	
	for (PxU32 i = 0; i < treeParams.mNbIndices; i++)
	{
		mIndices[mNbIndices + i] = treeParams.mIndicesOffset + treeParams.mIndices[i];
	}	

	// check the mRefitBitmask if we fit all the new nodes
	mRefitBitmask.resize(mTotalNbNodes + treeParams.mNbNodes + 1);	

	// create the parent information so we can update it
	if(!mParentIndices)
	{
		mParentIndices = reinterpret_cast<PxU32*>(PX_ALLOC(sizeof(PxU32)*mTotalNbNodes, "AABB parent indices"));
		_createParentArray(mTotalNbNodes, mParentIndices, mRuntimePool, mRuntimePool, mRuntimePool);
	}		
	
	// if new tree is inside the root AABB we will traverse the tree to find better node where to attach the tree subnodes
	// if the root is a leaf we merge with the root. 		
	if(treeParams.getRootNode().mBV.isInside(mRuntimePool[0].mBV) && !mRuntimePool[0].isLeaf())
	{
		traverseRuntimeNode(mRuntimePool[0], treeParams, 0);
	}
	else
	{				
		if(mRuntimePool[0].isLeaf())
		{			
			mergeRuntimeLeaf(mRuntimePool[0], treeParams, 0);
		}
		else		
		{			
			mergeRuntimeNode(mRuntimePool[0], treeParams, 0);		
		}

		// increase the tree root AABB
		mRuntimePool[0].mBV.include(treeParams.getRootNode().mBV);
	}

#ifdef _DEBUG
	//verify parent indices
	for (PxU32 i = 0; i < mTotalNbNodes; i++)
	{
		if (i)
		{
			PX_ASSERT(mRuntimePool[mParentIndices[i]].getPosIndex() == i || mRuntimePool[mParentIndices[i]].getNegIndex() == i);
		}
		if (!mRuntimePool[i].isLeaf())
		{
			PX_ASSERT(mParentIndices[mRuntimePool[i].getPosIndex()] == i);