SAT test for Triangle - convex hull

Question

I'm having real trouble resolving this issue with triangle-convex hull SAT test intersection.

The problem is as follows:

Misses are detected accurately enough:

Clear miss

I have not found a problem with false negatives (ie collision is there but not detected).

But I do have a problem with false positives (collision detected even though there is not one)

Appears to detect false +

This only happens occasionally with orientations like the one shown (that is actually a pretty big gap).

What I'm doing conceptually is just a usual SAT test for the triangle against the hull. I'm pretending the single triangle is a "convex hull", indeed it might be if you imagine it is a very thin, very flat tetrahedron. I don't know if I am mistaken in this concept of triangle-convex hull intersection, if the slight inaccuracy is to be expected, or if there is perhaps a bug in my code (the same SAT Test routines work for hull-hull, box-hull, and other test quite accurately though)

The relevant code is at line 621 of hull.h, with the SATTest overlap routine in Intersectable.cpp.

Answer 1

It seems you're testing with the faces of the hull and the triangle, which is good, although these are not the only possible axes of separation.

There exists more axes of separation that are the result of the various edges of the polyhedron. You can compute these axes by taking the actual edges of your two polyhedron and crossing them together. Then projections onto these axes can be used to determine possible overlap along that axis.

Of course, since cross products are involved, you must make sure to ignore edges that are near parallel. It can be shown, theoretically, that if two edges of a polyhedron are parallel then skipping their cross product (and consequently their axis projection test) will not result in a false positive.

This edge checks are literal edge cases, and the necessity of edge checks make the traditional SAT in 3D the time complexity on the order of O(N^3), which is why you don't commonly see it in professional code bases. As a side note there exists a new optimization called Gauss Map optimization, originally popularized on the Bullet forums by Erin Catto. This optimization brings the complexity back down to O(N^2), making it a great candidate for convex hulls with a smaller number of faces. There is a single resource for this optimization as a GDC 2013 lecture by Dirk Gregorius, slides of which are available at Box2D.org's downloads section.

I hope this helps!