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.
I noticed a small bug in this implementation which leads to false negatives. If your triangle has one edge parallel to one axis (for example (1, 0, 0)), then you will have a null vector when computing
triangleEdges[i].Cross(boxNormals[j])
This will lead to equality in the test below and give you a false negative.
replace <= and >= by < and > at line
if (boxMax <= triangleMin || boxMin >= triangleMax)
(strict comparers to remove those cases).
Works well except for that!
Thank you
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++)
{
IVector n = boxNormals[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). None of the faces can be used as a separating plane, yet they do not intersect. The separating axis is <1,1,0>, which is obtained from the cross product between <1,0,0> and <-3,3,0>.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With