Vehicle/Rigid Collision Fixes
by Ross Pawley · in Torque Game Engine · 06/11/2007 (10:23 pm) · 115 replies
Hey everyone, I just wanted to post these early fixes to the frequent and frustrating vehicle collision problems people have had with TGE. We spent a few hours today at the office going through things and this new code works relatively well with some small issues, mainly interpenetration. However, it's a far sight better than what was there, which was just calling into the collision routine for immobile ridgid objects (and thus unsuitable for vehicles entirely).
In rigid.cpp replace these functions:
(CONTINUED)
In rigid.cpp replace these functions:
bool Rigid::resolveCollision(const Point3F& p, Point3F normal, Rigid* rigid)
{
atRest = false;
Point3F v1,v2,r1,r2;
getOriginVector(p,&r1);
getVelocity(r1,&v1);
rigid->getOriginVector(p,&r2);
rigid->getVelocity(r2,&v2);
// Make sure they are converging
F32 nv = mDot(v1,normal);
nv -= mDot(v2,normal);
if (nv > -0.001f)
return false;
// Compute impulse
F32 d, n = -nv * (1 + restitution * rigid->restitution);
Point3F a1,b1,c1;
mCross(r1,normal,&a1);
invWorldInertia.mulV(a1,&b1);
mCross(b1,r1,&c1);
Point3F a2,b2,c2;
mCross(r2,normal,&a2);
rigid->invWorldInertia.mulV(a2,&b2);
mCross(b2,r2,&c2);
Point3F c3 = c1 + c2;
d = oneOverMass + rigid->oneOverMass + mDot(c3,normal);
Point3F impulse = normal * (n / d);
applyImpulse(r1,impulse);
impulse.neg();
rigid->applyImpulse(r2,impulse);
return true;
}
bool Rigid::resolveCollision(const Point3F& p, Point3F normal)
{
atRest = false;
Point3F v,r;
getOriginVector(p,&r);
getVelocity(r,&v);
F32 n = -mDot(v,normal);
if ( n < 0 )
return false;
// Collision impulse, straight forward force stuff.
F32 d = getZeroImpulse(r,normal);
F32 j = n * (1 + restitution) * d;
Point3F impulse = normal * j;
// Friction impulse, calculated as a function of the
// amount of force it would take to stop the motion
// perpendicular to the normal.
Point3F uv = v + (normal * n);
F32 ul = uv.len();
if (ul) {
uv /= -ul;
F32 u = ul * getZeroImpulse(r,uv);
j *= friction;
if (u > j)
u = j;
impulse += uv * u;
}
//
applyImpulse(r,impulse);
return true;
}(CONTINUED)
#62
11/01/2007 (10:42 pm)
Well Ross, while that is disheartening, it is not at all surprising. It has long been a source of trouble for those wanting to use this engine for vehicles only to find out its collision system is not up to the task for any extensive and reliable vehicle collision simulations. 
#63
We definitely did do a lot of tweaks, and I'd like to do a paper on them sometime in the before early next year (when I have the time!) if you guys feel as though our end results are something that you would like to achieve
If however you think that they are crap, then I wont bother ;)
11/01/2007 (10:51 pm)
Seeing that our game, MINI#37 Arcade Racer is now LIVE (and FREE to download and play!!!), you can register and download it from www.mini37.com and try it out to see the acceptable collision reactions.We definitely did do a lot of tweaks, and I'd like to do a paper on them sometime in the before early next year (when I have the time!) if you guys feel as though our end results are something that you would like to achieve
If however you think that they are crap, then I wont bother ;)
#64
To see what I mean, you might go grab the PhysX SDK and run their CCD demo that has a walled in room and a stack of rectangles. It has a key mapped to applying a huge force to the stack, with a toggle for CCD on and CCD off.
I'd wager that implementing a decent CCD algorithm wouldn't take *that* long, probably a couple of weeks, most of which would be figuring out how the current stuff works in order to integrate it. If you need a hard and fast solution and can't or don't want to implement a custom one yourself, I'd say definitely grab the PhysX resource and use an actor for your vehicles, or test out the polysoup stuff with what's in there at the moment (you'll of course want to put in our change mentioned above that applies an equal and opposite force to whatever object was hit, and possibly take out the while() loop altogether (we tested with and without it, and it seems pretty decent without)).
11/01/2007 (11:00 pm)
*Shrug* It's somewhat to be expected though. It is a rather game specific sort of feature. Truth be told, the collision *detection* is rather good as it is. The response? Not so much. Essentially it's just the same as the player collision response. It can definitely be tweaked to handle high speed collisions between vehicles *reasonably* well, but impulse methods really really aren't suited to them. To see what I mean, you might go grab the PhysX SDK and run their CCD demo that has a walled in room and a stack of rectangles. It has a key mapped to applying a huge force to the stack, with a toggle for CCD on and CCD off.
I'd wager that implementing a decent CCD algorithm wouldn't take *that* long, probably a couple of weeks, most of which would be figuring out how the current stuff works in order to integrate it. If you need a hard and fast solution and can't or don't want to implement a custom one yourself, I'd say definitely grab the PhysX resource and use an actor for your vehicles, or test out the polysoup stuff with what's in there at the moment (you'll of course want to put in our change mentioned above that applies an equal and opposite force to whatever object was hit, and possibly take out the while() loop altogether (we tested with and without it, and it seems pretty decent without)).
#65
FYI, in our stuff we barely modified the impulse collision response and our big wins were from re-doing the collision detection to not use (kinda polysoup-ish) TGEs standard methods (the big problems with it were always caused by the distance infront/behind of a plane for inter-penetrations), as well as making adjustments to the client/server logic by removing client-side collisions and tweaking some interpolation methods.
11/01/2007 (11:05 pm)
@Ross:FYI, in our stuff we barely modified the impulse collision response and our big wins were from re-doing the collision detection to not use (kinda polysoup-ish) TGEs standard methods (the big problems with it were always caused by the distance infront/behind of a plane for inter-penetrations), as well as making adjustments to the client/server logic by removing client-side collisions and tweaking some interpolation methods.
#66
11/02/2007 (5:29 am)
In case it helps, we have a method for reproducing the ResolveCollisions infinite loop lock. Making the "lateralRestitution" something crazy (like 25.0f) it always happens. It seems that the algorithm doesn't handle the extreme cases correctly.
#67
11/02/2007 (7:04 am)
@Luke, yeah we had some luck increasing various parameters as well, but nothing that we couldn't arbitrarily set up a case for that would fail.
#68
11/02/2007 (7:08 am)
In case it helps, we have a method for reproducing the ResolveCollisions infinite loop lock. Making the "lateralRestitution" something crazy (like 25.0f) it always happens. It seems that the algorithm doesn't handle the extreme cases correctly.
#69
11/02/2007 (10:30 am)
Luke I would really like to see those tweaks. BTW your game looks sweet. I am gonna try it later today.
#70
11/02/2007 (2:18 pm)
@Ross Pawley: You can use polysoup collision for vehicles? Ie. for the vehicle itself?
#71
11/02/2007 (2:31 pm)
@Lee, I don't know exactly how the polysoup stuff is set up, but it works on DTS, I believe, so I imagine you could do it.
#72
Any ideas?
11/03/2007 (1:45 pm)
Well I have managed to tweak my settings and have pretty much perfect collisions with one exception that perhaps one of you can explain. Occasionally, when two vehicles collide, I get a massive processing load that causes the game to freeze.Any ideas?
#73
11/03/2007 (2:33 pm)
@Ron, that's the outer while() loop in ResolveCollisions. As I noted before, not having it at all seems to give about the same results.
#74
I was curious about that one myself other than being used for delaying time a bit, it doesn't seem to serrve any purpose.
Also how did you remove it? as far as I can see the code gets a bit hairy if you do.
11/03/2007 (3:13 pm)
Are you referring to while (colliding);?I was curious about that one myself other than being used for delaying time a bit, it doesn't seem to serrve any purpose.
Also how did you remove it? as far as I can see the code gets a bit hairy if you do.
#75
11/03/2007 (4:43 pm)
Yeah, that's the one. And um, you don't have to do anything special to remove it. Just comment it out. It will still run through one for loop of all the gathered collisions.
#76
I just had to remember my basic coding. SHEESH!
Thanks Ross.
11/03/2007 (4:43 pm)
Yeah I just got it done. It totally fixed my problem. My collisions work pretty good now.I just had to remember my basic coding. SHEESH!
Thanks Ross.
#77
More seriously (but not much more), I thought I'd answer Ross' suggestion about using polysoup vs. polysoup collision to improve results. Well, you can't do that with vehicles out of the box, so I did the second best thing (I presume) and just created a very high poly collision mesh.
Here's before:
and after
Now you might be asking yourself, "what the hell, is that a fish?", the answer is yes, as below:
I've made a small (18mb) but hi res and self serving video showing what's going on:
www.singularityfps.com/images/fish.avi
As you can see, in my project I've got a lot more collision between vehicle bodies and other shapes going on than in most games, due to it's nature. Most games where you fly you're, like, in the sky and stuff. In mine you're in a crowded room. I think that's fun, but it's probably also why I'm suffering so badly.
Anyway, I wanted to explain that so you'd understand my testing methodology :-). I simply timed how long the fish could wander without the game locking up. The AI takes very curvy paths, and the fish are large in relation to their environment, so there's all kinds of collision going on with the plants and the rocks and the walls of the tank.
Anyway, with the simpler collision mesh, they averaged right at about 5 minutes (in 5 tries). I replaced the fish with the higher poly collision mesh and they all locked up within a minute.
I know it isn't as scientific as one might like, but the fact is that with the higher mesh fish, it came close to locking up a _lot_ more often--the difference was obvious. I'm referring to framerate dropping to 1-2fps for several seconds, before getting back to normal.
It appears more vertexes means more opportunities to fail, and not more data to prevent failure. And that's what I thought might be useful knowledge.
11/05/2007 (12:16 am)
I've got a big six pack of beer for whoever can really nail this one. Literally, it's huge, it fills my master bedroom. Feel free to contact me to make arrangements for transport of said cerveza to your domecile or place of business!More seriously (but not much more), I thought I'd answer Ross' suggestion about using polysoup vs. polysoup collision to improve results. Well, you can't do that with vehicles out of the box, so I did the second best thing (I presume) and just created a very high poly collision mesh.
Here's before:
and after
Now you might be asking yourself, "what the hell, is that a fish?", the answer is yes, as below:
I've made a small (18mb) but hi res and self serving video showing what's going on:
www.singularityfps.com/images/fish.avi
As you can see, in my project I've got a lot more collision between vehicle bodies and other shapes going on than in most games, due to it's nature. Most games where you fly you're, like, in the sky and stuff. In mine you're in a crowded room. I think that's fun, but it's probably also why I'm suffering so badly.
Anyway, I wanted to explain that so you'd understand my testing methodology :-). I simply timed how long the fish could wander without the game locking up. The AI takes very curvy paths, and the fish are large in relation to their environment, so there's all kinds of collision going on with the plants and the rocks and the walls of the tank.
Anyway, with the simpler collision mesh, they averaged right at about 5 minutes (in 5 tries). I replaced the fish with the higher poly collision mesh and they all locked up within a minute.
I know it isn't as scientific as one might like, but the fact is that with the higher mesh fish, it came close to locking up a _lot_ more often--the difference was obvious. I'm referring to framerate dropping to 1-2fps for several seconds, before getting back to normal.
It appears more vertexes means more opportunities to fail, and not more data to prevent failure. And that's what I thought might be useful knowledge.
#78
11/05/2007 (6:42 am)
@Lee, did you already remove the while( collliding ) loop from the ResolveCollision function in the Vehicle class? That is 100% the cause of lockups, and will definitely be more frequent and worse the more collisions it gathers (i.e., more detailed collision mesh). As I noted a couple of times before, it really doesn't provide enough of a benefit to warrant the possibility of it crapping out or crashing the game altogether, and the results without it are pretty much damn near identical. Go ahead and give it a try (just comment the while( colliding ) { and the end } out and you're good, it will still go through all of the collisions it generated at least once).
#79
The occasional interpenetration is a small price to pay for no lockups.
Incidentally, the high poly collision meshes are much more disposed to interpenetrate.
11/05/2007 (7:31 pm)
@Ross: MUCH better! Woot! Sorry, I must have misunderstood some of the conversation about that. Yep, lockup free--thanks! BTW one must comment out the "do" at the beginning too, right? The occasional interpenetration is a small price to pay for no lockups.
Incidentally, the high poly collision meshes are much more disposed to interpenetrate.
#80
Also, it's not really about having more polygons, it's about where they are and their vertices and edges. It should be pretty easy to have the polysoup stuff work on the vehicles, since they do with regular DTS anyway. I definitely suggest looking at extending that to work with vehicles. It will definitely give you a different result than just a higher poly collision mesh. To test you could always add a polysoup static fish, and collide your regular one into it to see what I mean (put a breakpoint on resolvecollisions and it will likely have ~60+ collision details generated.)
11/05/2007 (8:34 pm)
@Lee, I guess it is a do { } while() loop, so yeah. The reason that would lock up is because it'd fail to resolve the collision on the next loop, and after that the impulses it gets are infinitesimal so it won't ever complete. You'll also notice that you don't get massive slowdowns on each collision.Also, it's not really about having more polygons, it's about where they are and their vertices and edges. It should be pretty easy to have the polysoup stuff work on the vehicles, since they do with regular DTS anyway. I definitely suggest looking at extending that to work with vehicles. It will definitely give you a different result than just a higher poly collision mesh. To test you could always add a polysoup static fish, and collide your regular one into it to see what I mean (put a breakpoint on resolvecollisions and it will likely have ~60+ collision details generated.)
Associate Ross Pawley
My personal feeling is that the algorithm that the code is based on (Baraff's) simply isn't meant for vehicle collisions. If you take a look at his paper, you can see what I mean (in the introduction to the algorithm he states some conditions where it will fail, such as with identically sized cubes sitting on top of eachother....in that case, there's no vertex-face collisions and no edge-edge collisions detected, so they'd just fall through. Now, granted it might be hard to get them set up in exactly such a stack, but it illustrates my point).
For high speed collision detection and response of the type most commonly seen in vehicle sims, you really need a continuous collision detection and response routine. Impulse methods usually just don't cut it, since the algorithms don't really care about inter-penetrations, and by that time you would have to have a larger impulse generated to resolve them anyway (we tried a number of things along this route, but basically, our results pointed to the fact that you can't easily come up with an analytical solution for figuring out when to apply such things and not have it affect normal collisions).
If your game relies heavily on such things, I suggest basically taking the routines that are used for this in stock Torque and writing your own to use a CCD method, or implementing a physics library like PhysX which already has CCD and the like.
@Lee, we noticed in our testing that collisions against polysoup objects were somewhat more reliable, since they generate a *lot* more edge-edge and vertex-face collision detections than with DIFs or collision hulls of regular DTS. So you guys might have more luck making your vehicles use polysoup and just not using a collision hull.