1
\$\begingroup\$

In the 2D SAT collision determination algorithm, you project the convex polygons onto each potential separating axis. Supposing the polygons intersect, from what I understand, the axis for which the overlap of the projections is the smallest determines the minimum translation vector. The MTV direction is parallel to the separating axis and the magnitude is the length of the overlap.

When calculating the overlap, however, I'm wondering if it is necessary to account for different overlap scenarios.

We have projection intervals (for some axis) (a, b) and (c, d). (a, b) comes from the polygon who normals we're currently testing as separating axes.

Case 1:

Case 1

Case 2:

Case 2

Intuitively, the overlap in the first case is b - c, and the overlap in the second case is d - a. And if this turns out the be the axis of minimum overlap, you might want to flip the MTV direction in one of the above cases, depending on what you are doing.

However, I'm wondering if it is actually necessary to consider the d - a interval. I.e., is there a proof of something to the effect that, when d - a is less than b - c, that the axis cannot possibly be the axis of minimum overlap (or, if it is, that we could have used another edge's normal, such that its projections' b - c interval was the minimum overlap)? In the second case, it is true -- d - a is less than b - c, and there is a smaller axis of overlap (e.g. b - c when the axis is the red polygon's upper edge normal).

But does this hold in general? Is there a simple counter example?

\$\endgroup\$
  • \$\begingroup\$ I can't migrate this to the math site as you requested because the question's too old (the ability to migrate is disabled after a certain number of weeks). I'm not familiar with the rules of the math site, so I don't know if this would be on-topic there, but you could certainly try. If you post it there, please let me know and I'll close this one with a link to your new question. \$\endgroup\$ – Josh Feb 21 '16 at 20:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.