Intersection efficace AABB / sortingangle en C #

Quelqu’un peut-il recommander un port efficace à CSharp de n’importe lequel des algorithmes d’intersection AABB / sortingangle publics.

J’ai examiné l’approche de Moller, décrite de manière abstraite ici , et si je la portais, je partirais probablement de cette version C ++ . Cette bibliothèque C ++ de Mike Vandelay semble constituer un excellent sharepoint départ.

… ou … toute autre “roue” pouvant prendre un sortingangle de Vector3 et me dire si elle croise un AABB), de manière relativement efficace.

Il semble y avoir une variété d’algorithmes, mais la plupart semblent être écrits en c ++, ou juste décrits de façon abstraite dans des livres blancs et j’ai besoin d’une implémentation spécifique à ac # pour notre application. L’efficacité n’est pas la clé, mais c # l’est. (bien que l’efficacité soit évidemment belle aussi bien sûr; p)

Toute option C #, avant de parcourir un portage “mathématique”;) serait grandement appréciée! Merci.

Pour savoir si deux maillages convexes se croisent, vous devez vérifier s’il existe un plan de séparation. Si c’est le cas, ils ne se croisent pas. Le plan peut être sélectionné à partir de n’importe quelle face de forme ou de produit croisé.

Le plan est défini comme une normale et un décalage par rapport à Origo. Il suffit donc de vérifier trois faces de l’AABB et une face du sortingangle.

bool IsIntersecting(IAABox box, ITriangle sortingangle) { double sortingangleMin, sortingangleMax; 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 sortingangle normal double sortingangleOffset = sortingangle.Normal.Dot(sortingangle.A); Project(box.Vertices, sortingangle.Normal, out boxMin, out boxMax); if (boxMax < triangleOffset || boxMin > sortingangleOffset) return false; // No intersection possible. // Test the nine edge cross-products IVector[] sortingangleEdges = new IVector[] { sortingangle.A.Minus(sortingangle.B), sortingangle.B.Minus(sortingangle.C), sortingangle.C.Minus(sortingangle.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 >= sortingangleMax) 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; } }

Un bon exemple est la boîte (± 10, ± 10, ± 10) et le sortingangle (12,9,9), (9,12,9), (19,19,20). Aucune des faces ne peut être utilisée comme plan de séparation, mais elles ne se croisent pas. L’axe de séparation est <1,1,0>, qui est obtenu à partir du produit croisé entre <1,0,0> et <-3,3,0>.

Graphique

J’ai remarqué un petit bug dans cette implémentation qui conduit à de faux négatifs. Si votre sortingangle a un bord parallèle à un axe (par exemple (1, 0, 0)), vous aurez un vecteur nul lors du calcul

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

Cela conduira à l’égalité dans le test ci-dessous et vous donnera un faux négatif.

remplacez <= et> = par à la ligne

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

(comparateurs ssortingcts pour éliminer ces cas).

Fonctionne bien sauf pour ça!

Je vous remercie