Friday 5 February 2010

XNA Triangle Intersections to Ray and Sphere

I have converted examples of Ray to Triangle and BoundingSphere to Triangle intersections available on the Internet in to a XNA C# triangle class. It also includes a few other triangle related methods.

Download Source Code

Triangle XNA class (4kb) Feb. 2010

The triangle uses an array of Vector3's for the corner points.

public Triangle()
{
 Vertex = new Vector3[3];
 Vertex[0] = Vector3.Zero;
 Vertex[1] = Vector3.Zero;
 Vertex[2] = Vector3.Zero;
}

The Intersect Ray method is from the Creators club picking with triangle accuracy sample.


// Returns the distance from the origin of the ray to the intersection with 
// the triangle, null if no intersect and negative if behind.
public void Intersects(ref Ray ray, out float? distance)
{
 // Set the Distance to indicate no intersect
 distance = null;
 // Compute vectors along two edges of the triangle.
 Vector3 edge1, edge2;

 Vector3.Subtract(ref Vertex[2], ref Vertex[1], out edge1);
 Vector3.Subtract(ref Vertex[0], ref Vertex[1], out edge2);

 // Compute the determinant.
 Vector3 directionCrossEdge2;
 Vector3.Cross(ref ray.Direction, ref edge2, out directionCrossEdge2);

 float determinant;
 Vector3.Dot(ref edge1, ref directionCrossEdge2, out determinant);

 // If the ray is parallel to the triangle plane, there is no collision.
 if (determinant > -float.Epsilon && determinant < float.Epsilon)
 {
  return;
 }

 float inverseDeterminant = 1.0f / determinant;

 // Calculate the U parameter of the intersection point.
 Vector3 distanceVector;
 Vector3.Subtract(ref ray.Position, ref Vertex[1], out distanceVector);

 float triangleU;
 Vector3.Dot(ref distanceVector, ref directionCrossEdge2, out triangleU);
 triangleU *= inverseDeterminant;

 // Make sure it is inside the triangle.
 if (triangleU < 0 || triangleU > 1)
 {
  return;
 }

 // Calculate the V parameter of the intersection point.
 Vector3 distanceCrossEdge1;
 Vector3.Cross(ref distanceVector, ref edge1, out distanceCrossEdge1);

 float triangleV;
 Vector3.Dot(ref ray.Direction, ref distanceCrossEdge1, out triangleV);
 triangleV *= inverseDeterminant;

 // Make sure it is inside the triangle.
 if (triangleV < 0 || triangleU + triangleV > 1)
 {
  return;
 }

 // == By here the ray must be inside the triangle

 // Compute the distance along the ray to the triangle.
 float length = 0;
 Vector3.Dot(ref edge2, ref distanceCrossEdge1, out length);
 distance = length * inverseDeterminant;
}


The Triangle to sphere intersection is an expensive test compared to other intersections. I only use it to create level files. I do not use it in game.


// This is an expensive test.
// The result is true or false.
public void Intersects(ref BoundingSphere sphere, out bool result)
{
 result = false;
 // First check if any corner point is inside the sphere
 // This is necessary because the other tests can easily miss
 // small triangles that are fully inside the sphere.
 if (sphere.Contains(A) != ContainmentType.Disjoint ||
  sphere.Contains(B) != ContainmentType.Disjoint ||
  sphere.Contains(C) != ContainmentType.Disjoint)
 {
  // A point is inside the sphere
  result = true;
  return;
 }
 // Test the edges of the triangle using a ray
 // If any hit then check the distance to the hit is less than the length of the side
 // The distance from a point of a small triangle inside the sphere coule be longer
 // than the edge of the small triangle, hence the test for points inside above.
 Vector3 side = B - A;
 // Important:  The direction of the ray MUST
 // be normalised otherwise the resulting length 
 // of any intersect is wrong!
 Ray ray = new Ray(A, Vector3.Normalize(side));
 float distSq = 0;
 float? length = null;
 sphere.Intersects(ref ray, out length);
 if (length != null)
 {
  distSq = (float)length * (float)length;
  if (length > 0 && distSq < side.LengthSquared())
  {
   // Hit edge
   result = true;
   return;
  }
 }
 // Stay at A and change the direction to C
 side = C - A;
 ray.Direction = Vector3.Normalize(side);
 length = null;
 sphere.Intersects(ref ray, out length);
 if (length != null)
 {
  distSq = (float)length * (float)length;
  if (length > 0 && distSq < side.LengthSquared())
  {
   // Hit edge
   result = true;
   return;
  }
 }
 // Change to corner B and edge to C
 side = C - B;
 ray.Position = B;
 ray.Direction = Vector3.Normalize(side);
 length = null;
 sphere.Intersects(ref ray, out length);
 if (length != null)
 {
  distSq = (float)length * (float)length;
  if (length > 0 && distSq < side.LengthSquared())
  {
   // Hit edge
   result = true;
   return;
  }
 }
 // If we get this far we are not touching the edges of the triangle
 
 // Calculate the InverseNormal of the triangle from the centre of the sphere
 // Do a ray intersection from the centre of the sphere to the triangle.
 // If the triangle is too small the ray could miss a small triangle inside
 // the sphere hence why the points were tested above.
 ray.Position = sphere.Center;
 // This will always create a vector facing towards the triangle from the 
 // ray starting point.
 InverseNormal(ref ray.Position, out side);
 ray.Direction = side;
 Intersects(ref ray, out length);
 if (length != null && length > 0 && length < sphere.Radius)
 {
  // Hit the surface of the triangle
  result = true;
  return;
 }
 // Only if we get this far have we missed the triangle
 result = false;
}


A good source of intersection code mainly in C/++ and theoretical papers is available from: realtimerendering.com

To get the vertices and triangles from an XNA model:
using XNA 3.1 is available from enchantedage.com
using XNA 4.0 I have a modified version of the above here.

No comments: