Building dynamic bounding box hierachies

Question

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?

Answer 1

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.

Answer 2

A basic method is to use Binary Space Partitioning.

Answer 3

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();
...

player->addChild( torso );
torso->addChild( head );
torso->addChild( larm );

...

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".