Suppose you have a plane equation in local space and you’d like to express that plane equation in world space. The plane in local space is written as:
\[ P := (n, w) \]
where \(n\) is the plane normal and \(w\) is the plane offset.

A point \(x\) is on the plane if
\[n \cdot x = w \]

Now define a transform \(A\) as
\[ A := (R, p) \]
where \(R\) is an orthonormal rotation matrix and \(p\) is a translation vector.

Suppose we have a transform \(A\) that transforms points in local space into world space. With our transform \(A\) we can convert any point \(x_1\) in local space (space 1) into world space (space 2):
\[x_2 = R x_1 + p\]
Also any vector \(n_1\) in local space can be converted to world space:
\[n_2 = R n_1\]

Also suppose we have a plane defined in local space (space 1). Then for any point \(x_1\) in local space:
\[n_1 \cdot x_1 = w_1 \]

The main problem now is to find \(w_2\), the plane offset in world space. We can achieve this by substitution. First invert the transform relations above:
\[x_1 = R^T (x_2 – p)\]
\[n_1 = R^T n_2\]
where \(R^T\) is the transpose of \(R\). Recall that the inverse of an orthonormal matrix is the equal to the transpose.

Now substitute these expressions into the local space plane equation:
\[R^T n_2 \cdot (R^T (x_2 – p)) = w_1\]

Expand:
\[R^T n_2 \cdot R^T x_2 – R^T n_2 \cdot R^T p = w_1\]

The rotations cancel out since they are orthonormal. Also the dot product is equivalent to matrix multiplication by the transpose. For example:
\[R^T n_2 \cdot R^T x_2 = n_2^T R R^T x_2 = n_2^T I x_2 = n_2 \cdot x_2\]

Simplify:
\[n_2 \cdot x_2 = w_1 + n_2 \cdot p\]

From this we can identify the world space plane offset \(w_2\):
\[w_2 = w_1 + n_2 \cdot p\]

Done!

Update:
Of course it is easy to transform a plane if you have it expressed in terms of a normal and position:
\[P := (n,a)\]
where \(a\) is a point on the plane. The trick is then to find \(a\) given just the normal and offset description.
\[n \cdot x = w \]
After looking at this for a minute, it appears that if I use the point:
\[a := wn\]
then
\[n \cdot wn = w(n \cdot n) = w\]
so it is easy to find a point on the plane given the normal and offset. Then we can just transform \(n\) and \(a\).

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.