AABBtrees in local coordinate systems
by Kenny Hoff

In order to quickly compute the intersection between two objects, we can check for 
overlap hierarchically by using a bounding volume hierarchy over the two objects. 
The process proceeds as follows given to bounding volume nodes:

1) Check if the two nodes overlap.
2) If they do, then recursively apply overlap between all children.
   (in the case of a binary tree, we will have to perform four more overlap
   tests each time we recurse).
3) If they do not, then the objects do not overlap (this could simply be a
   subtree).

The simplest strategy would be to create an axis-aligned bounding box hierarchy
over the two objects in a common world space. This results in simple interval 
checking to perform the overlap test (min/max tests along each axis); however, if 
an object moves, the hierarchy must be rebuilt, since it is formed from axis-
aligned extents in world space. Rebuilding a tree is prohibitively expensive since 
it must be applied to all nodes of the hierarchy.

An alternative is to use oriented bounding boxes (OBB), where each box is "rotated 
to tightly fit". Each OBBtree node has its own coordinate system, so the overlap 
test must be general enough to test between two boxes of arbitrary pose. Each 
overlap test at all levels of the tree have equivalent numbers of operations. 
There is no reuse of calculations down the tree. Nevertheless, the OBBtree tightly 
conforms to the shape of the object asymptotically faster than a comparable 
AABBtree.

Another approach that could combine the ease of interval checking in the AABBtree 
while still avoiding the hierarchy rebuilding for dynamic objects as in the 
OBBtree would be to use an AABBtree in each object's local coordinate system. An 
AABBtree is built for each object relative to its own coordinate system and the 
general position and orientation of the object is stored at the root. This avoids 
the hierarchy rebuilding, but what about the overlap tests? Obviously two 
AABBtrees can be at an arbitrary pose to each other, so the overlap test must 
still be quite general. At the top level this may be true, but as we traverse down 
the hierarchies perhaps we can reuse many calculations performed at the root.

We must first figure out a simple overlap test between to oriented bounding boxes. 
Here is the approach I have in mind:

Given two object A and B with an AABB for each in their local coordinate systems. 
In other words, each object has a set of coordinate axes, an origin, and the 
extents (min/max) along each axis. We will define the axes and origin of A and B 
as follows: AX, AY, AZ, AO, BX, BY, BZ, and BO. Min and max will be denoted m and 
M respectively.

The basic overlap test begins by finding object A's extents (the extreme points of 
A's AABB) in B's coordinate system. The simplest strategy is to simply transform 
the eight corners of A's AABB into B's coordinate system. The calculations proceed 
as follows:

  Eight corners of A's AABB (given m and M for A):
  1) (Amx,Amy,Amz)
  2) (AMx,AMy,AMz)
  3) (Amx,AMy,AMz)
  4) (AMx,Amy,AMz)
  5) (AMx,AMy,Amz)
  6) (AMx,Amy,Amz)
  7) (Amx,AMy,Amz)
  8) (Amx,Amy,AMz)

  Transformation from A to B:

  (I) translate -AO

   1) (Amx-AOx, Amy-AOy, Amz-AOz)
   2) (AMx-AOx, AMy-AOy, AMz-AOz)
   3) (Amx-AOx, AMy-AOy, AMz-AOz)
   4) (AMx-AOx, Amy-AOy, AMz-AOz)
   5) (AMx-AOx, AMy-AOy, Amz-AOz)
   6) (AMx-AOx, Amy-AOy, Amz-AOz)
   7) (Amx-AOx, AMy-AOy, Amz-AOz)
   8) (Amx-AOx, Amy-AOy, AMz-AOz)

  (II) rotate A to world coord system by using A's axes as columns 
       of 3x3 rotation matrix:
.
.
.
    

Rather than transforming the eight corners of A's AABB into B's coordinate system 
and do a min/max search, we can reduce this to only six (not necessarily unique) 
corners if we can find the extremes. The extremes in B's coordinate system are 
defined along B's coordinate axes. If we transform B's axes in A's coordinate 
system, we will know along which axes the extreme points of A in B's coordinate 
system lie.

  Transform B's coordinate axes into A's coordinate system:

    [ - BX - ]   [ |  |  |  ]   [ |   |   |   ]
    [ - BY - ] * [ AX AY AZ ] = [ AX' AY' AZ' ]
    [ - BZ - ]   [ |  |  |  ]   [ |   |   |   ]
.
.
.