Collision detection

#1 Lol, good luck :D Ive been messing with the terrain collision and I can say that it sucks... badly.

#2 Cheers :)

So can you point me at where all the collision is happening? I guess terrain collision might be near dts collison...

#3 Basic break down of collision in TGE as I have come to understand it:

You have two types of colliders in TGE: active and passive.

The active colliders are the ones who initiate collisions while the passive colliders just return their collision information for the active colliders to use how they see fit. Active colliders will often also act as passive colliders for other active colliders (did that make sense?)

In general, your moving objects like the player, vehicle, or item are your active colliders. At some point in their processTick() or in a function that is called by processTick() they will make a call to the scenegraph to update their working collision set.

What happens at this point is that the scenegraph will loop through all of the objects in the same bin (read Melv's description of bins) as the active collider and check to see if their bounding boxes overlap (this is where it also checks the collision masks vs the object types). If their bounding boxes overlap then buildConvex() is called for each object.

Inside buildConvex() is where each sceneobject decides how to represent themselves to the rest of the objects. In order for collision to occur against an object it must register at least one convex with the working list. Once this convex is registered all of the rest of the collision code acts against it and never directly against the original sceneobject. A convex itself doesn't store any vertex/edge/face information and really can't ever return any meaningful collision information which is why you almost always see a subclass of Convex created for each sceneobject (InteriorConvex, ShapeBaseConvex, TerrainConvex, etc.)

These subclasses use a pointer back to the original sceneobject (Convex::mObject or a separate pointer in the subclass) to pull meaningful collision information for the functions getPolyList(), support(), and getFeatures(). They also often include a unique id that allows them to pull only a subset of the information from the original. For example, InteriorConvex::hullId allows getPolyList() to only pull the polys for a specific brush instead of *all* the polys in the interior. Most objects are going to be complex enough to require more than one convex to represent it. It is also beneficial to be able to split up the object into smaller convexes simply so that the active collider doesn't have to collide against too many unrelated polys (like those on the other side of the level). There is a point of diminishing return though where you lose speed from having too many convexes as opposed to testing against too many unrelated polys. I found for practical purposes, going smaller/fine-grained than about half the size of the player object was actually slower.

Once the scene has been traversed and all of the relavent convexes have been registered with the working list for our active collider, it is time for it to do some actual collisions. TGE uses the GJK convex-to-convex algorithim for collision calculations. I won't go into detail here about that algorithim partly b/c I am still a little fuzzy on it and partly b/c it would take too long (search Resources for GJK to read the articles Tim posted on it). However, I can tell you the functions you will need to implement and what they do:

- Continued -

#4 - Continued -

getPolyList() - this is the biggy for player collisions. You are given a box to test against and a pointer to a AbstractPolyList to add polys to. Basically, just add any polys in your convex/sceneobject that are inside the box to the AbstractPolyList. You can also make use of the isInterestedInPlane() function to make sure that you only hand in "forward" facing polys to the list. Don't forget to transform the box from world space into your object space for testing.

support() - this is a pretty simple function. Simply return the furthest point from the point handed in. Easiest way to do this is to loop through all the points and return the one where the dot product is the greatest.

getFeatures() - I still haven't quite gotten my version of this function working but from what I understand you are handed in a transform matrix, a normal, and a pointer to a ConvexFeature structure to fill out. You add all of the points (transformed), faces, and edges of your convex object to the ConvexFeature structure. These are used for vertex-to-face and edge-to-edge collisions later.

Once the active collider has the collision information it is pretty much up to them on how to use it whether in some kind of physics simulation or something else entirely.

I should also quickly mention castRay() since it is related to collision. This is the line-of-sight function that gets used for stuff like projectiles and fxSun. You are given a starting point and an ending point and are expected to fill out a RayInfo structure with information about the collision like the distance along that line (between 0.0 and 1.0) of where a collision occurred. This does get used for the wheel extensions in wheeledVehicle so it is wise to implement it for your sceneobject.

Well, that is TGE collision in a nut shell. If you poke through the various Convex subclasses you can see decent examples of how to implement all of this. boxConvex was particularily helpful to me when I was getting started though it has some optimizations that make it hard to read in places. At some point in the near future I plan to release a nice clean example of a collidable sceneobject. I think I may flesh out this post a little more and post it as a resource soon also.

I wanted to clarify one thing:
For collision you need to implement buildConvex() and castRay() for your sceneobject and getPolyList(), support(), and getFeatures() for your Convex subclass. I just wanted to make it clear which went where.

#5 Thankyou very, very much for such a clear and detailed post.

I want to have more detailed collision for my Player object: several boxes rather than one convex mesh. I guess I'll make a child of the Player class and re-write the above functions. Any comments on this?

Ian

#6 Excellent little write up Mathew...
Btw, I'd like to talk with you about your answer on IRC yesterday (ie you had left when I saw it ;))
You can reach me at the email on my profile, etc.

#7 Ian,

IIRC the player model can use up to 9 different collision meshes in combination

#8 Thanks for this info matt. Very interesting. Please do post as a resource. I'm running out of bookmark slots!

Phil.

#9 Thanks again Matt, but 9 isn't enough :( Oh well, I'm sure I can increase that figure anyway.

#10 I am already working on fleshing this out into a resource =) I'd like to include some more details about how GJK works and how objects use the returned collision information (like the player and the vehicle classes). I also want to run this by Tim a bit to make sure I am on track.

Ian,
It is probably trivial to increase the limit from 9 but you might start to suffer a performance hit.

#11 Very cool Matt, I've also posted this in our snippit DB (I'm still the only one posting there btw. *hint hint* :P)

#12 You should check out the resources posted by Josh Albrecht, dealing with extending player collision. I don't know if its what you are going for, but it might help.

http://www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=3374

#13 Hey again.

I read Matt's post which has given me some insight into the collision system, and what I want to do sounds like it should be quite simple (registering several convexes with the collider list rather than one for my player class) but I can't see where to do it.

I want to have a more complex collision mesh for my player class. Basically, I want to define a number of boxes, one for each hand, one for each lower arm, one for each upper arm, one for the head etc etc. I don't just want to collide projectiles against these (as is explained in Josh's resources) I want to collide against the difs and dts' like this too. I know there will be a performance hit, but I'm not worried about that at the moment.

I don't want to export a collision mesh (or 9) from Milkshape, defining the boxes by hand in a text file is fine.

Any more help would be really, really appreciated. I'm banging my head against the wall with this low level coding.

Ian

#14 You would have to do it in the processTick (or one of the methods called form there) in the Player class. You would most probably have to rewrite the collision code for the Player and make its register a few BoxConvex objects instead of the dts collision convex.

Dylan