XNA: Perform Collision Detection Against 3D Scene Geometry

Question

How would one perform collision detection between a simple scene like the one below and a simple object like a sphere?

I assume the best solution would involve convex hulls in some way but I have no idea how that works (still learning :)

Answer 1

If the terrain is fixed you can do some precalculations to cut down on the problem size. For example, for each sector (pick reasonable sizes to work with) you can define a guaranteed-clear altitude. Each object also has a maximum object height variable.

If the object position - object height is greater than the known safe altitude then no further checks need to be done. This won't do anything about your worst time but if you have a lot of moving objects that are mostly clear of the terrain then it will do a lot for your average time.

Answer 2

For simple scenes, use an aggregate of geometric primitives for collision testing. Your example can be broken down into a finite plane, box and rectangular prism. Since the only object interacting is a single sphere, your testing can be kept very simple. If your scene is considerably larger, an quadtree or octree approach to organizing collision shapes is sufficient enough and can ensure that you only test what is close to the sphere.

Convex hulls would apply to the moving sphere, for representing the space that the sphere moves within a given time frame. This space is best envisioned as a short capsule with round ends. For collision detection, you can break this into one cylinder and two half-spheres and test for those.

Going back to the quadtree, you will first recursively check which leaves/nodes the capsule shape is occupying, not the sphere (capsule-box intersection). Then iterate through the collision shapes that are in them and do a test case for each.

It's probably not the most efficient method for collision checking (sweep and prune handle many more scenarios) but for one sphere this is good enough.

Answer 3

I use Mogre3D, but I think this could work in XNA as well.

Use a raycast that is cast downward, check where the ray hits the poly or face so that your character does not fall through the level.

Don't start the ray for very high, just something above your character, so the character can still walk under a bridge or something.

If you are using high detailed scenes, try creating a very low poly mesh that you can use with your ray, so that the performance is improved greatly.

Then for doodads, or scene objects, use a collision sphere, some kind of fixed radius or bounding box when running around your character.

For speeding up the loading of your game, you could already pre-calculate the triangles of the scene mesh.

Hope this helps.

T.