   AABB Triangle/Plane Intersection.  Distance to plane is incorrect? [I have solved it]
  I am using XNA with code adapted from Christer Ericson's Real Time Collision.I understand that in XNA, the z axis is reversed from the code found the aforementioned book, is this correct?  Sorry to sound a bit vague but what I mean is that if you view [-ve x] going left and [+ve x] going right then [-ve Z] on XNA goes into the screen as opposed to towards to viewing eye.The triangles I have used in the following example are all clockwise winding, as such when creating a Plane the Plane.Normal is reversed.The problem I am having is that the distance (s) NEVER falls within [-r,+r] interval.Here is the C# code for the AABB Triangle Collision:   public static float? TestAABBTriangle(BoundingBox b, Triangle tri)   {  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 c = (b.Min + b.Max) * 0.5f;  float e0 = (b.Max.X - b.Min.X) * 0.5f;  float e1 = (b.Max.Y - b.Min.Y) * 0.5f;  float e2 = (b.Max.Z - b.Min.Z) * 0.5f;  Vector3 v0 = tri.P0;  Vector3 v1 = tri.P1;  Vector3 v2 = tri.P2;  // Translate triangle as conceptually moving AABB to origin  v0 = v0 - c;  v1 = v1 - c;  v2 = v2 - c;  // Compute edge vectors for triangle  Vector3 f0 = v1 - v0;  Vector3 f1 = v2 - v1;  Vector3 f2 = v0 - v2;  // Test axes a00..a22 (category 3)  // Test axis a00  p0 = v0.Z * v1.Y - v0.Y * v1.Z;  p2 = v2.Z * (v1.Y - v0.Y) - v2.Z*(v1.Z - v0.Z);  r = e1 * Math.Abs(f0.Z) + e2 * Math.Abs(f0.Y);  if (Math.Max(-Math.Max(p0, p2), Math.Min(p0, p2)) > r)  { return 0; // Axis is a separating axis  }  // Test axis a01 (a01 = new Vector3(0, -f1.Z, f1.Y))  p0 = Vector3.Dot(v0, new Vector3(0, -f1.Z, f1.Y));  p1 = Vector3.Dot(v1, new Vector3(0, -f1.Z, f1.Y));  p2 = Vector3.Dot(v2, new Vector3(0, -f1.Z, f1.Y));  //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 0; // Axis is a separating axis  }  // Test axis a02 (a02 = new Vector3(0, -f2.Z, f2.Y))  p0 = Vector3.Dot(v0, new Vector3(0, -f2.Z, f2.Y));  p1 = Vector3.Dot(v1, new Vector3(0, -f2.Z, f2.Y));  p2 = Vector3.Dot(v2, new Vector3(0, -f2.Z, f2.Y));  //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 0; // Axis is a separating axis  }  // Test axis a10 (a10 = new Vector3(f0.Z, 0, -f0.X))  p0 = Vector3.Dot(v0, new Vector3(f0.Z, 0, -f0.X));  p1 = Vector3.Dot(v1, new Vector3(f0.Z, 0, -f0.X));  p2 = Vector3.Dot(v2, new Vector3(f0.Z, 0, -f0.X));  //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 0; // Axis is a separating axis  }  // Test axis a11 (a11 = new Vector3(f1.Z, 0, -f1.X))  p0 = Vector3.Dot(v0, new Vector3(f1.Z, 0, -f1.X));  p1 = Vector3.Dot(v1, new Vector3(f1.Z, 0, -f1.X));  p2 = Vector3.Dot(v2, new Vector3(f1.Z, 0, -f1.X));  //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 0; // Axis is a separating axis  }  // Test axis a12 (a12 = new Vector3(f2.Z, 0, -f2.X))  p0 = Vector3.Dot(v0, new Vector3(f2.Z, 0, -f2.X));  p1 = Vector3.Dot(v1, new Vector3(f2.Z, 0, -f2.X));  p2 = Vector3.Dot(v2, new Vector3(f2.Z, 0, -f2.X));  //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 0; // Axis is a separating axis  }  // Test axis a20 (a20 = new Vector3(-f0.Y, -f0.X, 0))  p0 = Vector3.Dot(v0, new Vector3(-f0.Y, -f0.X, 0));  p1 = Vector3.Dot(v1, new Vector3(-f0.Y, -f0.X, 0));  p2 = Vector3.Dot(v2, new Vector3(-f0.Y, -f0.X, 0));  //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 0; // Axis is a separating axis  }  // Test axis a21 (a21 = new Vector3(-f1.Y, -f1.X, 0))  p0 = Vector3.Dot(v0, new Vector3(-f1.Y, -f1.X, 0));  p1 = Vector3.Dot(v1, new Vector3(-f1.Y, -f1.X, 0));  p2 = Vector3.Dot(v2, new Vector3(-f1.Y, -f1.X, 0));  //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 0; // Axis is a separating axis  }  // Test axis a22 (a22 = new Vector3(-f2.Y, -f2.X, 0))  p0 = Vector3.Dot(v0, new Vector3(-f2.Y, -f2.X, 0));  p1 = Vector3.Dot(v1, new Vector3(-f2.Y, -f2.X, 0));  p2 = Vector3.Dot(v2, new Vector3(-f2.Y, -f2.X, 0));  //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 0; // 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 < -e0 || x_Min > e0)  { return 0;  }  // ... [-e1, e1] and [min(v0.y,v1.y,v2.y), max(v0.y,v1.y,v2.y)] do not overlap  if (y_Max < -e1 || y_Min > e1)  { return 0;  }  // ... [-e2, e2] and [min(v0.z,v1.z,v2.z), max(v0.z,v1.z,v2.z)] do not overlap  if (z_Max < -e2 || z_Min > e2)  { return 0;  }  // Test separating axis corresponding to triangle face normal (category 2)  // Face Normal is -ve as Triangle is clockwise winding (and XNA uses -z for into screen)  Plane p;  p.Normal = -Vector3.Cross(f0, f1);  p.Normal.Normalize();  p.D = Vector3.Dot(p.Normal, v0);  return TestAABBPlane(b, p);   }Is the Plane being created correctly here (in the case of XNA)?Are the edge Vectors correct with the current clockwise winding and opposite z axis value?  // Compute edge vectors for triangle  Vector3 f0 = v1 - v0;  Vector3 f1 = v2 - v1;  Vector3 f2 = v0 - v2;If all this IS correct, then why can't I return the distance s in the follow test between the newly created Plane and the AABB?   // Test if AABB (Axis Aligned Bounding Box) b intersects plane p   private static float? TestAABBPlane(BoundingBox b, Plane p)   {  // These two lines not necessary with a (center, extents) AABB representation  Vector3 centre = (b.Max + b.Min) * 0.5f; // Compute AABB center  Vector3 e = b.Max - centre; // Compute positive extents  // Compute the projection interval radius of b onto L(t) = b.c + t * p.n  float r = e.X * Math.Abs(p.Normal.X) + e.Y * Math.Abs(p.Normal.Y) + e.Z * Math.Abs(p.Normal.Z);  // Compute distance (s) of box center from plane  float s = Vector3.Dot(p.Normal, centre) - p.D;  Console.WriteLine("Distance " + s);  // Intersection occurs when distance s falls within [-r,+r] interval  if (Math.Abs(s) <= r)  { return s;  // NEVER OCCURS WITH CURRENT SETUP  }  else  { return null;  }   }The good news is that the TestAABBPlane function is only called when my AABB intersects the triangle so I know that I have coded it correctly.However, the value for s is way too large and I'm sure this boils down to something to do with the winding of the triangle, the reversal of the z axis and the normalization of the Normals.Can anyone help with this please?Thank you.[Large amounts of code go in source tags rather than code tags, please - Zahlman][Edited by - Spa8nky on May 13, 2009 8:02:23 PM]
  The handedness of the coordinate system shouldn't matter in this case. It shouldn't hurt anything to flip the normal, but it shouldn't be necessary either.Also, just as a side note, the separating axis test can be set up so as not to require any vector normalizations (a small optimization, but worth being aware of).I didn't spot anything particularly suspicious in your code - have you tried stepping through the AABB-plane function in the debugger? I'd suggest setting up a simple test case with a known outcome (say, an axis-aligned plane with the box placed some number of units away from the plane), and then stepping through the code to try and determine why the value of 's' is coming out wrong (you might also double check that the box projected radius is being computed correctly).   ;  I have created a AABB (cube for simplicity) of radius 2.In the TestAABBPlane obtaining the AABB radius using the following method returns 20000.  // Compute the projection interval radius of b onto L(t) = b.c + t * p.n  float r = e.X * Math.Abs(p.Normal.X) + e.Y * Math.Abs(p.Normal.Y) + e.Z * Math.Abs(p.Normal.Z);  Console.WriteLine("Radius [Plane Method] " + r);Incidently if I normalize the Plane.Normal then the above method returns 2.[a00]:r = e1 * Math.Abs(f0.Z) + e2 * Math.Abs(f0.Y);Radius for (a00) returns: 200[a01]:r = e1 * Math.Abs(f1.Z) + e2 * Math.Abs(f1.Y);Radius for (a01) returns: 200[a02]:r = e1 * Math.Abs(f2.Z) + e2 * Math.Abs(f2.Y);Radius for (a02) returns: 0 ?![a10]:r = e0 * Math.Abs(f0.Z) + e2 * Math.Abs(f0.X);Radius for (a10) returns: 0 ?![a11]:r = e0 * Math.Abs(f1.Z) + e2 * Math.Abs(f1.X);Radius for (a11) returns: 200[a12]:r = e0 * Math.Abs(f2.Z) + e2 * Math.Abs(f2.X);Radius for (a12) returns: 200[a20]:r = e0 * Math.Abs(f0.Y) + e1 * Math.Abs(f0.X);Radius for (a20) returns: 200[a21]:r = e0 * Math.Abs(f1.Y) + e1 * Math.Abs(f1.X);Radius for (a21) returns: 400 ?![a22]:r = e0 * Math.Abs(f2.Y) + e1 * Math.Abs(f2.X);Radius for (a22) returns: 200Distance (s) of box center from plane (when intersecting) is around:-80000 ?!?!?!?!What on Earth is happening here folks?   ;  Problem solved.The code in the book suggested that I should use the projected point in the creation of the Plane.I have discovered this to be incorrect and by using the original triangle point instead then I have the correct result for the distance: p.D = Vector3.Dot(p.Normal, v0);BECOMES:  // Must create Plane.D from ORIGINAL Triangle Points (not translated v0)  p.D = Vector3.Dot(p.Normal, tri.P0);Hope that is of use to someone using XNA!   