PDA

View Full Version : OT: Sphere-Box intersection algorithm



Humus
09-02-2002, 09:25 AM
Sorry for the slightly off-topic question.

I need a (decently) simple algoritm for finding whether a sphere intersects an axis-aligned box. The algoritm should return true if the sphere a little as touches the box. At first I thought this was an easy problem, but after trying to find a simple solution myself and then googleing like mad over it I still haven't found a good solution. The only solution I can come up with right now is to check for intersection on all 6 planes and all 12 lines.

Do anyone have a better solution?

LaBasX2
09-02-2002, 09:35 AM
You can calculate the plane equation for every box side (pretty cheap for a box since you don't really need to calculate it) and check the distance of the sphere's radius to every plane. If the distance is somewhere greater than the radius, there is no collision. But make sure that your normals are all pointing out of the box!

LaBasX2

Humus
09-02-2002, 10:07 AM
Thanks for your reply, but that's not a complete solution. I need it to return false even in a situation like this (http://esprit.campus.luth.se/~humus/temp/intersect.png) .

LaBasX2
09-02-2002, 11:26 AM
Hmm....you're right, that won't work in that case. I always though that test were safe for convex objects but probably only as a point in brush test, not sphere in brush test...

If you've done a google search, you've probably also found that Gamasutra article about collision detection. I haven't tested it but it is looking quite interesting: http://www.gamasutra.com/features/19991018/Gomez_4.htm

LaBasX2

PH
09-02-2002, 11:41 AM
That's the algorithm I use. It's pretty much identicle to the one in Graphics Gems. It handles all special cases ( including Humus' ), sphere completely inside box and sphere enclosing entire box.

Humus
09-02-2002, 01:02 PM
Ah! Thanks, that's exactly what I need. So simple and easy to understand once you see it. http://www.opengl.org/discussion_boards/ubb/smile.gif
(I had to redo the search to see if I got that one or if I just used a bad search string. Sure, I did get that one too, quite early too. Not sure why I passed it by, probably because of that AABB abbreviation that looked like something completely different at first. I just now understood what it means, Axis-Aligned Bounding Box)

zed
09-02-2002, 06:55 PM
realtimerendering website have a page with a table which lists a LOT of various intersection tests.
also sphere->AABB can be found at dave eberly's site

davepermen
09-02-2002, 09:33 PM
hehe, that code snipped is CUTE! http://www.opengl.org/discussion_boards/ubb/biggrin.gif
my version would involve checking against the points, against the egdes, against the faces, etc.. HEHE http://www.opengl.org/discussion_boards/ubb/biggrin.gif

well then, i _think_ that one could be a _bit_ faster http://www.opengl.org/discussion_boards/ubb/biggrin.gif