AABB Tree - Where's the poly o_O?

Yeah this is a common misunderstanding.

The building criteria you outline is correct, a polygon only goes into one bin (box or node if you prefer). The key is the collision checking, where you always check both nodes at the same level. That is you pass in a bounding AABB representing the potential collider. You traverse from the root, checking the input AABB against both of the root's child AABB nodes. If an overlap is detected you continue down that nodes branch, which can mean you continue down both in some cases.

It may sound strange, but it works rather well.

http://staff.hangarnet.com.br/horta/intersection.png

I believe I expressed myself inadequately. As you can see in this image, the intersection occurs in the bottom box. However, the polygon is only classified in the top box. This will cause a collision test failure, because the collision took place in the bottom box.

Thats because the bounding boxes are wrong or at least in what I consider to be an AABB tree. The two boxes you have divide the space in half, this is correct for building the tree, but not for collision checking. When checking a node for collision you should use a bounding box that encompasses all the polygons assigned to it. This means finding the min/max of all the polygon vertices.

I've got some old diagrams I did when I was working through this for an AABB tree of AABB's. I'll post it up in a moment. That should hopefully make it clear.

There is something called a "loose octree" that solves this problem. It has two nice properties, compared to the AABB or regular octrees:

1) the bounding radius of an object determines absolutely which level of the tree the object will be found in

2) objects are only inserted once, and all intersections are always found

As mentioned above, here is what I've done with AABB trees. I used to use Octrees, but my feeling is AABB trees are generally better and have switched to using them in most cases.


The first set of images shows the construction of the AABB Tree. In this case the tree contains AABB primitives, but they could just as easily be polygons.

AABB tree Construction Diagram

Image 1 (row 1): shows all the elements that need to be placed into the tree (root).

Image 2 (row 1): shows the first split (black line). All element center points above this line are added to the 'left' node, those below are added to the 'right' node.

Image 3 (row 2): Shows the 'left' node (red box outline), notice its AABB encompasses all the elements in the node, and is not the size of the node itself as defined by the splitting plane (in Image 2 - blackline)

Image 4 (row 2): Shows the previous 'left' node itself split into a left (red) and right (blue) node.

Image 5 to 7 continue the binary splits

Image 8 (row 3) Shows the 'right' node (blue box outline) of the Root (image 2) Notice its bounding box overlaps that of the 'left' node (red).


The second image shows collision checking. The two pink circles illustrate the start/end points of the collider, whilst the pink box outline is its AABB to send through the tree.

Collision Checking Diagram

Image 1. The Collider AABB clearly overlaps both 'left' (red) and 'right' (blue) nodes, so both branches are traversed.

Image 2. Shows the 'left' node, where this time the AABB only overlaps the new 'left' node, so we ignore the 'right' node, and continue.

Image 3. Shows the leaf of this branch, where only two bounding boxes are left the actual elements 'A' and 'E'. In this case our AABB only overlaps 'E' so this is added to our potential collision list.

Image 4 shows the 'right' node traversal (from image 1), where it only overlaps the 'left' node bounding box.

Image 5. shows the leaf of this branch with elements 'D' and 'G' and where our AABB only overlaps with 'D' so we add this to our potential collision list.

As we've reached the leaves there are no more checks, we can now use the potential collision list to carry out more accruate collision checks.


Hope this helps.

Quote:

Original post by Jungle Boy I believe I expressed myself inadequately. As you can see in this image, the intersection occurs in the bottom box. However, the polygon is only classified in the top box. This will cause a collision test failure, because the collision took place in the bottom box.

Yes, this is a problem. Currently, these are solutions you could use:

* Use a different way to build your tree, by guaranteeing that each primitive is always encompassed by the tree node it resides in. That's basically what noisecrime was suggesting. This approach works well, but can lead to very inefficient hierarchies, if your primitives are large and not well localized.

* Put the primitive into both nodes (or even more, if it overlaps more than two nodes), and keep track of the primitive using flags, so to avoid multiple checks on the same faces.

* Use a tree where geometry can also be stored in the nodes themselves, rather than in the leaves alone. A primitive encompassing both child nodes will be placed in the parent node directly. This scheme guarantees zero doubles, but has a bad tendency to 'cluster' geometry in a very shallow tree, making it inefficient again.

* Split the primitive into multiple parts.

[shameless plug]
Of course, an ABT will solve your problem by a balanced combination of growing nodes and splitting geometry. It is also usable on moving and dynamic geometry, and will guarantee zero double assignments. It is however harder to implement.
[/shameless plug]

I'm very pleased with your replies, guys ;P

noisecrime, your diagrams explain very well this approach to build an AABB Tree and collision checking, i think you must make a tuto for that ;P, its not very easy to find information about AABB Tree, thanks.

I'm thinking about the possibility to use a mix of octree and aabbtree. The first one would be to carry polys of static meshes (like the buildings, trees, terrain) and also, in the leaf nodes, to store information about the intersecting AABB of dynamic meshes, the last one without regard of its polys and how many polys a leaf node of an octree should have (of course, in this way, same dynamic meshes would be in more than one octree leaf node). So to do frustum culling, i would use the leaf nodes of octree to render its polys of static meshes normally and dynamic meshes (the last one, entirely) and to do collision checking, for static_mesh vs dynamic_mesh i would use the octree leaf nodes where the dynamic_mesh lies and test its AABBs (of the dynamic mesh) against the polys (of static meshes) of the corresponding leaf nodes.

Thus i believe the management of octree will be very easy and fast because i won't have to rebalance its nodes (because the static meshes don't move and the dynamic meshes will be stored without regard of its quantity of polys and so on).

Anyone have implemented something like that? I forgot something?