collision detection algorithms

[patrick]

implement some algorithms to check for collisions between all objects and also between the ground. There are types of known solutions to this problem. try to read about them all and implement an algorithm that makes most sense for orxonox.

[patrick]

Object - Object Collision Detection

Works now, i've implemented it using obbs

Object - Terrain Collision Detection

Work in progress: The idea is to define pillars/wheels on which the object stands on. The object itself is abstracted as an OBB, I will use the 1st level obb of the object. There is no deeper (finer) CD with the Model itself, I don't think that it will be necessary nor utile.

To get the trianges, on which the wheel/pillar is standing, there needs to be some terrain separating algorithms. Height maps separate themselfs by default in regions, obj's will have to do this manualy.

To split the terrain manualy, it seems to be a good idea to split the terrain using barycentric coordinate representation. the idea is to parameterize space in terms of a set of points and their associated weights. A good resource on "point in triangle" thematics is applicable on ​blackpawn more o nthe barycentric coordinate representation and how to use the cross product ​on gamedev.

Now we know how to find out if one point is inside a triangle. But do we have to check all triangles in the terrain? The answer for this stupid question is of course "no". We partition the terrain into quadtrees ​gamedev forum and ​gamedev article this will be sufficient for CD performance and will also be easily enhanced to support frustum culling algorithms. LOD can be implemented later on as well (​monstrous terrain article)

[patrick]

Object - Terrain Collision Detection

Some more ideas on how to test collisions with the ground:

1. find out in which quadtree the object is
2. find out if the object is over/under the maxheight of the terrain in this quadtree
3. if below maxheight→collision possible so check for collision with each of the triangles

There is probably some speedup possible in not checking with all triangles in a given quadtree

[patrick]

Speed Improvements

I just thought about some speed improvements in the collision detection system:

• Size of object matters: the obb-tree depth can be adjusted to the object size: big objects have a greater depth to resolve collisions more precisely. This arises the need for asymmetric tree depth checks
• First bv-tree instance should be a bounding sphere