XNA
Resources |
## Games.DiscoverThat.co.uk |

Home XNA Contents Development Blog

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.