insertLeaf method

void insertLeaf(DBVTNode leaf)

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);
}