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)
#82
PS: So, do I get the beer? :P
11/05/2007 (9:49 pm)
Yeah, in our tests at work, we never really managed to get the car we were using to go through the polysoup terrain.PS: So, do I get the beer? :P
#83
And yes, you earned that beer a long time ago. For the first time in a year and a half of development, my game never, ever locks up. but yeah ok i lied about having a giant six pack in my room. Still, numerous six packs are certainly under your name in my Beer Ledger, should we ever be in a similar geographical location.
Hey, you're in Dallas! My folks live there, and I'm in Houston. I don't see any reason they won't be coming your way quite soon!
11/06/2007 (1:26 am)
Ross: I've been studying the diff between supplied tsStatic.cpp/h with the stock one, with an eye to adapting the polysoup changes to vehicle.cpp/h. Is that the right track? I'm wondering if gamebase might be more appropriate. This whole namespace thing has been kicking my ass.And yes, you earned that beer a long time ago. For the first time in a year and a half of development, my game never, ever locks up. but yeah ok i lied about having a giant six pack in my room. Still, numerous six packs are certainly under your name in my Beer Ledger, should we ever be in a similar geographical location.
Hey, you're in Dallas! My folks live there, and I'm in Houston. I don't see any reason they won't be coming your way quite soon!
#84
As far as the beer, no worries man, I was just continuing the joke :) Besides, it's not truly fixed to not have inter-penetrations, in which case I'd feel worthy of a beer reward. Unfortunately, without a different algorithm, I'm not sure I see that happening. The Baraff method *truly* wasn't mean to be used for vehicles.
11/06/2007 (8:44 am)
@Lee, I haven't really looked at the polysoup stuff myself. I'll give it a quick glance sometime tonight or this weekend and see if I can see an obvious way to get it working with vehicles though.As far as the beer, no worries man, I was just continuing the joke :) Besides, it's not truly fixed to not have inter-penetrations, in which case I'd feel worthy of a beer reward. Unfortunately, without a different algorithm, I'm not sure I see that happening. The Baraff method *truly* wasn't mean to be used for vehicles.
#85
But I could be hallucinating about that.
11/06/2007 (2:00 pm)
Oh, I thought you were saying you had implemented polysoup vehicles already (which is why I asked your advice on how to do it). My regular vehicles are interpenetrating polysoup objects, though, which is now what I think you were saying yours were not doing. It does seem worse if the vehicle has a complex collision mesh, or, if the environemental DTS does NOT have a complex one. That is, they seem to go through meshes that don't have a lot of points more easily.But I could be hallucinating about that.
#86
I also read through Baraff's documentation of the rigid body algorithms which were used for TGE, specifically to compare said algorithms with the actual code found in the vehicle-vs-vehicle collision function, and they're basically spot on (minus the obvious typo at the bottom of the original function). The problem seems to be that, as Ross said, this stuff really was never intended to be used in an application this dynamic. Also, trying to stack crates will quickly prove that, again as Ross mentioned, the algorithm really doesn't like big flat surfaces. For safety, make your crates kind of like chamfer boxes.
In the end, I came up with the same solutions; I implemented the loop hack (using a counter or completely removing the loop), which solved the crashing, but left the failure rate about the same. I collected minor collision detection fixes, which really didn't do much.
As a final attempt to make the physics "playable," as opposed to realistic, I implemented a cheap inter penetration hack, which adds the inter penetration to the velocity of the collision, basically saying, "somehow these two objects are inside each other.. let's pretend they're really *about* to be inside each other due to their velocity and solve that instead." This actually works out for the vehicles, as any collision which doesn't call in time to miss inter penetration simply hits a lot harder. The result is slightly exaggerated collision, but it's still solid enough that you can stack jeeps without them flipping out.
It is worth noting that my tests showed that the physics were far less crash-prone while running off a dedicated server! I'm not sure why this is exactly, but my theory is that running the server and client together in one instance creates some interpolation issues which result in the object creating bizarre collision situations which produce astronomical values of force. Running on a dedicated server, you can see these situations pop up, but the object will immediately snap back to a sane server-dictated position before the client can say "I think this should be fired at the moon."
-------------------------
This is getting kind of long, but there is one area I always meant to look into and never got around to. Baraff explains that you'll need to be able to reset the position of your sim to the exact time the collision would have occurred, and as far as I can tell, this absolutely is not happening. The algorithm has no case for interpenetration, so when it occurs (and it will occur), the objects just stay that close unless an outside force changes the situation. My interpenetration hack is a super-cheap version of this, but it's not mathematically accurate in any way. As I understand it (and it's been a year since I read that stuff), what should happen is:
1) Find the time this collision would have happened at based on already having all the numbers for prediction.
2)If you catch it less than a frame (interpolation frame) too late, predict backwards and use the state from the moment of impact to do the solver work. For simplicity, we're probably actually going to actually snap that object back to said old position. If this is vs. another rigid body, do it for both.
3) Apply the impulse to the object.
4) Sim out the time you "took away" earlier. If you went back 10ms, sim the object forward 10ms based on the new, solved impulse. If vs. another rigid body, do this for both objects. Do it one of two ways:
4a) Just snap it forward like we did before (it was pretty safe to do it before, as we knew the object had just been there and was unlikely to hit anything on the way back). There's a slim chance you'll miss a new collision, but since it happens in less than a frame, the next cycle should be able to handle it the same way. Right? Hmm..
4b) Actually sim it forward to check for any new collisions in that 10 ms. Is there an easy way to sim only one object forward? Can I call its processTick function with a made up amount of time and expect that to work? Do we really need to do this, or is it ok to let the objects hang outside of time for 10ms?
It actually doesn't sound that bad now that I write it out. All you really need to do is store the old pos, rot, and lin/ang velocity from the last interpolation frame and use a percentage of that to do the back-interpolation. Obviously you lose that 15ms (or whatever) in the real game, as the object snaps from about to collide to just collided, but that's perfectly normal, and remember that it occurs at the interpolation rate, which is very fast, generally faster than the player's framerate.
Baraff mentions that you need this, but doesn't include specifics, since it's dependent on your simulation. I could be wrong about the actual process, but the general idea is solid. I'm guessing that the collision tolerance stuff in the Rigid datablock is intended to avoid this whole thing by adding an invisible bubble of repulsion to the object, but that only works up to a point.
There are complete failures in the algorithm, in other words what happens with the crates, but I think it still may be possible to improve the functionality for what it considers proper geometry. There may also be some super-amazing way to fix the issues with flat surfaces, but it's a less important issue than the interpenetration stuff from my point of view.
11/06/2007 (4:03 pm)
Hey, I'm jumping into this a little late, but I actually went through more or less the same process as Ross when I attempted to fix the vehicle collision solver last year. I'm glad to see people are still working on this.I also read through Baraff's documentation of the rigid body algorithms which were used for TGE, specifically to compare said algorithms with the actual code found in the vehicle-vs-vehicle collision function, and they're basically spot on (minus the obvious typo at the bottom of the original function). The problem seems to be that, as Ross said, this stuff really was never intended to be used in an application this dynamic. Also, trying to stack crates will quickly prove that, again as Ross mentioned, the algorithm really doesn't like big flat surfaces. For safety, make your crates kind of like chamfer boxes.
In the end, I came up with the same solutions; I implemented the loop hack (using a counter or completely removing the loop), which solved the crashing, but left the failure rate about the same. I collected minor collision detection fixes, which really didn't do much.
As a final attempt to make the physics "playable," as opposed to realistic, I implemented a cheap inter penetration hack, which adds the inter penetration to the velocity of the collision, basically saying, "somehow these two objects are inside each other.. let's pretend they're really *about* to be inside each other due to their velocity and solve that instead." This actually works out for the vehicles, as any collision which doesn't call in time to miss inter penetration simply hits a lot harder. The result is slightly exaggerated collision, but it's still solid enough that you can stack jeeps without them flipping out.
It is worth noting that my tests showed that the physics were far less crash-prone while running off a dedicated server! I'm not sure why this is exactly, but my theory is that running the server and client together in one instance creates some interpolation issues which result in the object creating bizarre collision situations which produce astronomical values of force. Running on a dedicated server, you can see these situations pop up, but the object will immediately snap back to a sane server-dictated position before the client can say "I think this should be fired at the moon."
-------------------------
This is getting kind of long, but there is one area I always meant to look into and never got around to. Baraff explains that you'll need to be able to reset the position of your sim to the exact time the collision would have occurred, and as far as I can tell, this absolutely is not happening. The algorithm has no case for interpenetration, so when it occurs (and it will occur), the objects just stay that close unless an outside force changes the situation. My interpenetration hack is a super-cheap version of this, but it's not mathematically accurate in any way. As I understand it (and it's been a year since I read that stuff), what should happen is:
1) Find the time this collision would have happened at based on already having all the numbers for prediction.
2)If you catch it less than a frame (interpolation frame) too late, predict backwards and use the state from the moment of impact to do the solver work. For simplicity, we're probably actually going to actually snap that object back to said old position. If this is vs. another rigid body, do it for both.
3) Apply the impulse to the object.
4) Sim out the time you "took away" earlier. If you went back 10ms, sim the object forward 10ms based on the new, solved impulse. If vs. another rigid body, do this for both objects. Do it one of two ways:
4a) Just snap it forward like we did before (it was pretty safe to do it before, as we knew the object had just been there and was unlikely to hit anything on the way back). There's a slim chance you'll miss a new collision, but since it happens in less than a frame, the next cycle should be able to handle it the same way. Right? Hmm..
4b) Actually sim it forward to check for any new collisions in that 10 ms. Is there an easy way to sim only one object forward? Can I call its processTick function with a made up amount of time and expect that to work? Do we really need to do this, or is it ok to let the objects hang outside of time for 10ms?
It actually doesn't sound that bad now that I write it out. All you really need to do is store the old pos, rot, and lin/ang velocity from the last interpolation frame and use a percentage of that to do the back-interpolation. Obviously you lose that 15ms (or whatever) in the real game, as the object snaps from about to collide to just collided, but that's perfectly normal, and remember that it occurs at the interpolation rate, which is very fast, generally faster than the player's framerate.
Baraff mentions that you need this, but doesn't include specifics, since it's dependent on your simulation. I could be wrong about the actual process, but the general idea is solid. I'm guessing that the collision tolerance stuff in the Rigid datablock is intended to avoid this whole thing by adding an invisible bubble of repulsion to the object, but that only works up to a point.
There are complete failures in the algorithm, in other words what happens with the crates, but I think it still may be possible to improve the functionality for what it considers proper geometry. There may also be some super-amazing way to fix the issues with flat surfaces, but it's a less important issue than the interpenetration stuff from my point of view.
#87
11/06/2007 (4:32 pm)
@Henry, you're absolutely right about stepping the simulation back to the time when collision would have occurred. We looked at doing that at work but just didn't have the time. Unfortunately, as easy as it sounds there are some complexities due to the way Torque generates all its various bounding boxes, collision details etc. It definitely can work, but it wouldn't be a quick fix by any stretch.
#88
11/07/2007 (8:25 am)
Henry, could you talk a bit more about your "interpentration hack"?
#89
Sorry to be gauche, I don't care for those "bounty" posts, and I'm not a rich man, and frankly I don't even NEED this fixed right now...it's just so annoying to be so close! I realize that extremely helpful ideas have been posted--I'm just not yet coder enough to implement them. Like Henry I'm not so concerned about realism, gameplay is much more important, but vehicles flying through each other and walls and stuff is just a bit silly. But seriously I'll send you a check.
Well, the FIRST person who does! :-) I actually don't have two hundred dollars to spend right now.
edit @Ross: you DO still have some serious beer coming your way, already. You going to the IGC in Austin in a couple weeks by any chance?
11/14/2007 (10:07 pm)
Henry, I'll send you a hundred bucks if you post your code here. Or anyone else who's solved it.Sorry to be gauche, I don't care for those "bounty" posts, and I'm not a rich man, and frankly I don't even NEED this fixed right now...it's just so annoying to be so close! I realize that extremely helpful ideas have been posted--I'm just not yet coder enough to implement them. Like Henry I'm not so concerned about realism, gameplay is much more important, but vehicles flying through each other and walls and stuff is just a bit silly. But seriously I'll send you a check.
Well, the FIRST person who does! :-) I actually don't have two hundred dollars to spend right now.
edit @Ross: you DO still have some serious beer coming your way, already. You going to the IGC in Austin in a couple weeks by any chance?
#90
thankyou.
11/16/2007 (6:58 am)
Quote:Sorry to be gauche, I don't care for those "bounty" posts, and I'm not a rich man, and frankly I don't even NEED this fixed right now...it's just so annoying to be so close!nice spirit, Lee. i respect your community mindedness and generosity.
thankyou.
#93
Seriously, though,
//putting on my manager hat
what is the status of this?
What is the workaround?
Are people still looking into this?
Will this be under my christmas tree?
Also, Thanks goes out to everyone who has sweat on this one. ;)
12/21/2007 (12:37 pm)
//completely solve the vehicle collision issues that people have been bitching about since 2002Seriously, though,
//putting on my manager hat
what is the status of this?
What is the workaround?
Are people still looking into this?
Will this be under my christmas tree?
Also, Thanks goes out to everyone who has sweat on this one. ;)
#94
01/30/2008 (6:27 am)
I too am interested in the status of vehicle physics/collisions. Has anyone ever resolved this? 
#95
02/19/2008 (3:18 pm)
Guessing henry didn't want that $100.
#96
'sokay, I'll get it sorted one way or the other.
02/19/2008 (4:11 pm)
Lol I think it's more to do with it not being enough money for the amount of work required.'sokay, I'll get it sorted one way or the other.
#97
I'm kind of reviving an ancient thread here, but if this is still something people care about, I'd be happy to post my code.. nothing's changed since my original post here, though. I actually moved to using PhysX for a while, but I didn't have the patience to implement proper networking interpolation. I definitely recommend it for any single-player application or anything that doesn't expect a high-latency situation.
08/09/2008 (4:16 pm)
Heh, sorry, I actually never came back to check on this thread until just today. The solutions I came up with are largely hacks, and while they do get the job done to a certain degree, I wouldn't call them a valid solution, and certainly not worth paying for. I never actually wrote any code for that whole simulation back-peddling thing, just the inter penetration hack I mentioned.I'm kind of reviving an ancient thread here, but if this is still something people care about, I'd be happy to post my code.. nothing's changed since my original post here, though. I actually moved to using PhysX for a while, but I didn't have the patience to implement proper networking interpolation. I definitely recommend it for any single-player application or anything that doesn't expect a high-latency situation.
#98
You'd be, like, a supergod if you posted your code.
08/09/2008 (4:37 pm)
@Henry: you were a god to post what you already did.You'd be, like, a supergod if you posted your code.
#99
Luke Lamothe from Luma (the Mini#37 guys) was kind enough to email me a huge amount of useful advice about their experiences on Mini#37 and another racer they're currently working on for Instant Action. Unfortunately I'm not at the stage where I can make any immediate use of it except to take it under consideration in our plan, kinda decided that it wasn't a critical issue for prototyping so it's been slotted in further down the line.
That said, I'd be more than happy to lend my hand to any attempt at taking this further. Luke has hinted at the possibility of releasing a resource in the future although I gather he has his hands rather full at the moment. Unless I've missed something somewhere I reckon a good solid resource for vehicle collision is something that's long overdue for Torque. :)
08/09/2008 (5:18 pm)
@Henry Todd - People definitely still care about this, infact I'm really pleased to see this thread get revived having recently found it (and several others) while researching quirks, fixes and resources for TGE vehicles.Luke Lamothe from Luma (the Mini#37 guys) was kind enough to email me a huge amount of useful advice about their experiences on Mini#37 and another racer they're currently working on for Instant Action. Unfortunately I'm not at the stage where I can make any immediate use of it except to take it under consideration in our plan, kinda decided that it wasn't a critical issue for prototyping so it's been slotted in further down the line.
That said, I'd be more than happy to lend my hand to any attempt at taking this further. Luke has hinted at the possibility of releasing a resource in the future although I gather he has his hands rather full at the moment. Unless I've missed something somewhere I reckon a good solid resource for vehicle collision is something that's long overdue for Torque. :)
Torque Owner Lee Latham
Default Studio Name
I'll give the polysoup vehicles a crack. I guess you're thinking they may not have the interpenetration problems?