2
\$\begingroup\$

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?

\$\endgroup\$

2 Answers 2

2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
3
  • 1
    \$\begingroup\$ How would a bounding sphere be less optimal if the model itself is sphere shaped? \$\endgroup\$
    – Steve H
    Nov 26, 2011 at 23:12
  • \$\begingroup\$ @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. \$\endgroup\$ Nov 26, 2011 at 23:41
  • 1
    \$\begingroup\$ @Drackir yes, very minimal space there compared to an AABB though. \$\endgroup\$
    – Steve H
    Nov 27, 2011 at 0:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .