Remove a leaf node from the tree
| 347 | |
| 348 | // Remove a leaf node from the tree |
| 349 | void DynamicAABBTree::removeLeafNode(int nodeID) { |
| 350 | |
| 351 | assert(nodeID >= 0 && nodeID < mNbAllocatedNodes); |
| 352 | assert(mNodes[nodeID].isLeaf()); |
| 353 | |
| 354 | // If we are removing the root node (root node is a leaf in this case) |
| 355 | if (mRootNodeID == nodeID) { |
| 356 | mRootNodeID = TreeNode::NULL_TREE_NODE; |
| 357 | return; |
| 358 | } |
| 359 | |
| 360 | int parentNodeID = mNodes[nodeID].parentID; |
| 361 | int grandParentNodeID = mNodes[parentNodeID].parentID; |
| 362 | int siblingNodeID; |
| 363 | if (mNodes[parentNodeID].children[0] == nodeID) { |
| 364 | siblingNodeID = mNodes[parentNodeID].children[1]; |
| 365 | } |
| 366 | else { |
| 367 | siblingNodeID = mNodes[parentNodeID].children[0]; |
| 368 | } |
| 369 | |
| 370 | // If the parent of the node to remove is not the root node |
| 371 | if (grandParentNodeID != TreeNode::NULL_TREE_NODE) { |
| 372 | |
| 373 | // Destroy the parent node |
| 374 | if (mNodes[grandParentNodeID].children[0] == parentNodeID) { |
| 375 | mNodes[grandParentNodeID].children[0] = siblingNodeID; |
| 376 | } |
| 377 | else { |
| 378 | assert(mNodes[grandParentNodeID].children[1] == parentNodeID); |
| 379 | mNodes[grandParentNodeID].children[1] = siblingNodeID; |
| 380 | } |
| 381 | mNodes[siblingNodeID].parentID = grandParentNodeID; |
| 382 | releaseNode(parentNodeID); |
| 383 | |
| 384 | // Now, we need to recompute the AABBs of the node on the path back to the root |
| 385 | // and make sure that the tree is still balanced |
| 386 | int currentNodeID = grandParentNodeID; |
| 387 | while(currentNodeID != TreeNode::NULL_TREE_NODE) { |
| 388 | |
| 389 | // Balance the current sub-tree if necessary |
| 390 | currentNodeID = balanceSubTreeAtNode(currentNodeID); |
| 391 | |
| 392 | assert(!mNodes[currentNodeID].isLeaf()); |
| 393 | |
| 394 | // Get the two children of the current node |
| 395 | int leftChildID = mNodes[currentNodeID].children[0]; |
| 396 | int rightChildID = mNodes[currentNodeID].children[1]; |
| 397 | |
| 398 | // Recompute the AABB and the height of the current node |
| 399 | mNodes[currentNodeID].aabb.mergeTwoAABBs(mNodes[leftChildID].aabb, |
| 400 | mNodes[rightChildID].aabb); |
| 401 | mNodes[currentNodeID].height = std::max(mNodes[leftChildID].height, |
| 402 | mNodes[rightChildID].height) + 1; |
| 403 | assert(mNodes[currentNodeID].height > 0); |
| 404 | |
| 405 | currentNodeID = mNodes[currentNodeID].parentID; |
| 406 | } |
nothing calls this directly
no test coverage detected