Vehicle/Rigid Collision Fixes

#1 In vehicle.cpp replace these functions:

bool Vehicle::resolveCollision(Rigid&  ns,CollisionList& cList)
{
   // Apply impulses to resolve collision
   bool colliding, collided = false;
   
   do 
   {
      colliding = false;
      for (S32 i = 0; i < cList.count; i++) 
      {
         Collision& c = cList.collision[i];
          
         // TODO: We're getting collisions against ourselves here because
         // Convex::updateWorkingList() doesn't filter them.  Is there any
         // good reason why it doesn't skip over these to save performance?
         if ( c.object == this )
            continue;
  
         if ( c.distance > mDataBlock->collisionTol ) 
            continue;
  
         // Velocity into surface
         Point3F v,r;
         ns.getOriginVector(c.point,&r);
         ns.getVelocity(r,&v);
         F32 vn = mDot(v,c.normal);
  
         // Only interested in velocities greater than sContactTol,
         // velocities less than that will be dealt with as contacts
         // "constraints".
         if ( mFabs(vn) < mDataBlock->contactTol )
            continue;
  
         // Apply impulses to the rigid body to keep it from
         // penetrating the surface.
         if ( c.object->getTypeMask() & VehicleObjectType )
         {
            Vehicle* other = static_cast<Vehicle*>( c.object );
            colliding |= ns.resolveCollision(c.point , c.normal, &other->mRigid );
         }
         else
            colliding |= ns.resolveCollision(c.point, c.normal);
  
         // This keeps track if we had any collisions during
         // any of the iteration loops.
         collided |= colliding;
  
         // Keep track of objects we collide with
         if (!isGhost() && c.object->getTypeMask() & ShapeBaseObjectType) 
         {
            ShapeBase* col = static_cast<ShapeBase*>(c.object);
            queueCollision(col,v - col->getVelocity());
         }
      }
  
   } while (colliding);
  
   return collided;
}
 
bool Vehicle::resolveContacts(Rigid& ns,CollisionList& cList,F32 dt)
{
   // Use spring forces to manage contact constraints.
   bool collided = false;
   Point3F t,p(0,0,0),l(0,0,0);
   for (S32 i = 0; i < cList.count; i++) 
   {
      Collision& c = cList.collision[i];
 
      // TODO: We're getting collisions against ourselves here because
      // Convex::updateWorkingList() doesn't filter them.  Is there any
      // good reason why it doesn't skip over these to save performance?
      if ( c.object == this )
         continue;
 
      if ( c.distance > mDataBlock->collisionTol )
         continue;
       
      // Velocity into the surface
      Point3F v,r;
      ns.getOriginVector(c.point,&r);
      ns.getVelocity(r,&v);
      F32 vn = mDot(v,c.normal);

      // Only interested in velocities less than mDataBlock->contactTol,
      // velocities greater than that are dealt with as collisions.
      if ( mFabs(vn) > mDataBlock->contactTol )
         continue;
 
      collided = true;
 
      // Penetration force. This is actually a spring which
      // will seperate the body from the collision surface.
      F32 zi = 2 * mFabs(mRigid.getZeroImpulse(r,c.normal));
      F32 s = (mDataBlock->collisionTol - c.distance) * zi - ((vn / mDataBlock->contactTol) * zi);
      Point3F f = c.normal * s;
 
      // 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 - (c.normal * vn);
      F32 ul = uv.len();
      if (s > 0 && ul) 
      {
         uv /= -ul;
         F32 u = ul * ns.getZeroImpulse(r,uv);
         s *= mRigid.friction;
         if (u > s)
            u = s;
         f += uv * u;
      }
 
      // Accumulate forces
      p += f;
      mCross(r,f,&t);
      l += t;
   }
 
   // Contact constraint forces act over time...
   ns.linMomentum += p * dt;
   ns.angMomentum += l * dt;
   ns.updateVelocity();
   return true;
}

#2 First of... FYI... Ross is one of the new programmers here at Sickhead.

Our goal is to completely solve the vehicle collision issues that people have been bitching about since 2002.

While these changes still result in some penetrations, they do actually work in the majority of the cases. A vehicle can push and knock another vehicle around when hitting it. It is a night and day change in how vehicles behave. After what we found today, we're sure that a little more debugging will turn up the last few bugs and get vehicle collision response working properly.

Show us some love by buying Torsion. ;)

#3 You are the man! Erm, men! People! Nice people!

The vehicle/vehicle collision stuff is just delightful. It's as though, you know, there is actually physics happening there :) For example I drove into another car at high speed and it rolled over and over. Just great. Just great.

Looks like your code needs to be applied to the RigidShape class (vehicle/rigidshape collisions often result in a lockup--not complaining, just observing! Presumebly y'all didn't use rigidshape class in your game). Tried to slap it in there,
wasn't quite plug'n'play, there's a pointer or something that isn't being initialized or something--I'm gonna jack with it tomorrow and post the fix when/if I get it. Happily, my professional coder buddy is coming to visit, so I'm sure he'll be delighted to check it out if I can't get it :)

Anyway, I drove/flew around my map in a super collidy way for an hour after applying this patch, and not a single lockup--totally unheard of before.

Thanks again!
Lee
P.S. I own Torsion, and recommend it to anyone who will listen! There have been a couple issues with my game I could never have solved without Torsion. Never. Ever. Forget it, uh-uh.

#4 I think some of the reasons for the interpenetration might actually be faults in the collision detection code, btw. So you may need to look at that, it might not be solvable in the collision resolution code.

#5 Fantastic... Thanx guys!

#6 You can't imagine how happy this fix makes me... ;-))

Thanks!

#7 Hey I already bought Torsion and I couldn't live without it now! Good work btw and thanks!

#8 First up, let me say looking good so far, it *does* improve on the baseline alot... however... getting some odd issues when ramming one wheeledvehicle into another while they're both traveling the same direction... seems almost as if the collision points aren't being released after resolution, as the game starts to grind a bit... Going to go review my own codebase for anything that might be interfereing, but figured I'd best pass that along as a heads up.

#9 @Sam - I did apply Garney's collision fix from a few months back, but i'll recheck that. Still there could be more bugs than that.

@Martin - Is this giving you better collisions in your flying starter kit as well? Is this giving you better mid air collisions between planes?

@Kirk - We're seeing that issue as well and working on it. Again... it isn't done, but much much better.

#10 Tossed in the following for a quick-hack:

bool Vehicle::resolveCollision(Rigid&  ns,CollisionList& cList)
...
         collided |= colliding;
			if (colliding) itr++;
...
   } while (colliding && itr<64);

wich seems to have mitigated it *to a degree*, however, doesn't out and out stop the behavior. Also noted it seems to be more likely to occur on a second itteration of a map, though I *think* I can be reasonably certain
in stating thats unlikely to be related... still...

Lil bit more data for you... still haven't traced it down totally, but:

Behaving:
Ordered by non-sub total time -
%%NSTime %% Time Invoke # Name
0.006 0.006 1524 VehicleResolveContacts
0.004 0.004 1524 VehicleResolveCollision

Ordered by non-sub total time -
%%NSTime %% Time Invoke # Name
0.006 0.006 1524 VehicleResolveContacts
0.004 0.004 1524 VehicleResolveCollision

4.627 0.002 28 ServerProcess
0.005 0.005 1224 VehicleResolveContacts
0.004 0.004 1224 VehicleResolveCollision
1.863 0.122 28 ClientProcess
0.001 0.001 300 VehicleResolveContacts
0.001 0.001 300 VehicleResolveCollision

MisBehaving:
0.007 0.007 11396 VehicleResolveCollision
0.004 0.004 6864 VehicleResolveCollision

4.166 0.001 59 ServerProcess
0.005 0.005 6864 VehicleResolveContacts
0.004 0.004 6864 VehicleResolveCollision
2.572 0.076 59 ClientProcess
0.003 0.003 4532 VehicleResolveCollision
0.010 0.010 4532 VehicleResolveContacts

mebbey I'm just misreading the data here, but... seems the time it's taking to go through the client-side contact resolution function when it's not playing so nice is inordinately long comparatively speaking...

#11 @Tom: I would assume yes - both yes. Haven't tested that yet because of beeing so busy writing mails to GG regarding the FGE. Today the collisions between ships and the ground often end up in getting the ships stuck in each other or in the ground and it may be solved with that. Normally you wouldn't see that often in the FGE because ships explode then, but the bug is there. Haven't dived deep into the fix above, but from what I overlooked so far it looks promising. Super!

#12 @Kirk -

Quote:Tossed in the following for a quick-hack:

which seems to have mitigated it *to a degree*

To be sure i understand what your talking about... mitigated what exactly? The stickiness of collisions?

The trick you have there... stopping after a certain amount of iterations is a bad idea. This is saying "you didn't resolve all the collisions... so give up" which would leave you in a penetrated state. From our testing the only cases where you are stuck in this loop is when the input collision data is wrong.

We did find a case where we got a divide by zero out of Convex which resulted in a NaN in the collision normal. This then NaN'd the Rigid integrator and you would get stuck in the Vehicle::resolveCollision() loop. We have a fix for that and another improvement that Ross will post in a bit.

So we're getting closer.

#13 Here's a couple of fixes, including the fix to the ConvexFeature::testEdge function which was causing divide by zero problems. The other change is the one suggested by Brad Shapcott and confirmed by myself and Tom this morning (in Vehicle::updatePos).

First the change to updatePos (only the top part up to the call to updateCollision):

void Vehicle::updatePos(F32 dt)
{
   Point3F origVelocity = mRigid.linVelocity;
 
   // Update internal forces acting on the body.
   mRigid.clearForces();
   updateForces(dt);
 
   // We first integrate the rigid body which calculates
   // the new rigid position based on its current velocities.
   if (!mRigid.atRest)
      mRigid.integrate(dt);
 
   // We have a new world position and we can now update the
   // collision information and check for collisions.
   bool collided = false;
   if (!mRigid.atRest) 
   {
      collided = updateCollision(dt);

And in convex.cpp:

void ConvexFeature::testEdge(ConvexFeature* cf,const Point3F& s1, const Point3F& e1, CollisionList* cList, F32 tol)
{
   F32 tolSquared = tol*tol;
 
   // Test edges against edges
   const Edge* edge = mEdgeList.begin();
   const Edge* end  = mEdgeList.end();
   for (; edge != end; edge++) {
      if (cList->count >= CollisionList::MaxCollisions)
         return;
 
      const Point3F& s2 = mVertexList[edge->vertex[0]];
      const Point3F& e2 = mVertexList[edge->vertex[1]];
 
      // Get the distance and closest points
      Point3F i1,i2;
      F32 distance = sqrDistanceEdges(s1, e1, s2, e2, &i1, &i2);
      if (distance > tolSquared)
         continue;

      VectorF normal = i1 - i2;
 
      // The distance returned above from sqrDistanceEdges is 
      // squared.  If the distance is small the squared distance
      // would be an order of magnitude smaller.  This can cause
      // a zero squared distance when there is a non-zero normal
      // length.
      // 
      // This commented line is what the code used to do, which
      // is only really a performance optimization.
      //
      //distance = mSqrt(distance);
      //
      // For now... until we resolve the other collision issues
      // lets use the accurate distance value to ensure we get
      // good collision normals.
      distance = normal.len();
 
      // Need to figure out how to orient the collision normal.
      // The current test involves checking to see whether the collision
      // points are contained within the convex volumes, which is slow.
      if (inVolume(i1) || cf->inVolume(i2))
         distance = -distance;
 
      // Normalize the contact normal, but beware of divide-by-zero.
      if ( mFabs( distance ) > 0 )
         normal *= 1 / distance;
 
      // Return a collision
      Collision& info = cList->collision[cList->count++];
      info.point    = i1;
      info.normal   = normal;
      info.distance = distance;
      info.material = material;
      info.object   = object;
   }
}

#14 Apologies: "and you would get stuck in the Vehicle::resolveCollision() loop." is precicely the issue I was looking at, for clarity.

As well, I'm fully aware a collision-count limiter is a nasty notion most times, hence calling it a hack in the first place. Been using that for similar issues for quite a while now though to resolve the flat out lockup of the stock method, and this seemd the same issue.

Afraid right now theres quite a few spots I'm having to simply settle for 'good enough' instead of ideal, simply to finish up the prototype stage this end. Glad to see better solutions are recieving the needed attention, though.

#15 Here are some updates from today's work on the collision code. We've reverted the change made to updatePos regarding where Rigid::integrate is called, as it seems from testing and analysis that it's actually more correct to do that after the updateCollision call (provides better results). In addition we've tracked down some bugs and incorrect math in resolveContacts. Currently the code below will provide almost flawless collisions with static objects of any type (if anyone can manage to get a vehicle penetrating DIFs or other stationary geometry, please try to figure out the issue, as we haven't seen any further problems of this sort in our testing today). There are still issues with the collisions between vehicles, resulting in inter-penetrations. If anyone has any code or ideas where these issues are arising, post! For the most part though, this will perform much better all around and fixes some potentially very nasty problems.


A number of small but important changes to convex.cpp (testVertex and testEdge):

void ConvexFeature::testVertex(const Point3F& v,CollisionList* cList,bool flip, F32 tol)
{
   // Test vertex against all faces
   const Face* face = mFaceList.begin();
   const Face* end  = mFaceList.end();
   for (; face != end; face++) {
      if (cList->count >= CollisionList::MaxCollisions)
         return;
 
      const Point3F& p0 = mVertexList[face->vertex[0]];
      const Point3F& p1 = mVertexList[face->vertex[1]];
      const Point3F& p2 = mVertexList[face->vertex[2]];
 
      // Point near the plane?
      F32 distance = mFabs( mDot(face->normal,v - p0) );
      if ( distance > tol )
         continue;
 
      // Make sure it's within the bounding edges
      if (isInside(v,p0,p1,face->normal) && isInside(v,p1,p2,face->normal) &&
            isInside(v,p2,p0,face->normal)) {
 
         // Add collision to this face
         Collision& info = cList->collision[cList->count++];
         info.point = v;
         info.normal = face->normal;
         if (flip)
            info.normal.neg();
       
         info.material = material;
         info.object = object;
         info.distance = distance;
      }
   }
}

void ConvexFeature::testEdge(ConvexFeature* cf,const Point3F& s1, const Point3F& e1, CollisionList* cList, F32 tol)
{
   F32 tolSquared = tol*tol;
 
   // Test edges against edges
   const Edge* edge = mEdgeList.begin();
   const Edge* end  = mEdgeList.end();
   for (; edge != end; edge++) {
      if (cList->count >= CollisionList::MaxCollisions)
         return;
 
      const Point3F& s2 = mVertexList[edge->vertex[0]];
      const Point3F& e2 = mVertexList[edge->vertex[1]];
 
      // Get the distance and closest points
      Point3F i1,i2;
      F32 distance = sqrDistanceEdges(s1, e1, s2, e2, &i1, &i2);
      if (distance > tolSquared)
         continue;
 
      VectorF normal = i1 - i2;
 
      // The distance returned above from sqrDistanceEdges is 
      // squared.  If the distance is small the squared distance
      // would be an order of magnitude smaller.  This can cause
      // a zero squared distance when there is a non-zero normal
      // length.
      // 
      // This commented line is what the code used to do, which
      // is only really a performance optimization.
      //
      //distance = mSqrt(distance);
      //
      // For now... until we resolve the other collision issues
      // lets use the accurate distance value to ensure we get
      // good collision normals.
      distance = normal.len();
 
      // Need to figure out how to orient the collision normal.
      // The current test involves checking to see whether the collision
      // points are contained within the convex volumes, which is slow.
      if (inVolume(i1) || cf->inVolume(i2))
         distance = -distance;
 
      // Normalize the contact normal, but beware of divide-by-zero.
      if ( mFabs( distance ) > 0 )
         normal *= 1 / distance;
 
      // Return a collision
      Collision& info = cList->collision[cList->count++];
      info.point    = i1;
      info.normal   = normal;
      
      info.distance = mFabs( distance );
      info.material = material;
      info.object   = object;
   }
}

IMPORTANT: updatePos in vehicle.cpp was changed back after testing to call the Rigid::integrate method after the updateCollision method, because this was shown to result in better simulation. I'm not reposting the entire function here for the sake of brevity, but this change should be made if you used the code from the earlier post of today that changed it.

The only other major changes were made to the resolveContacts function to solve problems with divides by zero and negative values of the distance variable.

In vehicle.cpp:

bool Vehicle::resolveContacts(Rigid& ns,CollisionList& cList,F32 dt)
{
   // Use spring forces to manage contact constraints.
   bool collided = false;
   Point3F t,p(0,0,0),l(0,0,0);
   for (S32 i = 0; i < cList.count; i++) 
   {
      Collision& c = cList.collision[i];
 
      // TODO: We're getting collisions against ourselves here because
      // Convex::updateWorkingList() doesn't filter them.  Is there any
      // good reason why it doesn't skip over these to save performance?
      if ( c.object == this )
         continue;
 

      
 
      // If the collision is further away than our tolerance
      // then we don't count it as a contact.
      if ( c.distance > mDataBlock->collisionTol )
         continue;
       
      // Velocity into the surface
      Point3F v,r;
      ns.getOriginVector(c.point,&r);
      ns.getVelocity(r,&v);
      F32 vn = mDot(v,c.normal);
 
      // Only interested in velocities less than mDataBlock->contactTol,
      // velocities greater than that are dealt with as collisions.
      if ( mFabs(vn) > mDataBlock->contactTol )
         continue;
 
      collided = true;
 
      // Penetration force. 
      // The "zero impulse" is the impulse needed to stop movement
      // along a normal at some point.  We multiply this by two here
      // to generate a reverse force in the direction of the contact.
      F32 zi = 2 * mFabs(mRigid.getZeroImpulse(r,c.normal));
 
      // This is actually a spring which will seperate the body 
      // from the collision surface.
      F32 s = (mDataBlock->collisionTol - c.distance) * zi; // - ((mFabs(vn) / mDataBlock->contactTol) * zi);
      Point3F f = c.normal * s;
 
      // 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 - (c.normal * vn);
      F32 ul = uv.len();
      if (s > 0 && ul) 
      {
         uv /= -ul;
         F32 u = ul * ns.getZeroImpulse(r,uv);
         s *= mRigid.friction;
         if (u > s)
            u = s;
         f += uv * u;
      }
 
      // Accumulate forces
      p += f;
      mCross(r,f,&t);
      l += t;
 
      // If we have a collision with another object, it needs to have
      // atRest set to false, so it will do velocity/position updates
      if ( c.object->getTypeMask() & VehicleObjectType )
      {
         Vehicle* other = static_cast<Vehicle*>( c.object );
         other->mRigid.atRest = false;
      }
   }
 
   // Only add forces if we actually collided
   if ( collided )
   {
      // Contact constraint forces act over time...
      ns.linMomentum += p * dt;
      ns.angMomentum += l * dt;
      ns.updateVelocity();
      ns.atRest = false;
   }
 
   return true;
}

#16 Support shown... got Torsion (finally)
I'm sure I speak for everyone when I say I REALLY appreciate your dedicated efforts!

#17 And another thing. Haven't looked at it in code (I'll just waste my time with collision code), but will these changes help/work with the Polysoup code?

I'm thinking of implementing the Polysoup code for TSStatics but keeping the rest the way it is (specifically Vehicles, since I'm using that). If these fixes you guys are giving here has nothing to do with that, I'll rather stick with this. So I need some advice here.

#18 In order to help with vehicle/vehicle collisions, you can try the following:

In vehicle.cc, set:

const S32 sMaxWarpTicks = 0;

This will remove the client-side interpolation of vehicles (which will cause them to "pop" given low framerates), but it has pretty much solved all vehicle/vehicle collision problems on my side (although, I've done another score of tweaks/fixes along with that change...). It may not do anything for you, but it certainly has for me. However, it only fixes issues when both vehicles are moving. Even with the WarpTicks set to the default value, I have no issues with one moving vehicle and one stationary vehicle, no matter their impacts.

It's not so much a solution as a temporary fix for me until I can find out why client-side prediction causes vehicle collision to be so wonky. I started a thread a few weeks back hoping for help on the issue (http://www.garagegames.com/mg/forums/result.thread.php?qt=62695), but it seems that nobody else (other than Kirk) has anything to add to my predicament...

#19 In order to help with vehicle/vehicle collisions, you can try the following:

In vehicle.cc, set:

const S32 sMaxWarpTicks = 0;

This will remove the client-side interpolation of vehicles (which will cause them to "pop" given low framerates), but it has pretty much solved all vehicle/vehicle collision problems on my side (although, I've done another score of tweaks/fixes along with that change...). It may not do anything for you, but it certainly has for me. However, it only fixes issues when both vehicles are moving. Even with the WarpTicks set to the default value, I have no issues with one moving vehicle and one stationary vehicle, no matter their impacts.

It's not so much a solution as a temporary fix for me until I can find out why client-side prediction causes vehicle collision to be so wonky. I started a thread a few weeks back hoping for help on the issue (www.garagegames.com/mg/forums/result.thread.php?qt=62695), but it seems that nobody else (other than Kirk) has anything to add to my predicament...

#20 @James - We're using the polysoup stuff here when testing this. So we're testing WheeledVehicle vs. WheeledVehicle, WheeledVehicle vs. Polysoup TSStatics, and WheeledVehicle vs. DIF. The only thing that has penetration issues is WheeledVehicle vs. WheeledVehicle. Everything else is rock solid.

While you probably could convert WheeledVehicle to use Polysoup collisions it would be more CPU intensive and make WheeledVehicle vs. WheeledVehicle collisions even more complex. I do not see a great benifit to it.

@Luke - We're testing that now and report back... thanks for pointing it out.