Collisions in a real world application.

Question

Here's my problem. I'm creating a game and I'm wondering about how to do the collisions. I have several case to analyze and to find the best solution for.

I'll say it beforehand, I'm not using any third party physics library, but I'm gonna do it in house. (as this is an educational project, I don't have schedules and I want to learn)

I have 2 types of mesh for which I have to make the collisions for :

1) Static Meshes (that move around the screen, but does not have ANY animation)

2) Skinned/Boned Meshes (animated)

Actually I have this solution (quite hacky :|)

First of all I have a test against some bounding volume that enclose the full mesh (capsule in my case), after :

1) For the static meshes I divide them manually in blocks (on the modeler) and for each of these blocks i use a sphere/AABB test. (works fine, but its a little messy to slice every mesh :P) (i tried an automatic system to divide the mesh through planes, but it gives bad results :()

2) For the animated mesh ATM i'm dividing the mesh at runtime into x blocks (where x is the number of bones). Each block contain the vertex for which that bone is the major influencer. (Sometimes works, sometimes gives really bad results. :|)

Please note that the divide of the mesh is done at loading time and not each time (otherwise it would run like a slideshow :D)

And here's the question :

What is the most sane idea to use for those 2 case? Any material for me to study these methods? (with some sourcecode and explanations would be even better (language is not important, when i understand the algorithm, the implementation is easy)) Can you argument why that solution is better than others? I heard a lot of talk about kd-tree, octree, etc..while I understand their structure I miss their utility in a collision detection scenario.

Thanks a lot for the answers!!!

EDIT : Trying to find a K-Dop example with some explanation on the net. Still haven't found anything. :( Any clues? I'm interested on HOW the K-Dop can be efficiently tested with other type of bounding volumes etc...but the documentation on the net seems highly lacking. :(

Answer 1

Prior to doing complex collision detection you should perform basic detection.

Using spheres or rectangles as bounding volumes is your best bet. Then if this detects a collision, move onto your more complex methods.

What I'm getting at is simple is often better, and quicker. Wrapping bounding volumes and splitting meshes up is costly, not to mention complex. You seem to be on the right track though.

As with game programming there are multiple ways of collision detection. My advice would be start simple. Take a cube and perfect your routines on that, then in theory you should be able to use any other model. As for examples I'd check gamedev.net as they have some nice articles. Much or my home made collision detection is a combination of many methods, so I can't really recommended the definitive resource.

Answer 2

The answering question comes down to how precise do you need?

Clearly, sphere bounding boxes are the most trivial. On the other side of the scale, you have a full triangle mesh-mesh collision detection, which has to happen each time an object moves.

Game development physics engine rely on the art of the approximation(I lurked in GameDev.net's math and physics forums years ago).

My opinion is that you will need some sort of bounding ellipsoid associated with each object. An object can be a general multimesh object, a mesh, or a submesh mesh. This should provide a 'decent' amount of approximation.

Answer 3

Pick up Christer Ericson's book, Real-Time Collision Detection. He discusses these very issues in great detail.

When reading articles, remember that in a real-world game application you will be working under hard limits of memory and time - you get 16.6ms per frame and that's it! So be cautious of any article or paper that doesn't seriously discuss the memory and CPU footprint of its algorithm.

Answer 4

The most common approaches used in many current AAA games is "k-DOP" simplified collision for StaticMeshes, and a simplified physical body representation for the SkeletalMeshes.

If you google for "kDOP collision" or "discrete orientation polytopes" you should find enough references. This is basicly a bounding volume defined of several planes that are moved from outside towards the mesh, until a triangle collision occurs. The "k" in kDOP defines how much of these planes are used, and depending on your geometry and your "k" you will get really good approximations with this.

For SkeletalMeshes the most commen technique ist to define simple geometry that is attached to specific bones. This geometry might be a box or a sphere. This collision-model than can be used for quite accurate collision detection of animated meshes.

If you need per-triangle collision, the "Seperating Axis Theorem" is the google-search term of your choice. This is usefull for specific cases, but 75% of your collision-detection needs should be covered with the above mentioned methods.

Keep in mind, that you most probably will need a higher level of early collision rejection than a bounding-volume. As soon as you have a lot of objects in the world, you will need to use a "spatial partitioning" to reject groups of objects from further testing as early as possible.