Detect Collision point between a mesh and a sphere?

Question

I am writing a physics simulation using Ogre and MOC.

I have a sphere that I shoot from the camera's position and it travels in the direction the camera is facing by using the camera's forward vector.

I would like to know how I can detect the point of collision between my sphere and another mesh.

How would I be able to check for a collision point between the two meshes using MOC or OGRE?

Update: Should have mentioned this earlier. I am unable to use a 3rd party physics library as we I need to develop this myself (uni project).

Answer 1

Hi, I think the best would be to use a specialized physics library.

That said. If I think about this problem, I would suspect that it's not that hard:

The sphere has a midpoint and a radius. For every point in the mesh do the following:

1. check if the point lies inside the sphere.
2. if it does check if it is closer to the center than the previously found point(if any)
3. if it does... store this point as the collision point

Of course, this routine will be fairly slow. A few things to speed it up:

1. for a first trivial reject, first see if the bounding sphere of the mesh collides
2. don't calc the squareroots when checking distances... use the squared lengths instead.(much faster)
3. Instead of comparing every point of the mesh, use a dimensional space division algorithm (quadtree / BSP)for the mesh to quickly rule out groups of points

Ah... and this routine only works if the sphere doesn't travel too fast (relative to the mesh). If it would travel very fast, and you sample it X times per second, chances are the sphere would have flown right through the mesh without every colliding. To overcome this, you must use 'swept volumes' which basically makes your sphere into a tube. Making the math exponentially complicated.

Answer 2

The accepted solution here flat out doesn't work. It will only even sort of work if the mesh density is generally high enough that no two points on the mesh are farther apart than the diameter of your collision sphere. Imagine a tiny sphere launched at short range on a random vector at a huuuge cube mesh. The cube mesh only has 8 verts. What are the odds that the cube is actually going to hit one of those 8 verts?

This really needs to be done with per-polygon collision. You need to be able to check intersection of polygon and a sphere (and additionally a cylinder if you want to avoid tunneling like reinier mentioned). There are quite a few resources for this online and in book form, but http://www.realtimerendering.com/intersections.html might be a useful starting point.

The comments about optimization are good. Early out opportunities (perhaps a quick check against a bounding sphere or an axis aligned bounding volume for the mesh) are essential. Even once you've determined that you're inside a bounding volume, it would probably be a good idea to be able to weed out unlikely polygons (too far away, facing the wrong direction, etc.) from the list of potential candidates.