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 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 many of these planes are used, and depending on your geometry and your "k" you can get really good approximations.

For SkeletalMeshes the most common technique is 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 "Separating 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.