Balancing Dynamic Trees

I received this question on LinkedIn:
I’m working on a 3d dynamic aabb tree based on the concepts of Presson’s bullet contribution. I came across a bullet forum thread in which Dirk recommended looking at your box2d implementation. I noticed the major difference is that box2d is a balanced tree using a surface area heuristic while bullet’s is unbalanced with manhattan distance heuristic.

My guess is that keeping your tree balanced resulted in increased maintenance overhead but decreased tree query times. Was there any benchmark of this anywhere that measured if the tradeoff was worth it? Or if there was any other motivation for implementing it this way?

Here is my reply:
A dynamic tree must be actively balanced through rotations (like AVL trees), otherwise you can easily have the tree degenerate into a very long linked list.

For example, imagine a world with many boxes in a row. Say 100 boxes extending along the x-axis. If the boxes are added to the tree at the origin and then incrementally along the x-axis, you will end up not with a tree, but a linked list with 100 elements. You do not need to run a benchmark to know this will yield horrible query performance. Not only will the performance be bad, but you will also need a large stack to process queries (ray casts or overlap tests).

This may sound like a contrived example, but this actually happens a lot in games. Imagine a side scrolling game, as the player moves through the world, objects are added in a linear fashion.

The Bullet code attempts to keep the tree balanced through random removal and insertions. In my tests, I found situations where this would take thousands of iterations to balance the tree reasonably. So I decided to implement tree rotations like you will find in AVL trees. It is actually a little bit simpler since there is no strict right-left sorting necessary.

5 thoughts on “Balancing Dynamic Trees

  1. ” you will end up not with a tree, but a linked list with 100 elements ”
    i think, it would not be completely like a linked list. because all nodes either have both or neither children. in worst situation it would be like this :

    *
    / \
    *
    / \
    *
    / \
    …..
    Am i wrong?

    • You are probably right. In terms of cost of computation it scales like a linked list.

  2. >>In my tests, I found situations where this would take
    >>thousands of iterations to balance the tree reasonably.

    Interesting, I haven’t run into this issue myself yet, but it is better safe than sorry.
    Can you describe this test that requires thousands of iterations?

  3. Hi Erwin! I give the example above. You simply need a world where you have many boxes along a single axis. The boxes should be added to the world starting at the origin and then progressing down the single axis. I recommend trying this yourself.

  4. Hey Erin, have you considered, R-Trees? It seems it could be quite a cool step forward compared to more “vanilla” AABB tree implementations. In particular the R*-tree seems interesting.

Comments are closed.