在C#高效AABB /三角形相交 [英] Efficient AABB/triangle intersection in C#
问题描述
谁能推荐任何公共AABB /三角形相交算法的高效端口CSHARP。
Can anyone recommend an efficient port to CSharp of any of the public AABB/triangle intersection algorithms.
我一直在寻找穆勒的做法,抽象描述的此处,如果我是将它移植,我可能会从的这个C ++版本。的这个C由Mike Vandelay ++库好像它也可能是一个很好的起点。
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.
...或...任何其他的车轮,可以采取Vector3类型的一个三角形,并告诉我,如果将其与AABB相交),相对有效。
...or... any other "wheel" that can take a triangle of Vector3's and tell me if it intersects with an AABB), relatively efficiently.
似乎有不同的算法,但多数似乎是用C ++编写,或者只是在白皮书中描述抽象的,我需要交流#具体的实施为我们的应用程序。效率不是关键,但C#是。 (虽然效率显然是很好过的课程; P)
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 )
任何C#的选择,之前我涉水通过数学端口;)将大大AP preciated!谢谢你。
Any C# options, before I wade through a "math" port ;) would be greatly appreciated! Thanks.
推荐答案
对于任何两个凸目,发现他们是否相交,则需要检查是否存在分离平面。如果是这样,他们不相交。该平面可以从任何面任一形状的,或边缘交叉的产品被拾取
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.
的平面被定义为一个正常的和从欧瑞偏移。所以,你只需要检查三个面的AABB,以及一个面三角形的。
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; }
}
一个很好的例子是箱(±10,±10,±10)和三角形(12,9,9),(9,12,9),(19,19,20)。没有一个面可以作为一个分离平面,但它们不相交。该分离轴线为&lt; 1,1,0>,它是从交叉乘积得到之间&所述; 1,0,0>和&lt;。-3,3,0>
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>.
这篇关于在C#高效AABB /三角形相交的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!