insertLeaf method
Insert a new leaf to the tree
Implementation
void insertLeaf(DBVTNode leaf){
if(root == null){
root = leaf;
return;
}
AABB lb = leaf.aabb;
DBVTNode? sibling = root;
double oldArea;
double newArea;
while(sibling?.proxy == null){ // descend the node to search the best pair
DBVTNode c1 = sibling!.child1!;
DBVTNode c2 = sibling.child2!;
AABB b = sibling.aabb;
AABB c1b = c1.aabb;
AABB c2b = c2.aabb;
oldArea = b.surfaceArea();
aabb.combine(lb,b);
newArea = aabb.surfaceArea();
double creatingCost = newArea*2;
double incrementalCost = (newArea-oldArea)*2; // cost of creating a new pair with the node
double discendingCost1 = incrementalCost;
aabb.combine(lb,c1b);
if(c1.proxy!=null){
// leaf cost = area(combined aabb)
discendingCost1+=aabb.surfaceArea();
}
else{
// node cost = area(combined aabb) - area(old aabb)
discendingCost1+=aabb.surfaceArea()-c1b.surfaceArea();
}
double discendingCost2=incrementalCost;
aabb.combine(lb,c2b);
if(c2.proxy!=null){
// leaf cost = area(combined aabb)
discendingCost2+=aabb.surfaceArea();
}
else{
// node cost = area(combined aabb) - area(old aabb)
discendingCost2+=aabb.surfaceArea()-c2b.surfaceArea();
}
if(discendingCost1<discendingCost2){
if(creatingCost<discendingCost1){
break;// stop descending
}
else{
sibling = c1;// descend into first child
}
}
else{
if(creatingCost<discendingCost2){
break;// stop descending
}
else{
sibling = c2;// descend into second child
}
}
}
DBVTNode? oldParent = sibling?.parent;
DBVTNode? newParent;
if(numFreeNodes>0){
newParent = freeNodes[--numFreeNodes];
}
else{
newParent = DBVTNode();
}
newParent.parent = oldParent;
newParent.child1 = leaf;
newParent.child2 = sibling;
newParent.aabb.combine(leaf.aabb,sibling!.aabb);
newParent.height = sibling.height+1;
sibling.parent = newParent;
leaf.parent = newParent;
if(sibling == root){
// replace root
root = newParent;
}
else{
// replace child
if(oldParent!.child1 == sibling){
oldParent.child1 = newParent;
}else{
oldParent.child2 = newParent;
}
}
// update whole tree
do{
newParent = balance(newParent!);
fix(newParent);
newParent = newParent.parent;
}while(newParent != null);
}