Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
1  
How would a bounding sphere be less optimal if the model itself is sphere shaped? –  Steve H Nov 26 '11 at 23:12
    
@SteveH I'm taking a stab in the dark here but maybe because the model isn't actually spherical but made up of many small triangles. So, if you were to take a real sphere (i.e. the calculated bounding sphere), it would still have gaps where the triangle edges are flat in-between vertices. Just a thought. –  Richard Marskell - Drackir Nov 26 '11 at 23:41
1  
@Drackir yes, very minimal space there compared to an AABB though. –  Steve H Nov 27 '11 at 0:11
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.