   Separating Axis Test - Testing For Near Zero Vector
  I'm having a problem when testing for an instersection with an AABB and a Triangle.When the AABB intersects 2 Triangles at 270 degrees it will determine the wrong Triangle as the closest Triangle: (Triangle 1)  |  |  |    |________ (Triangle 2)  ^(AABB Hits here from this side)    _   |_| (AABB)    <------- (Direction of AABB)The AABB, although closer to Triangle 2 will determine that Triangle 1 is closer and this be pushed out by the Normal of Triangle 1 instead of the Normal of Triangle 2.This occurs when the AABB is sliding/moving from right to left, along the face of Triangle 2.Why would the AABB code determine that Triangle 1 is closer?Does it have something to do with the lack of Robustness of the Separating-Axis Test for an ABBB intersecting a Triangle?  (I.E. 2 edges being parallel (AABB and Triangle and floating point errors occurring?)Or is there something else going on here?I can post the intersection test should it be necessary but I didn't want to create too large a post to begin with.Thank you.   
  You can use < pre > or [ source ] tags (without the spaces) to preserve the formatting of your ASCII diagram. That'll make it easier to see what you're referring to.   ;  this is the problem annoyed me a long long time. here is a summary about how i solve such problem1) extend the SAT intersection test to handle moving stuff, ie finding first time contact (can also find last time contact)2) relax the aabbbasically, most of the time 1) will solve ur problem, given your collision response is sliding (instead of bouncing) and u will continue simulate as long as the remaining distance or time within the frame is still long enough. this way, after the first collision detection & response, ur aabb will probably pass a bit the triangle 1, so even if the first time contact report triangle 1, the collision normal will still be correct for the rest of the simulationthe need for 2) is that if u run into some walls having inner angle less than 90 degree then usually, u will keep penetrating into stuff and the collision detection & response will be undefined. also, animated environment may also cause u such penetration. therefore, relax is to correct this situation and the simulation can go on.for SAT to handle moving things, the axes to test are the same, ie tri's normal, box's axes (3 tests), box's axes crossing tri's edges (9 tests)the relax stuff is a bit tricky, if u want to know more, i can talk about it a bit   ;Quote:1) extend the SAT intersection test to handle moving stuff, ie finding first time contact (can also find last time contact)I think that this is where I am going wrong.  I have the following for testing a moving AABB against a Plane:   // Test if moving AABB (Axis Aligned Bounding Box) b intersects plane p   private bool TestAABBPlane(Plane p, out float radius, out float distance, out float time, out Vector3 point_Intersection)   {  // Compute the projection interval radius of b onto L(t) = b.c + t * p.n (calc extents distance relative to plane normal)  radius = Math.Abs(this.Extents.X * p.Normal.X) + Math.Abs(this.Extents.Y * p.Normal.Y) + Math.Abs(this.Extents.Z * p.Normal.Z);  //Console.WriteLine("Radius [Plane Method] " + radius);  Vector3 min_Origin = this.Min - this.Centre;  Vector3 max_Origin = this.Max - this.Centre;  Vector3 centre_Origin = (min_Origin + max_Origin) * 0.5f;  // Compute distance (s) of AABB center from plane   distance = Vector3.Dot(p.Normal, centre_Origin) - p.D;  time = float.MaxValue;  point_Intersection = Vector3.Zero;  // Intersection occurs when distance s falls within [-r,+r] interval  if (Math.Abs(distance) <= radius)  { // AABB is already overlapping the plane // Set time (t) of intersection to zero and collision point (q) to AABB center time = 0.0f; point_Intersection = this.Centre;  return true;  }  else  { // (v) = Direction vector for AABB (AABB.Direction) float denom = Vector3.Dot(p.Normal, this.Direction); if (denom * distance >= 0.0f)  // AABB moving parallel to or away from Plane (Therefore no intersection)  {return false; }else  // AABB is moving towards the Plane {// Use +r in computations if AABB in front of plane, else -r// float r = distance > 0.0f ? radius : -radius (Ternary Operator equivalent to below)if (distance <= 0.0f){    radius = -radius;}time = (radius - distance) / denom;point_Intersection = this.Centre + time * this.Direction - radius * p.Normal; return true; }   }   }The problem is that the time is never anything other than 0.0f because:  // Intersection occurs when distance s falls within [-r,+r] interval  if (Math.Abs(distance) <= radius)is ALWAYS true?!?!The full test for Triangle Intersection is as follows:   private CollisionResult TestAABBTriangle(CD_Triangle tri, CollisionResult result)   {  float p0, p1, p2, r;  float p_Min;  float p_Max;  float x_Min;  float y_Min;  float z_Min;  float x_Max;  float y_Max;  float z_Max;   // Compute box center and extents of AABoundingBox (if not already given in that format)  //Vector3 centre = (b.Max + b.Min) * 0.5f;  Vector3 v0 = tri.A;  Vector3 v1 = tri.B;  Vector3 v2 = tri.C;  // Translate triangle as conceptually moving AABB to origin  v0 = v0 - this.Centre;  v1 = v1 - this.Centre;  v2 = v2 - this.Centre;  // Compute edge vectors for triangle  Vector3 f0 = v1 - v0;  Vector3 f1 = v2 - v1;  Vector3 f2 = v0 - v2;  // Test axes a00..a22 (category 3)  Vector3 a00 = new Vector3(0, -f0.Z, f0.Y);  Vector3 a01 = new Vector3(0, -f1.Z, f1.Y);  Vector3 a02 = new Vector3(0, -f2.Z, f2.Y);  Vector3 a10 = new Vector3(f0.Z, 0, -f0.X);  Vector3 a11 = new Vector3(f1.Z, 0, -f1.X);  Vector3 a12 = new Vector3(f2.Z, 0, -f2.X);  Vector3 a20 = new Vector3(-f0.Y, f0.X, 0);  Vector3 a21 = new Vector3(-f1.Y, f1.X, 0);  Vector3 a22 = new Vector3(-f2.Y, f2.X, 0);  // Test axis a00  p0 = Vector3.Dot(v0, a00);  p1 = Vector3.Dot(v1, a00);  p2 = Vector3.Dot(v2, a00);  //Vector3 cross = Vector3.Cross(tri.Normal, a00);  //if (Math.Abs(cross.X) < GameConstants.EPSILON && Math.Abs(cross.Y) < GameConstants.EPSILON && Math.Abs(cross.Z) < GameConstants.EPSILON)  //{  //    return result;  //}  // p0 Always = p1;  //if (p0 != p1)  //{  //    Console.WriteLine("P0 " + p0 + " P1 " + p1);  //}  r = this.Extents.Y * Math.Abs(f0.Z) + this.Extents.Z * Math.Abs(f0.Y);  //Console.WriteLine("Radius(a00) = " + r);  if (Math.Max(-Math.Max(p0, p2), Math.Min(p0, p2)) > r)  { return result; // Axis is a separating axis  }  // Test axis a01 (a01 = new Vector3(0, -f1.Z, f1.Y))  p0 = Vector3.Dot(v0, a01);  p1 = Vector3.Dot(v1, a01);  p2 = Vector3.Dot(v2, a01);  //Console.WriteLine("P0 " + p0 + " P1 " + p1 + " P2 " + p2);  //if (p2 != p1) p2 always = p1??  //{  //    Console.WriteLine("P2 " + p2 + " P1 " + p1);  //}  r = this.Extents.Y * Math.Abs(f1.Z) + this.Extents.Z * Math.Abs(f1.Y);  //Console.WriteLine("Radius(a01) = " + r);  // [-r, r] and [min(p0, p1, p2), max(p0, p1, p2)] should be disjoint for this axis  p_Min = Math.Min(p0, p1);  p_Min = Math.Min(p_Min, p2);  p_Max = Math.Max(p0, p1);  p_Max = Math.Max(p_Max, p2);  if (Math.Max(-p_Max, p_Min) > r)  { return result; // Axis is a separating axis  }  // Test axis a02 (a02 = new Vector3(0, -f2.Z, f2.Y))  p0 = Vector3.Dot(v0, a02);  p1 = Vector3.Dot(v1, a02);  p2 = Vector3.Dot(v2, a02);  r = this.Extents.Y * Math.Abs(f2.Z) + this.Extents.Z * Math.Abs(f2.Y);  //Console.WriteLine("Radius(a02) = " + r);  // [-r, r] and [min(p0, p1, p2), max(p0, p1, p2)] should be disjoint for this axis  p_Min = Math.Min(p0, p1);  p_Min = Math.Min(p_Min, p2);  p_Max = Math.Max(p0, p1);  p_Max = Math.Max(p_Max, p2);  if (Math.Max(-p_Max, p_Min) > r)  { return result; // Axis is a separating axis  }  // Test axis a10 (a10 = new Vector3(f0.Z, 0, -f0.X))  p0 = Vector3.Dot(v0, a10);  p1 = Vector3.Dot(v1, a10);  p2 = Vector3.Dot(v2, a10);  r = this.Extents.X * Math.Abs(f0.Z) + this.Extents.Z * Math.Abs(f0.X);  //Console.WriteLine("Radius(a10) = " + r);  // [-r, r] and [min(p0, p1, p2), max(p0, p1, p2)] should be disjoint for this axis  p_Min = Math.Min(p0, p1);  p_Min = Math.Min(p_Min, p2);  p_Max = Math.Max(p0, p1);  p_Max = Math.Max(p_Max, p2);  if (Math.Max(-p_Max, p_Min) > r)  { return result; // Axis is a separating axis  }  // Test axis a11 (a11 = new Vector3(f1.Z, 0, -f1.X))  p0 = Vector3.Dot(v0, a11);  p1 = Vector3.Dot(v1, a11);  p2 = Vector3.Dot(v2, a11);  r = this.Extents.X * Math.Abs(f1.Z) + this.Extents.Z * Math.Abs(f1.X);  //Console.WriteLine("Radius(a11) = " + r);  // [-r, r] and [min(p0, p1, p2), max(p0, p1, p2)] should be disjoint for this axis  p_Min = Math.Min(p0, p1);  p_Min = Math.Min(p_Min, p2);  p_Max = Math.Max(p0, p1);  p_Max = Math.Max(p_Max, p2);  if (Math.Max(-p_Max, p_Min) > r)  { return result; // Axis is a separating axis  }  // Test axis a12 (a12 = new Vector3(f2.Z, 0, -f2.X))  p0 = Vector3.Dot(v0, a12);  p1 = Vector3.Dot(v1, a12);  p2 = Vector3.Dot(v2, a12);  r = this.Extents.X * Math.Abs(f2.Z) + this.Extents.Z * Math.Abs(f2.X);  //Console.WriteLine("Radius(a12) = " + r);  // [-r, r] and [min(p0, p1, p2), max(p0, p1, p2)] should be disjoint for this axis  p_Min = Math.Min(p0, p1);  p_Min = Math.Min(p_Min, p2);  p_Max = Math.Max(p0, p1);  p_Max = Math.Max(p_Max, p2);  if (Math.Max(-p_Max, p_Min) > r)  { return result; // Axis is a separating axis  }  // Test axis a20 (a20 = new Vector3(-f0.Y, -f0.X, 0))  p0 = Vector3.Dot(v0, a20);  p1 = Vector3.Dot(v1, a20);  p2 = Vector3.Dot(v2, a20);  r = this.Extents.X * Math.Abs(f0.Y) + this.Extents.Y * Math.Abs(f0.X);  //Console.WriteLine("Radius(a20) = " + r);  // [-r, r] and [min(p0, p1, p2), max(p0, p1, p2)] should be disjoint for this axis  p_Min = Math.Min(p0, p1);  p_Min = Math.Min(p_Min, p2);  p_Max = Math.Max(p0, p1);  p_Max = Math.Max(p_Max, p2);  if (Math.Max(-p_Max, p_Min) > r)  { return result; // Axis is a separating axis  }  // Test axis a21 (a21 = new Vector3(-f1.Y, -f1.X, 0))  p0 = Vector3.Dot(v0, a21);  p1 = Vector3.Dot(v1, a21);  p2 = Vector3.Dot(v2, a21);  r = this.Extents.X * Math.Abs(f1.Y) + this.Extents.Y * Math.Abs(f1.X);  //Console.WriteLine("Radius(a21) = " + r);  // [-r, r] and [min(p0, p1, p2), max(p0, p1, p2)] should be disjoint for this axis  p_Min = Math.Min(p0, p1);  p_Min = Math.Min(p_Min, p2);  p_Max = Math.Max(p0, p1);  p_Max = Math.Max(p_Max, p2);  if (Math.Max(-p_Max, p_Min) > r)  { return result; // Axis is a separating axis  }  // Test axis a22 (a22 = new Vector3(-f2.Y, -f2.X, 0))  p0 = Vector3.Dot(v0, a22);  p1 = Vector3.Dot(v1, a22);  p2 = Vector3.Dot(v2, a22);  r = this.Extents.X * Math.Abs(f2.Y) + this.Extents.Y * Math.Abs(f2.X);  //Console.WriteLine("Radius(a22) = " + r);  // [-r, r] and [min(p0, p1, p2), max(p0, p1, p2)] should be disjoint for this axis  p_Min = Math.Min(p0, p1);  p_Min = Math.Min(p_Min, p2);  p_Max = Math.Max(p0, p1);  p_Max = Math.Max(p_Max, p2);  if (Math.Max(-p_Max, p_Min) > r)  { return result; // Axis is a separating axis  }  // Test the three axes corresponding to the face normals of AABB b (category 1).  x_Max = Math.Max(v0.X, v1.X);  x_Max = Math.Max(x_Max, v2.X);  x_Min = Math.Min(v0.X, v1.X);  x_Min = Math.Min(x_Min, v2.X);  y_Max = Math.Max(v0.Y, v1.Y);  y_Max = Math.Max(y_Max, v2.Y);  y_Min = Math.Min(v0.Y, v1.Y);  y_Min = Math.Min(y_Min, v2.Y);  z_Max = Math.Max(v0.Z, v1.Z);  z_Max = Math.Max(z_Max, v2.Z);  z_Min = Math.Min(v0.Z, v1.Z);  z_Min = Math.Min(z_Min, v2.Z);  // Exit if [-e0, e0] and [min(v0.x,v1.x,v2.x), max(v0.x,v1.x,v2.x)] do not overlap  if (x_Max < -this.Extents.X || x_Min > this.Extents.X)  { return result;  }  // ... [-e1, e1] and [min(v0.y,v1.y,v2.y), max(v0.y,v1.y,v2.y)] do not overlap  if (y_Max < -this.Extents.Y || y_Min > this.Extents.Y)  { return result;  }  // ... [-e2, e2] and [min(v0.z,v1.z,v2.z), max(v0.z,v1.z,v2.z)] do not overlap  if (z_Max < -this.Extents.Z || z_Min > this.Extents.Z)  { return result;  }  // Test separating axis corresponding to triangle face normal (category 2)  Plane p;  p.Normal = tri.Normal; // Vector3.Cross(f0, f1);  p.Normal.Normalize();  // Make Normal (n) a unit vector  // Must create Plane.D from ORIGINAL Triangle Points (if projected v0 then AABB should be centred at origin first [centre_Origin])  p.D = Vector3.Dot(p.Normal, v0);  float radius;  float distance;  float time;  Vector3 point_Intersection;  if (TestAABBPlane(p, out radius, out distance, out time, out point_Intersection))  { result.isColliding = true;// There is a collision // If current distance to the Plane is closer than previous results, allow CollisionResult to be updated with new parameters if (result.KeepEarliest(time)) {result.isClosest = true;result.distance = distance; // - radius to remove need for result.radiusresult.normal = p.Normal;result.radius = radius;result.time = time; }    }  return result;   }I can't figure out why this isn't working and why it would consider Triangle1 to have a collision time of 0 when the AABB is also colliding with Triangle2?Any ideas folks? (Have I implemented the time of collision correctly?)   ;  hm... haven't have time to look deep into ur code, but it seems that the distance calculation is wrong??? its probably justdistance = Vector3.Dot(any_point_on_the_plane - this.Centre, p.Normal);btw, i guess ur AABBTriangle test is wrong toothe site of the book 3d game engine design contains some useful documentation, clicky, they should cover all ur needs;  The test for intersection between AABB and Triangle is working correctly.  If I have just one Triangle of any shape or size and test it against an AABB then it will detect intersections with a frightengly good degree of accuracy.I should hope that this test was correct too, otherwise the highly recommended orange book Realtime Collision Detection (Christer Ericson) would not be so.The fundamental problem of this test from my point of view is that when 2 Triangles occupy a same point along one of their axes the test will return positive for an intersection for both Triangles.This is correct in terms of intersection, but I require a way of differentiating between the 2 Triangles.As they are both intersected at the same time then finding the time between intersections does not help in this case.So I throw myself at the mercy of the experts on these forums to suggest a way that I can differentiate between the 2 Triangles in a meaningful way.Thank you.EDIT:  I think a big part of the problem which HellKnows2008 touched on is the Plane intersection method.  Whilst the method is correct, it also tests for an intersection on both sides of a Plane.How could I change this to only test for a collision on one side of the Plane?   ;  if u look for some solid working example, look at here, inside the first reply, u should find an archive which can demonstrate some SAT stuff (taken velocity into account), all credits go to oliii'sjust a side note, the aabb triangle test code is almost unreadable (though maybe optimized, but remember premature optimization is the root of all evils), and apart from aabbplane test, seems that other tests do not take velocity into account, and its not gonna return useful results when those cases are hitthe following is my obb tri swept test code, i guess its a bit clearerboolCD::OBBTriangle(const Vec3& obb_center, const Vec3 obb_eaxis[3], const Vec3& obb_velocity, const Vec3& v0, const Vec3& v1, const Vec3& v2, REAL& t0, REAL& t1, Vec3* first_time_contact_axis, Vec3* last_time_contact_axis){t0 = -INFINITY;t1 = INFINITY;Vec3 e0 = v1 - v0;Vec3 e1 = v2 - v1;Vec3 tri_nor = e0 ^ e1;// triangle face normalif(!SAT::cd_1axis_moving_obb_tri(SAT::stablize_axis(tri_nor), obb_center, obb_eaxis, obb_velocity, v0, v1, v2, t0, t1, first_time_contact_axis, last_time_contact_axis))return false;// obb faces' axisif(!SAT::cd_1axis_moving_obb_tri(SAT::stablize_axis(obb_eaxis[0]), obb_center, obb_eaxis, obb_velocity, v0, v1, v2, t0, t1, first_time_contact_axis, last_time_contact_axis))return false;if(!SAT::cd_1axis_moving_obb_tri(SAT::stablize_axis(obb_eaxis[1]), obb_center, obb_eaxis, obb_velocity, v0, v1, v2, t0, t1, first_time_contact_axis, last_time_contact_axis))return false;if(!SAT::cd_1axis_moving_obb_tri(SAT::stablize_axis(obb_eaxis[2]), obb_center, obb_eaxis, obb_velocity, v0, v1, v2, t0, t1, first_time_contact_axis, last_time_contact_axis))return false;Vec3 e2 = v0 - v2;// cross products of edges from bothif(!SAT::cd_1axis_moving_obb_tri(SAT::stablize_axis(e0 ^ obb_eaxis[0]), obb_center, obb_eaxis, obb_velocity, v0, v1, v2, t0, t1, first_time_contact_axis, last_time_contact_axis))return false;if(!SAT::cd_1axis_moving_obb_tri(SAT::stablize_axis(e1 ^ obb_eaxis[0]), obb_center, obb_eaxis, obb_velocity, v0, v1, v2, t0, t1, first_time_contact_axis, last_time_contact_axis))return false;if(!SAT::cd_1axis_moving_obb_tri(SAT::stablize_axis(e2 ^ obb_eaxis[0]), obb_center, obb_eaxis, obb_velocity, v0, v1, v2, t0, t1, first_time_contact_axis, last_time_contact_axis))return false;if(!SAT::cd_1axis_moving_obb_tri(SAT::stablize_axis(e0 ^ obb_eaxis[1]), obb_center, obb_eaxis, obb_velocity, v0, v1, v2, t0, t1, first_time_contact_axis, last_time_contact_axis))return false;if(!SAT::cd_1axis_moving_obb_tri(SAT::stablize_axis(e1 ^ obb_eaxis[1]), obb_center, obb_eaxis, obb_velocity, v0, v1, v2, t0, t1, first_time_contact_axis, last_time_contact_axis))return false;if(!SAT::cd_1axis_moving_obb_tri(SAT::stablize_axis(e2 ^ obb_eaxis[1]), obb_center, obb_eaxis, obb_velocity, v0, v1, v2, t0, t1, first_time_contact_axis, last_time_contact_axis))return false;if(!SAT::cd_1axis_moving_obb_tri(SAT::stablize_axis(e0 ^ obb_eaxis[2]), obb_center, obb_eaxis, obb_velocity, v0, v1, v2, t0, t1, first_time_contact_axis, last_time_contact_axis))return false;if(!SAT::cd_1axis_moving_obb_tri(SAT::stablize_axis(e1 ^ obb_eaxis[2]), obb_center, obb_eaxis, obb_velocity, v0, v1, v2, t0, t1, first_time_contact_axis, last_time_contact_axis))return false;if(!SAT::cd_1axis_moving_obb_tri(SAT::stablize_axis(e2 ^ obb_eaxis[2]), obb_center, obb_eaxis, obb_velocity, v0, v1, v2, t0, t1, first_time_contact_axis, last_time_contact_axis))return false;if(t0 > t1)return false;return true;}boolSAT::cd_1axis_moving_obb_tri(const Vec3& axis, const Vec3& obb_center, const Vec3 array_obb_eaxis[3], const Vec3& obb_velocity, const Vec3& v0, const Vec3& v1, const Vec3& v2, REAL& t0, REAL& t1, Vec3* first_time_contact_axis, Vec3* last_time_contact_axis){REAL min0, max0, min1, max1, temp;REAL obb_radius = FABS(array_obb_eaxis[0] * axis) + FABS(array_obb_eaxis[1] * axis) + FABS(array_obb_eaxis[2] * axis);temp = obb_center * axis;min0 = temp - obb_radius;max0 = temp + obb_radius;min1 = max1 = v0 * axis;min1 = min(min1, temp = v1 * axis);max1 = max(max1, temp);min1 = min(min1, temp = v2 * axis);max1 = max(max1, temp);REAL delta = obb_velocity * axis;if(FABS(delta) < EPSILON)return !test_intervals_sep(min0, max0, min1, max1);REAL inv_delta = 1.0f / delta;REAL mini = (min1 - max0) * inv_delta;REAL maxi = (max1 - min0) * inv_delta;SORT(mini, maxi);if(first_time_contact_axis && mini > t0)*first_time_contact_axis = axis;if(last_time_contact_axis && maxi < t1)*last_time_contact_axis = axis;t0 = max(t0, mini);t1 = min(t1, maxi);return true;}boolSAT::test_intervals_sep(REAL min0, REAL max0, REAL min1, REAL max1){return (min0 > max1 || min1 > max0);}