Archived

This topic is now archived and is closed to further replies.

Nathaniel Hammen

Bounding Box or Bounding Sphere??

Recommended Posts

Which is better to enclose a non-moving triangle, if you are using the bounding volume to determine whether the triangle is a possible collider with a moving unit sphere? I could always try each, and then get the framerate, but I''ll ask here first. Right now I am checking the bounding box of the moving sphere against the bounding box of the triangle, but I plan to change that. If I expand the bounding volume of the triangle by one to account for the radius of my sphere, then I only have to use the velocity vector to check against the bounding volume. This will reduce the number of potential colliders, especially in cases where the components of the velocity a nearly equal. I know that calculating a bounding box is faster than calculating a bounding sphere. Intersecting a line with a sphere is faster than intersecting a line with a bounding box, however. So which should I use? -------------------------------------- I am the master of stories..... If only I could just write them down...

Share this post


Link to post
Share on other sites
It really depends what you check against what, how your triangle is sized and also what you prefer: mistakenly reported potential collisions, or prefer better accuracy.

With the information you gave (moving sphere against triangle) and asuming the triangle is like the same size of your sphere, i''d say sphere-to-sphere collision checks are pretty fast and also will give you a good accuracy.

it shouldn''t be that hard to find the center of a sphere with the smalest radius to be the enclosing sphere for your triangle
(I think I''ve seen a algo here on the board).

finally a sphere-sphere collision is REALLY cheap. So my intuition would say go for that.

Share this post


Link to post
Share on other sites
I have seen the algorithm that calculates the smallest sphere enclosing n amount of points. It is called Welzl''s algorithm. However, I have discovered a faster way to do this with only three points. You see, I noticed that in any non-obtuse triangle, the smallest sphere enclosing these three points is the same as the smallest sphere with these three points lying on its surface, which is one of the steps in Welzl''s algorithm. If you only have to do one of the steps, rather than the entire algorithm, it is obviously faster. But I said this was only true for non-obtuse triangles didn''t I? So, what about obtuse triangles? Well, that''s even easier. The center of the smallest sphere will ALWAYS be the midpoint of the edge opposite the obtuse angle, and the radius will ALWAYS be half of the length of that edge. This is also true for right triangles. In fact, both of these methods work with right triangles.

I guess, since I discovered this, I sould use spheres, just so I can use this.

--------------------------------------
I am the master of stories.....
If only I could just write them down...

Share this post


Link to post
Share on other sites
sphere to sphere colision detection is by far the fastest colision detection... its real simple, if the distance between the two objects squared is less than the sum of the radii of the two objects squared then u got colision. Sphere-BoundingBox colision detection is a pain in the ass...

btw, you shouldn''t be recalculating the center point for your triangle sphere every frame (since your triangle is static)... so you don''t need to worry about making that part of the code fast, since you won''t notice any difference.

Share this post


Link to post
Share on other sites
I think AABB to AABB seems to look better for certain things though. With one AABB you can cover a guys pretty good, but you would need a couple of spheres to accurately do it. Sphere are pretty quick and pretty accurate, but it is all about your tests. So if you are doing a 3d person shooter do an AABB (axis aligned bounding box). First person do a sphere. Driving a vehicle do a OBB (oriented bounding box). The problem with mutiple tests is you need mutiple algorithms to find them, but that also isn''t too bad, since 90% of those are online as is.

Share this post


Link to post
Share on other sites
First of all, sorry for waiting so long to reply.

SpaceDude:
I am reluctant to precalculate the bounding volume, because storing it will more than double the amount of memory the terrain is using. I think I will use bounding spheres whether I precalculate or not, since my sphere creation algorithm is so good.

jimmynelson:
The bounding volume in question surrounds one triangle. I already know that I should use an ellipsoid to surround my character (since this is a FPS). The reason I''m asking this is to rule out non-potential colliders, so that I''m not trying to collide my unit sphere with all of the triangles in the scene.

--------------------------------------
I am the master of stories.....
If only I could just write them down...

Share this post


Link to post
Share on other sites
AABox/Sphere can compete with sphere sphere if you compute instant collisions (and not capsules or swept spheres). Since you do not want to precompute the spheres it''s faster like this. However you mentionned that you detect collisions in the context of a terrain. If it''s based on a height map, that is a regular grid, there are more obvious ways to make quick conservative rejections. Just compute the max height under the sphere. Then compute directly triangle sphere with a good routine based on the separating axis theorem.

Share this post


Link to post
Share on other sites