# Building dynamic bounding box hierachies

I've been reading about collision detection and I saw that the first part was a coarse detection which generates possible contacts using bounding box hierarchies.

I understand the concept of splitting up your objects in groups, to speed up the detection phase, but I'm a little confused on how do you actually build the hierachy, more so on what criteria is used to group them together.

Do I iterate through all the objects in the scene, and check the distance between them to see where they should be inserted in the tree?

Do you know some resources that may shed some light on this topic for me?

With 50 independent cubes manuvering all around your 3d world, I might consider a 3 level oct tree. that splits your world up into 64 nodes (Axis Aligned Bounding boxes). Each frame you determine which of the 64 boxes each cube is in, then foreach cube, if there are more than one cube in that node, check each against the others in that node, else move onto next cube or frame.

How you build it? Create a bounding box that encompasses the entire world, determine the corner positions, determine points hallfway between each corner, build 8 smaller bounding boxes based on those 'halfway points'. then foreach of the 8 bounding boxes you just built, repeat: determine their corner positions, then determine points halfway between, then build 8 boxes within each box.

this would take approx 150 to 175 AABB to AABB checks each frame instead of the 1200 a brute force check would take.

• Thanks, exactly what I was looking for.A nice concise answer. Jun 24 '11 at 9:27

A basic method is to use Binary Space Partitioning.

I think that the hierarchy that you want to know about is the called "scene graph".

The scene graph hierarchy has a lot of benefits, the majority of game engines use one. One of these benefits is the optimization of calculations. For example, collision detection ( the topic that you are asking ) and graphic culling to avoid send much information to the graphics card that is not visible.

The better form to know more about scene graphs is use one and see the features that have. For example, OpenSceneGraph or Ogre3D.

An overview:

A scene graph use basically the composition design pattern. A node can have more nodes, and the childs can have more nodes, ...

A node example:

class Node
{
public:
void addChild( Node* child );
void removeFromParent();
AABB calculateBoundingBox(); // Axis-aligned bounding box

private:
std::list< Node* >       m_children;
vector3                  m_positionRelativeToParentNode;
matrix4                  m_transformation;
};


Then, the construction that you're asking is composed when the scene is being created. I'm going to create a soccer player.

Node* player = new Node();
Node* torso = new Node();
Node* head = new Node();
Node* larm = new Node();
...

...


Ok. The player is composed. With the transformation of each node, and the position relative to the parent node, the bounding box can be calculated.

If we calculate the AABB of the player, and we do a collision test with other player, then is when we descend to the children and the collision test is done with more precision. If the test is not passed at player level, the children tests are not necessary ( we are optimizing ).

How to calculate the bounding box? Think that each node has his own coordinate system. The relative position to the coordinate system of the parent is the member Node::m_positionRelativeToParentNode, and the member Node::m_transformation is the own transformation in his coordinate system. With this information, we can calculate the bounding box of a node. Remind that if we know test two nodes, they must "live" in the same coordinate system. Then we need compose the transformations and go up to a common parent and do the test in the common parent coordinate system.

Edited:

There is a really good book about collision detection called: "Real Time Collision Detection".

• Hi, thanks for the time you took to write this answer.I have a subsequent question though.Let's say I have a scene where there's like 50 independent cubes and I need to test for collisions.If I only use a scene graph, I'll end up with a tree with 1 parent and 50 nodes and this doesn't seem to be an improvement.That's why I was asking how I can generate a tree based somehow on the proximity of the objects.I understand that I can use the scene graph to group the cubes together, but if they move independently then the tree won't be accurate anymore. Jun 23 '11 at 22:23
• In this extreme case, it will be good to have a special scene graph like a bsp or a octree. I say special because these structures can be seen like a specialization of a scene graph. In these structures, each node is responsible of a area or volume, nodes never move, the only are used to do collision/visible tests. Then, each node has other game nodes attached. These game nodes ( the 50 nodes that you are talking about, that can have other scene graph ) are attached or deattached to the nodes of the bsp/octree dynamically, if they move, your game logic is responsible to do the changes needed. Jun 23 '11 at 22:45
• Yes, you iterate through all objects in the dynamically attach/detach of the game nodes to the octree/bsp. The optimization deals in the bounding box number of tests to know what new octree/bsp node correspond. Jun 23 '11 at 22:54