Efficient AABB/triangle intersection in C#

Question

Can anyone recommend an efficient port to CSharp of any of the public AABB/triangle intersection algorithms.

I've been looking at Moller's approach, described abstractly here, and if I were to port it, I would probably start from this C++ version. This C++ library by Mike Vandelay seems like it could also be a great starting point.

...or... any other "wheel" that can take a triangle of Vector3's and tell me if it intersects with an AABB), relatively efficiently.

There seem to be a variety of algorithms, but most seem to be written in c++, or just described abstractly in white papers and I need a c# specific implementation for our application. Efficiency is not key, but c# is. (though efficiency is obviously nice too of course ;p )

Any C# options, before I wade through a "math" port ;) would be greatly appreciated! Thanks.

Answer 1

For any two convex meshes, to find whether they intersect, you need to check if there exist a separating plane. If it does, they do not intersect. The plane can be picked from any face of either shape, or the edge cross-products.

The plane is defined as a normal and an offset from Origo. So, you only have to check three faces of the AABB, and one face of the triangle.

bool IsIntersecting(IAABox box, ITriangle triangle)
{
    double triangleMin, triangleMax;
    double boxMin, boxMax;

    // Test the box normals (x-, y- and z-axes)
    var boxNormals = new IVector[] {
        new Vector(1,0,0),
        new Vector(0,1,0),
        new Vector(0,0,1)
    };
    for (int i = 0; i < 3; i++)
    {
        Project(triangle.Vertices, boxNormals[i], out triangleMin, out triangleMax);
        if (triangleMax < box.Start.Coords[i] || triangleMin > box.End.Coords[i])
            return false; // No intersection possible.
    }

    // Test the triangle normal
    double triangleOffset = triangle.Normal.Dot(triangle.A);
    Project(box.Vertices, triangle.Normal, out boxMin, out boxMax);
    if (boxMax < triangleOffset || boxMin > triangleOffset)
        return false; // No intersection possible.

    // Test the nine edge cross-products
    IVector[] triangleEdges = new IVector[] {
        triangle.A.Minus(triangle.B),
        triangle.B.Minus(triangle.C),
        triangle.C.Minus(triangle.A)
    };
    for (int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++)
    {
        // The box normals are the same as it's edge tangents
        IVector axis = triangleEdges[i].Cross(boxNormals[j]);
        Project(box.Vertices, axis, out boxMin, out boxMax);
        Project(triangle.Vertices, axis, out triangleMin, out triangleMax);
        if (boxMax < triangleMin || boxMin > triangleMax)
            return false; // No intersection possible
    }

    // No separating axis found.
    return true;
}

void Project(IEnumerable<IVector> points, IVector axis,
        out double min, out double max)
{
    double min = double.PositiveInfinity;
    double max = double.NegativeInfinity;
    foreach (var p in points)
    {
        double val = axis.Dot(p);
        if (val < min) min = val;
        if (val > max) max = val;
    }
}

interface IVector
{
    double X { get; }
    double Y { get; }
    double Z { get; }
    double[] Coords { get; }
    double Dot(IVector other);
    IVector Minus(IVector other);
    IVector Cross(IVector other);
}

interface IShape
{
    IEnumerable<IVector> Vertices { get; }
}

interface IAABox : IShape
{
    IVector Start { get; }
    IVector End { get; }
}

interface ITriangle : IShape {
    IVector Normal { get; }
    IVector A { get; }
    IVector B { get; }
    IVector C { get; }
}

---

A good example is the box (±10, ±10, ±10) and the triangle (12,9,9),(9,12,9),(19,19,20).

The separating plane is the one where (12,9,9),(9,12,9) is lying and the normal is (-3, -3, 0), so they do not intersect.

The separating axis is <1,1,0>(you can also say that it is (-3, -3, 0)), which is obtained from the cross product between <0,0,1> and <-3,3,0>.