Axis-Aligned Bounding Boxes vs Bounding Ellipse

Question

Why is it that most, if not all collision detection algorithms today require each body to have an AABB for the use in the broad phase only?

It seems to me like simply placing a circle at the body's centroid, and extending the radius to where the circle encompasses the entire body would be optimal. This would not need to be updated after the body rotates and broad overlap-calculation would be faster to. Correct?

Bonus:
Would a bounding ellipse be practical for broad phase calculations also, since it would better represent long, skinny shapes? Or would it require extensive calculations, defeating the purpose of broad-phase?

Answer 1

It seems to me like simply placing a circle at the body's centroid, and extending the radius to where the circle encompasses the entire body would be optimal.

Would be optimal for what? It all depends on what you're trying to accomplish.

The bounding sphere will generally have a larger volume than the axis-aligned bounding box. Which means that more things will touch each other. So, while the bounding sphere is faster to test against other bounding spheres, you'll get more positive results.

Which means if you're doing this for frustum culling, for example, then you'll have more objects actually on display than you otherwise might.

It's possible that one might be faster in some specific cases than the other, depending on what your fine-grained collision detection scheme is and what your world is like. And it depends on what other schemes you have in play (binning of objects, etc). But it's certainly not something you can say is true in all cases.

Would a bounding ellipse be practical for broad phase calculations also, since it would better represent long, skinny shapes?

No. Ellipses require far too many computations for intersection tests. You may as well use an AABB.

Answer 2

Answering your questions in order:

1. AABBs are used an accurate, low cost collision test which fits most models without a high set up cost.

2. Whilst it can not be denied Bounding spheres can be a great pre-cursor to further collision tests, they are by no means the holy grail. In almost all cases except for a mostly spherical object, the bounding sphere will almost always cover more area (ie sub-optimal) than a bounding box.

Some good reading material: http://www.gamedev.net/topic/216295-bounding-box-or-bounding-sphere/

For tight bounding spheres, have a look at: http://en.wikipedia.org/wiki/Smallest_circle_problem

Answer 3

If the highest precision needed is just loose collision detection (and not point) then go ahead with sphere or ellipse. If higher precision needed, then you need the axis aligned, for although it doesn't make any difference for circle/sphere, it does when the higher precision collision algorithms kick in. A mesh can have holes and such features that may affect the collision (liquid for example) and the only way to get to that place/data is having an axis bound to the physics mesh, as it translates perfectly to the mesh data which uses that too.