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.

Box2D v2.3.1 Released

Google Code no longer allows for downloads, therefore you will have to use SVN to get v2.3.1:

svn checkout http://box2d.googlecode.com/svn/tags/v2.3.1

You can view the changes here: https://code.google.com/p/box2d/source/list

The main change was the conversion of the Testbed to use GLFW and imgui instead of freeglut and GLUI. GLUI was not supported and I was having trouble with freeglut in newer versions of Visual Studio. If you work in Visual Studio 2013 or Xcode 5, you can open the project file and get started. On other platforms you will have to do more work to set things up. The big difference in running the Testbed is that the working path needs to be setup correctly so that the font may be loaded. In Visual Studio you can set the working path under the project settings. In Xcode you can setup a custom working directory in the Testbed scheme. The Testbed will crash if it fails to load the font file.

GDC 2014 Physics Tutorial

We had another successful tutorial this year at the Game Developer Conference in San Francisco. Thanks to everyone that attended!

Since Google Projects no longer hosts files, I am hosting new GDC files on this site. Get them here.

Next year I’d like to open up the Physics Tutorial a bit. If you’d like to present, please contact me on Twitter @erin_catto.

Computing a Basis

Given a normalized 3D vector, here’s an efficient method for computing a full basis. The computed basis is axis aligned if the input vector is axis aligned.

In SSE land you can eliminate the branch using a select operation.

Troublesome Triangle

I ran into a problem computing a polygon normal using Newell’s method as described in Christer Ericson’s excellent book Real-Time Collision Detection. In this case the polygon happens to a be a triangle that is close to the origin. So I would guess that Newell’s method would yield a great result. However, this is not true. I only get 2 digits of accuracy in single precision.

Here is the triangle:
p1 = (0.331916571f, 0.382771939f, -0.465963870f)
p2 = (0.378853887f, -0.246981591f, -0.440359056f)
p3 = (0.331879079f, 0.382861078f, -0.465974003f)

I knew I was getting a bad normal because some of my convex hull code was failing. So I decided to analyze the problem. First of all, this triangle has edge lengths of around 0.6320, 0.6321, and 1e-4. So this is a sliver and it is well known that slivers can be numerically challenging.

I computed a baseline normal using doubles. Doubles yielded the following normal vector (truncated to 6 digits):
normal_doubles = (0.206384 -0.0243884 -0.978167).
I got the same result computing the normal in many different ways. So I am confident that this is accurate.

Then I computed the normal many several different ways using single precision:
– 1 way using Newell’s method as stated in Christer’s book
– 3 ways using edge cross products
– 3 ways using Newell’s method on the triangle shifted to each vertex (suggested by Christer)
– 1 way using Newell’s method on the triangle shifted to the centroid

Here is the code:

And here are the results:
0.205007 -0.0244907 -0.978454
0.206384 -0.0243884 -0.978167
0.206417 -0.0243837 -0.97816
0.206384 -0.0243884 -0.978167
0.206377 -0.0243887 -0.978168
0.206453 -0.024386 -0.978153
0.206315 -0.0243899 -0.978182
0.206375 -0.0243882 -0.978169

Exact:
0.206384 -0.0243884 -0.978167

As you can see, Newell’s method is only giving 2 digits of accuracy. Every other method is giving close to 4 digits of accuracy or more. The best result is from n1 and n2. Both of these are cross products that include the shortest edge. This agrees with Gino van den Bergen’s comments on Twitter.

Shifting the triangle origin to one of the vertices or the centroid all improve Newell’s method substantially. I’m a little disappointed that Newell’s method is still not as good as _any_ of the cross products. The price of generality?

Bottom line:
1. Shift a vertex to the origin before applying Newell’s method.
2. Cross products can produce triangle normals that are superior to the results of Newell’s method.
3. Switching to doubles can solve numerical problems, but it is better to first understand the underlying issue.

New Testbed GUI

I’m making progress on a revised testbed framework using GLFW, GLEW, and imgui.

This is replacing the old framework that uses freeglut and GLUI. GLUI is no longer supported and freeglut has been having some problems with newer versions of Visual Studio. Maybe freeglut 3.0 will be better. GLFW is well maintained and very small. Hopefully it works well on OSX.

Anyhow, I’m excited by the results, so I decided to post a screenshot. I’m hoping to commit this in the next few days. I need to repair text rendering and get the XCode project fixed up.

NewTestbed

Box2D 2.3.0 Released

It has been a long time, but version 2.3.0 has finally been released. You can get it here: .

Here are the changes:

  • Polygon creation now computes the convex hull. Vertices no longer need to be ordered.
  • The convex hull code will merge vertices closer than dm_linearSlop. This may lead to failure on very small polygons.
  • Added b2MotorJoint.
  • Bug fixes.

Next year, Google Code will not allow new downloads: . So I am now using SVN tags for releases. If you want to switch over to using tags now, then you can use this:

svn checkout http://box2d.googlecode.com/svn/tags/v2.3.0

I plan to switch to this method for the next release of Box2D. Hopefully Google will make it easier to download a tagged version.

GDC 2013

This year’s physics tutorial was a lot of fun and all the speakers did a great job. We had some new speakers this year and all the presentations contained new material. You can get all the presentations here: Downloads. Look for files with a summary prefix of “GDC 2013″.

You can get Glenn Fiedler’s presentation here: click

__m128

The best way to use SSE is to use the __m128 intrinsic directly. Unfortunately Visual Studio displays the values backwards (w,z,y,x). Bleh. Here is a change to autoexp.dat to correct the order.

First comment out this line:

And add this line: