XNA
JCBDigger's Guides
XNA
Resources

  Games.DiscoverThat.co.uk

 Home  XNA Contents  Development Blog

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.


See also, other sites hosted here.    All content ©copyright 2009