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. :(

Pegg

Answer 1

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.

Euterpe

Nice answer. A lot of things to look up to. Tomorrow I'll give a good search and some work to implement them and report more on this thread. For the moment +1!!! Thanks – Pegg

I'm searching all the net, but still haven't found ONE working example with explanations of K-Dop. There are only lots of theorical paper (pay per view). :| Any clues? :( – Pegg

D-Collide seem to be an open source collision library that implements kDop, so this might be worth a look for an implementation example. d-collide.ematia.de This gamedev.net thread covers a lot of implementation details: gamedev.net/community/forums/… – Euterpe

Answer 2

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.

Helsinki

Obviously i'm first doing a test against a full bounding volume of the mesh (capsule in my case) and after i'm going to the complex that I need to understand and the topic of this question. – Pegg

Answer 3

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.

Astrophotography

I mean, that's ok for simple objects. (a sphere, a capsule, a OOBB, a AABB, an ellipsoid, whatever) If i want to make a collision tree for a complex object (a spaceship or a person) i would need to divide the mesh into multiple pieces. That's the base question. What's the best way to divide the meshes and use them in a system? I Do have my own system so i can move the data as I wish, but i would like to know what's the most common accepted method, so I can't avoid trying useless things. – Pegg

@feal87: I don't know the common/accepted method. But I would generate an ellipsoid in metadata in object creation time for each 'sufficiently interesting' object and it's subobjects, allowing a recursion to refine detail. – Astrophotography

Answer 4

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.

Jareb

Thanks for the suggestion, I will look into it in the future if I can't find anything on the net. – Pegg

+1 For Christer's book. It's an excellent reference and covers more areas than the title implies – Procurable