Imagine a ray (described as a vector) enters a cube with a sphere in it (the diameter of the sphere is the width of the cube), what is the quickest way to find out of the ray will go through the sphere, or leave the cube without ever touching the sphere? [edited by - lode on November 17, 2002 6:25:18 AM]

I don''t think that you can use the fact that it enters a cube to speed up the process.

To check if it intersects the sphere, simply compare the distance between the ray and the center of the sphere. Depending on the distance formula, you might be able to speed it up by comparing the squared distance.

Cédric

Cedric brings up an excellent point here: The ray is like a parameterized line (vector equation for a line), and using the resultant of the distance formula will most definitely be a sure way of determining whether the sphere is intersected. The ray will intersect the sphere if and only if the center lies within a radius of the line. I don''t remember the 3d distance formula for a point to a line, but I am sure that you can google it quickly. Just a question. Why was the sphere ever in a "bounding" box in the first place? You might want to reconsider whatever you are doing, because it will surely be slower to use the box. You have to first find where it intersects, use the angle information, and then figure out if it will go through the sphere, which is about 5 times as many computations right away. Use the dist. formula.
Brendan

What if it was not a perfect sphere, though. Say it was just a bunch of polygons. What are the ways used to figure out if it interesects or not, and if this is the system games use (figuring out if each bullet shot intersects with any polygons, wouldn''t it take up a lot of cpu for just that simple task?

Short answer:
Yes, it eats up a lot of CPU time to calculate that.

Long answer:
To speed up things you can always use a hirachical version of collision check, relying the higher checks will reject a collision has happened.
In GPG1 (i think it was 1) they suggested you first find a sphere surounding your complete object.
If you do not hit the sphere, you do not hit your object at all.
After that you still have to check where your object has been hit (or if your ray simply came close, but didn''t really hit it).
So place some more spheres, one around each polygon.
Do a collision check with the polygon-spheres. No hit? good.
Was hit? Well, now you have to check the ray versus the polygon in that sphere for a colision...

this should work well, and probably speed things up compared to doing a brute force collision check for each polygon...