C＃中高效的AABB /三角交叉

任何人都可以推荐任何公共AABB /三角交叉算法的CSharp高效端口。

我一直在看Moller的方法， 在这里抽象地描述，如果我要移植它，我可能会从这个C ++版本开始 。 Mike Vandelay的这个C ++库似乎也是一个很好的起点。

……或者……任何其他“轮子”可以采用Vector3的三角形并告诉我它是否与AABB相交，相对有效。

似乎有各种各样的算法，但大多数似乎是用c ++编写的，或者只是在白皮书中抽象地描述，我需要针对我们的应用程序的ac＃特定实现。 效率不是关键，但c＃是。 （虽然效率当然也很好; p）

任何C＃选项，在我通过“数学”端口之前;）将不胜感激！ 谢谢。

Answer 1

对于任何两个凸网格，要查找它们是否相交，您需要检查是否存在分离平面。 如果是，它们不相交。 可以从任何形状的任何面或边缘交叉产品中挑选平面。

平面定义为法线和偏离Origo。 因此，您只需要检查AABB的三个面和三角形的一个面。

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 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 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）。 没有任何面可以用作分离平面，但它们不相交。 分离轴<1,1.0>，其从<1,0,0>和<-3,3,0>之间的叉积获得。

Answer 2

我注意到这个实现中的一个小错误会导致漏报。 如果您的三角形有一条平行于一个轴的边（例如（1,0,0）），那么在计算时您将得到一个空向量

 triangleEdges[i].Cross(boxNormals[j]) 

这将导致下面的测试中的平等，并给你一个假阴性。

在行处用<和>替换<=和> =

  if (boxMax <= triangleMin || boxMin >= triangleMax) 

（删除那些案件的严格比较）。

除此之外，效果很好！

谢谢