Dynamic Tree Insertion

Dynamic tree insertion can be expensive if you try to optimize for some metric such as the surface area heuristic (SAH). The SAH tries find a node configuration that minimizes the total surface area of all internal nodes. The idea is to create fewer node visits for ray casts on average.

Insertion affects the surface area incrementally so it is essentially a greedy algorithm no matter how exhausive the search. Therefore, an exhaustive search is not justified.

This document describes the greedy insertion heuristic used in the Box2D dynamic tree that attempts to minimize the the surface area with a single decent through the tree. So this only follows a single path through the tree and may stop at any level to create a new internal node to parent the inserted node.

The algorithm starts with an existing tree and a new proxy D to be inserted. The proxy has a surface area areaD. We are looking for a node that will be a sibling to D. The initial choice is the root node. The cost of making D a sibling of a node S is the direct cost, which is the area of the union of D and S.

float directCost = Area(Union(D, S));

This cost is because I will need to create a new node that is a parent of D and S and that is the area of the new node.

There is also the area of the current sibling candidate:

float areaBase = Area( S );

There is also an inherited cost that must be maintained as I decend the tree. This starts at zero. This is the incremental cost of increasing the internal nodes bounds as D is pushed down the tree.

float ineritedCost += directCost - areaBase;

For any internal node I need to predict the cost of decending the right or left branch (child1 or child2).

There is the directCost:

float directCost1 = Area(Union(C1, D));

If child1 is a leaf then cost of choosing child1 as the sibling is:

float cost1 = directCost1 + inheritedCost;

This is an accurate cost because it represents the increased area of the internal nodes of the tree exactly.

If child1 is an internal node then I do not know how much area that sub-tree will add as I decend it with the new proxy D.

I choose to be optimistic about decending into a branch with an internal node. So what is the best result I can expect? I have the current inherited cost which cannot be ignored. Then I have the direct cost associated with creating a sibling with D. The sum of these two is actually conservative. It could be that I decent into branch 1 and I find some sibling with a lower direct cost. The lowest direct cost would be finding a sibling bounds that matches D. That would create a new internal node of areaD. And that could be a child of child1. In that case the cost would be

float cost1 = inheritedCost + Area(Union(C1, D)) - Area(C1) + Area(D);

If Area(D) > Area(C1) then

cost1 > inheritedCost + Area(Union(C1, D))

But this is the cost of choosing C1 as S. So I need to add some clamping in so that C1 could become S.

cost1 = inheritedCost + Area(Union(C1,D)) + Min(Area(D) - Area(C1), 0);

inheritedCost + directCost1 // Cost of using child1 as the sibling
inheritedCost + (directCost1 - area1) + areaD // Lowest possible cost of using a descendant of child1 as sibling

// Take the min of these two options and simplify:
min(inheritedCost + directCost1, inheritedCost + (directCost1 - area1) + areaD)
== inheritedCost + directCost1 + min(0, -area1 + areaD)