   Swept collision response and first time of collision doesn't work.
  After reading through the forums and articles on gamedev I decided to replace my take the deepest penetration depth collision response with a find the first time of collision response.I currently trying this out with 4 AABBs, 3 of which are stationary, 1 is moving.The 3 AABBs stationary are positioned in an L shape and the moving AABB approaches from the right:The position of my moving AABB is updated as follows:  Contact3D contact = new Contact3D();  float p = 0;  Vector3 n = Vector3.Zero;  float tMin = float.MaxValue;  Vector3 velocity = direction3D * speed * dt_Seconds;  debug_AABB[0].Velocity = velocity;  debug_AABB[0].Position += velocity;  for (int i = 0; i < Settings.RESOLUTION_ITERATIONS_MAX; ++i)  { tMin = float.MaxValue; bool coll = false; if (Detection3D.TestShapeShape(debug_AABB[0], debug_AABB[1], ref contact)) {Console.WriteLine("AABB 1 t_Enter: {0}", contact.t_Enter);if (contact.t_Enter < tMin){    p = contact.penetration;    n = contact.normal;    tMin = contact.t_Enter;    coll = true;} } if (Detection3D.TestShapeShape(debug_AABB[0], debug_AABB[2], ref contact)) {Console.WriteLine("AABB 2 t_Enter: {0}", contact.t_Enter);if (contact.t_Enter < tMin){    p = contact.penetration;    n = contact.normal;    tMin = contact.t_Enter;    coll = true;} } if (Detection3D.TestShapeShape(debug_AABB[0], debug_AABB[3], ref contact)) {Console.WriteLine("AABB 3 t_Enter: {0}", contact.t_Enter);if (contact.t_Enter < tMin){    p = contact.penetration;    n = contact.normal;    tMin = contact.t_Enter;    coll = true;} } if (coll) {debug_AABB[0].Position += n * p;debug_AABB[0].Position += debug_AABB[0].Velocity * contact.t_Enter; }  }The code finds the first time of collision and adjusts the moving AABBs position using the contact details.The problem is that the time of collision will often be 0 for 2 or more AABBs which prevents the response from being correct.  Why is this happening?The collision detection code for 2 AABBs is as follows:   private static bool TestAABBAABB(Shape3D s1, Shape3D s2, ref Contact3D contact)   {  CD_AABB a = (CD_AABB)s1;  CD_AABB b = (CD_AABB)s2;  Vector3 vel_Relative = a.Velocity - b.Velocity;  // Minimum Translation Vector parameters  float mtv_Distance = float.MaxValue;  // Set current minimum distance (max float value so next value is always less)  int mtv_Axis = 0; // Axis along which to travel with the minimum distance  // For each separating axis  for (int i = 0; i < 3; ++i)  { // Find distance intervals for current two slabs // Distance is between slab min/max values float d_S0 = a.MinPoint.Index(i) - b.MaxPoint.Index(i); float d_S1 = b.MinPoint.Index(i) - a.MaxPoint.Index(i); // The distance is positive if the intervals do not overlap // Must be >= to 0 and not > 0, otherwise MTV can equal Vector2.Zero and cause NaN if (d_S0 >= 0f || d_S1 >= 0f) {return false; } // Current distance interval for slabs float d = (d_S0 > d_S1) ? -d_S0 : d_S1; // If d is the smallest distance so far if (Math.Abs(d) < Math.Abs(mtv_Distance)) {// Store the distance and the current axismtv_Distance = d;mtv_Axis = i; }  }  // Minimum Translation Vector  Vector3 mtv = Vector3.Zero;  switch (mtv_Axis)  { case 0:mtv.X = mtv_Distance;break; case 1:mtv.Y = mtv_Distance;break; case 2:mtv.Z = mtv_Distance;break;  }  contact.normal = Vector3.Normalize(mtv);  contact.penetration = Math.Abs(mtv_Distance) + Math_Util.EPSILON;  float speed = Vector3.Dot(contact.normal, vel_Relative);  float min1 = a.MinPoint.Index(mtv_Axis);  float max1 = a.MaxPoint.Index(mtv_Axis);  float min2 = b.MinPoint.Index(mtv_Axis);  float max2 = b.MaxPoint.Index(mtv_Axis);  float t0 = 0;  float t1 = float.MaxValue;  float tMax = 1.0f;   if (max1 < min2)  { if (speed <= 0.0f) {return false; } float t = (min2 - max1) / speed; t0 = Math.Max(t, t0); if (t0 > tMax) {return false; } t = (max2 - min1) / speed; t1 = Math.Min(t, t1); if (t0 > t1) {return false; }  }  else if (max2 < min1)  { if (speed >= 0.0f) {return false; } float t = (max2 - min1) / speed; t0 = Math.Max(t, t0); if (t0 > tMax) {return false; } t = (-max1 + min2) / speed; t1 = Math.Min(t, t1); if (t0 > t1) {return false; }  }  else  { if (speed > 0) {float t = (max2 - min1) / speed;t1 = Math.Min(t, t1);if (t0 > t1){    return false;} } else if (speed < 0) {float t = (min2 - max1) / speed;t1 = Math.Min(t, t1);if (t0 > t1){    return false;} }  }  contact.t_Enter = t0;  contact.t_Exit = t1;  return true;   }Can someone help a confused man out please?   
  I've cleaned up the swept axis test so it now looks as follows:  Vector3 vel_Relative = a.Velocity - b.Velocity;  float speed = Vector3.Dot(contact.normal, vel_Relative);  float min1 = a.MinPoint.Index(mtv_Axis);  float max1 = a.MaxPoint.Index(mtv_Axis);  float min2 = b.MinPoint.Index(mtv_Axis);  float max2 = b.MaxPoint.Index(mtv_Axis);  float t0 = 0.0f;  float t1 = 1.0f;  if (max1 < min2)  { if (speed <= 0.0f) {return false; } // Time = Distance (projected) / Speed t0 = Math.Max((min2 - max1) / speed, t0); t1 = Math.Min((max2 - min1) / speed, t1); // No overlap possible if time of first contact occurs after time of last contact if (t0 > t1) {return false; }  }  else if (max2 < min1)  { if (speed >= 0.0f) {return false; } t0 = Math.Max((max2 - min1) / speed, t0); t1 = Math.Min((min2 - max1) / speed, t1);  if (t0 > t1) {return false; }  }  else  { if (speed > 0) {t1 = Math.Min((max2 - min1) / speed, t1);if (t0 > t1){    return false;} } else if (speed < 0) {t1 = Math.Min((min2 - max1) / speed, t1);if (t0 > t1){    return false;} }  }  contact.t_Enter = t0;  contact.t_Exit = t1;  return true;If I adjust the position using the time of exit:debug_AABB[0].Position += debug_AABB[0].Velocity * contact.t_Exit;then the moving AABB will jump to the other side of the stationary AABB perfectly so I know that the exit time is calculated correctly.This method still suffers from tunnelling if the moving AABB moves too quickly, I thought a swept test was supposed to prevent that?My main problem is how can the entry time be 0.0f for 2 or more AABBs, I thought the swept test is supposed to be able to determine the first AABB intersected, so how is this the case?Please help, I'm losing hope :(EDIT: If I ignore the inital overlap test and just test based on velocity:  for (int i = 0; i < 3; ++i)  {float speed = Vector3.Dot(a.Axes, vel_Relative);  float min1 = a.MinPoint.Index(i); float min2 = b.MinPoint.Index(i); float max1 = a.MaxPoint.Index(i); float max2 = b.MaxPoint.Index(i); if (max1 < min2) {if (speed <= 0.0f){    return false;}// Time = Projected Distance / Speedt0 = Math.Max((min2 - max1) / speed, t0);t1 = Math.Min((max2 - min1) / speed, t1);// No overlap possible if time of first contact occurs after time of last contactif (t0 > t1){    return false;} } else if (max2 < min1) {if (speed >= 0.0f){    return false;}t0 = Math.Max((max2 - min1) / speed, t0);t1 = Math.Min((min2 - max1) / speed, t1);if (t0 > t1){    return false;} } else {if (speed > 0){    t1 = Math.Min((max2 - min1) / speed, t1);    if (t0 > t1)    {   return false;    }}else if (speed < 0){    t1 = Math.Min((min2 - max1) / speed, t1);    if (t0 > t1)    {   return false;    }} }  }  contact.t_Enter = t0;  contact.t_Exit = t1;  return true;then using t0 (t_Enter) makes the AABB stick when colliding.Am I moving the AABB incorrectly:  Contact3D contact = new Contact3D();  bool coll = false;  float p = 0;  Vector3 n = Vector3.Zero;  float tMin = float.MaxValue;  for (int i = 0; i < Settings.RESOLUTION_ITERATIONS_MAX; ++i)  { tMin = float.MaxValue; if (Detection3D.TestShapeShape(debug_AABB[0], debug_AABB[1], ref contact)) {if (contact.t_Enter < tMin){    p = contact.penetration;    n = contact.normal;    tMin = contact.t_Enter;    coll = true;} } if (Detection3D.TestShapeShape(debug_AABB[0], debug_AABB[2], ref contact)) {if (contact.t_Enter < tMin){    p = contact.penetration;    n = contact.normal;    tMin = contact.t_Enter;    coll = true;} } if (Detection3D.TestShapeShape(debug_AABB[0], debug_AABB[3], ref contact)) {if (contact.t_Enter < tMin){    p = contact.penetration;    n = contact.normal;    tMin = contact.t_Enter;    coll = true;} } if (coll) {debug_AABB[0].Position += debug_AABB[0].Velocity * contact.t_Enter; } else {Vector3 velocity = direction3D * speed * dt_Seconds;debug_AABB[0].Position += velocity;debug_AABB[0].Velocity = velocity; }  } [Edited by - Spa8nky on May 18, 2010 5:16:29 PM];Quote:The problem is that the time of collision will often be 0 for 2 or more AABBs which prevents the response from being correct. Why is this happening?time of 0.0f would indicate that (max2 - min1) / speedint0 = Math.Max((max2 - min1) / speed, t0);is always negative. I'd check if that is correct.[Edited by - oliii on May 19, 2010 9:59:23 AM];  I've simplified the movement of the AABB: Vector3 direction3D = Vector3.Zero; float xLeft = InputState.Instance.LeftX(PlayerIndex.One); float yLeft = InputState.Instance.LeftY(PlayerIndex.One); if (xLeft != 0f || yLeft != 0f) {direction3D.X = xLeft;direction3D.Z = -yLeft; } Vector3 velocity = Vector3.Zero; if (coll) {velocity -= debug_AABB[0].Velocity * contact.t_Enter; } else {velocity = direction3D * speed * dt_Seconds;   } debug_AABB[0].Velocity = velocity; debug_AABB[0].Position += velocity;If I move the AABB at a slow constant velocity:velocity = -Vector3.UnitX * 0.01f * dt_Seconds;then value of t0 stays positive and decreases towards 0 as the moving AABB approaches the stationary AABBs.Is this not correct?  I have never recorded t0 being < 0 using the following:float test = (max2 - min1) / speed;if (test < 0)    Console.WriteLine("Negative");Could you please explain why you thought this was a problem as I'm a little confused?   ;Quote:Original post by Spa8nkyI've simplified the movement of the AABB:then value of t0 stays positive and decreases towards 0 as the moving AABB approaches the stationary AABBs.Is this not correct?  Yes. So it's working. So what's the problem exactly then? I don't see how testing one, two or three boxes would cause any problems. Simply pick the one that happens the earliest as the first contact.   ;  The problem lies with the collision response.  If I have 2 AABBs, one moving and one stationary, then the moving AABB just "sticks" to the stationary AABB when it comes into contact.  Why is this occuring?For the collision response: I've tried moving the AABB position based on the first time of collision but I must have done something incorrect if the collision detection is sound.The movement of the moving AABB is updated as follows: Vector3 velocity = Vector3.Zero; if (collision) {velocity -= debug_AABB[0].Velocity * contact.t_Enter; } else {velocity = direction3D * speed * dt_Seconds;   } debug_AABB[0].Velocity = velocity; debug_AABB[0].Position += velocity;;  I decided to make things as simple as possible and use a moving sphere/sphere test:   public static bool TestSphereSphereSwept(Shape3D s1, Shape3D s2, Vector3 v0, Vector3 v1, ref Contact3D contact)   {  // [Quadratic Equation For t]  //  // t = -b - &#8730;(b^2 - ac)  //--------------  // a  CD_BoundingSphere x = (CD_BoundingSphere)s1;  CD_BoundingSphere y = (CD_BoundingSphere)s2;  Vector3 s = y.Position - x.Position; // Use centre when working correctly    // Relative velocity of s1 to stationary s0  Vector3 v = v1 - v0;  float r = y.Radius + x.Radius;  float c = Vector3.Dot(s, s) - r * r;  if (c < 0.0f)  { // Spheres initially overlapping (perform static test) // IGNORE FOR TIME BEING SO JUST SWEPT TEST IS USED //contact.isOverlapping = true; //contact.t0 = 0.0f; //return TestSphereSphere(s1, s2, ref contact); return false;  }  float a = Vector3.Dot(v, v);  if (a < Math_Util.EPSILON)  { // Spheres not moving relative to each other return false;  }  float b = Vector3.Dot(v, s);  if (b >= 0.0f)  { // Spheres not moving towards each other return false;  }  float d = b * b - a * c;  if (d < 0.0f)  { // No real-valued root, spheres do not intersect return false;  }  float t = (-b - (float)Math.Sqrt(d)) / a;  // Clamp t0 to range [0, 1]  contact.t0 = Math.Min(1.0f, t);  return true;   }I can't get a sliding collision reponse for two spheres either.  I clamp t0 to [0, 1] and the moving sphere just loses all velocity when in contact and doesn't slide when I use the velocity along the contact normal.  If I use too higher value for the speed then the moving sphere shakes when it comes into contact with the stationary sphere.This is my collision response code:  Vector3 velocity = direction3D * 10f * dt_Seconds;  Vector3 vOriginal = velocity;  if (Detection3D.TestSphereSphereSwept(debug_Sphere[0], debug_Sphere[1], velocity, Vector3.Zero, ref contact))  { // t0 is 0.0f if contact is overlapping velocity = velocity * contact.t0;  }  debug_Sphere[0].Position += velocity;  // Find the normal of the collision  Vector3 normal = Vector3.Normalize(debug_Sphere[0].Position - debug_Sphere[1].Position);   // Find the velocity along the normal  Vector3 vn = vOriginal * Vector3.Dot(vOriginal, normal);   // Move the sphere along the normal by the projected velocity  debug_Sphere[0].Position += vn;What have I done wrong?   ;  You're missing an iterative process.Quote:    velocity = direction3D * 10f * dt_Seconds;   // tolerance for minimum velocity length (1/10th millimeter).   float tolerance = 1.0e-4f;   // run several iterations.   // slide against each collision   int iter = 0;   while(iter++) < 10)   {  if (!Detection3D.TestSphereSphereSwept(debug_Sphere[0], debug_Sphere[1], velocity, Vector3.Zero, ref contact))  { // no collision, move the sphere. debug_Sphere[0].Position += velocity; break;  }  // part of the velocity before contact  Vector3 vin = velocity * contact.t0;    // travel distance to contact.  float length = Vector3.Length(vin);  // move to within a small distance to contact.  if(length <= tolerance) vin = Vector3(0, 0, 0);  else vin.setLength(length - tolerance);  // part of the velocity remaining after moving to contact  Vector3 vout = velocity - vin;   // move sphere to contact position.  debug_Sphere[0].Position += vin;  // contact normal  Vector3 normal = Vector3.Normalize(debug_Sphere[0].Position - debug_Sphere[1].Position); // slide remaining velocity against contact normal.  vout -= normal * Vector3.Dot(vout, normal);   // new velocity needed to check for collisions.  velocity = vout;  // travel distance to contact.  float length = Vector3.Length(velocity);  if(length <= tolerance)  { // velocity too small for use. break the cycle. break;  }    }Also it's worth checking out Kasper fauerby's paper as well on that matter.[Edited by - oliii on May 24, 2010 8:19:04 AM];  Thank you very much oliii.If the 2 spheres are intially overlapping, I can perform a static test:   public static bool TestSphereSphereSwept(Shape3D s1, Shape3D s2, Vector3 v0, Vector3 v1, ref Contact3D contact)   {  CD_BoundingSphere x = (CD_BoundingSphere)s1;  CD_BoundingSphere y = (CD_BoundingSphere)s2;  Vector3 s = y.Position - x.Position; // Use centre when working correctly    // Relative velocity of s1 to stationary s0  Vector3 v = v1 - v0;  float r = y.Radius + x.Radius;  float c = Vector3.Dot(s, s) - r * r;  if (c < 0.0f)  { // Spheres initially overlapping (perform static test) contact.isOverlapping = true; contact.t0 = 0.0f; return TestSphereSphere(s1, s2, ref contact);  }How do I deal with this case when using velocities?  Currently the code won't test the spheres for overlap if there is no velocity.  while (iter++ < Settings.RESOLUTION_ITERATIONS_MAX)  { // Distance to contact float l0 = velocity.Length(); if (l0 <= tolerance) {// Velocity too small to use.  Break the cycle.break; } if (!Detection3D.TestSphereSphereSwept(debug_Sphere[0], debug_Sphere[1], velocity, Vector3.Zero, ref contact)) {// No collision, move the sphere using velocity.  Break the cycledebug_Sphere[0].Position += velocity;break; }So I can't check for initial overlap this way.  What would you suggest for this case?   ;  I suppose you'll have to move the length check at the end of the loop. I've changed the code to reflect that. However, there is probably some more logic to be added. I suppose you could run the iteration loop for the swept test only, and run another test at the end to deal with just intersections. That's what I do in that demo, to 'unstuck' the sphere from the geometry as the slide algorithm isn't perfect (due to floating point innacuracies).   