Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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

screen shot 2013-08-09 at 11 58 42 am

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 +

screen shot 2013-08-09 at 11 58 45 am

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.

share|improve this question
1  
No time to currently check, but I bet you have an issue with your cross products between edges. If I get time I'll peak around your code later. –  RandyGaul Aug 11 '13 at 3:34
    
You mean the cross product between edges to get the tri norm? Do you mean I should be doing more tests on the tri involving more than just the tri norm? –  bobobobo Aug 11 '13 at 3:44
    
Okay I think I see the problem. I don't see any cross product checks anywhere! Do you have cross products between edges, as the result of these cross products are additional potential axes of separation? Edit: I'll just put this up as an answer with a little more details. –  RandyGaul Aug 11 '13 at 3:46

1 Answer 1

up vote 2 down vote accepted

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!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.