## 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.

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.