9
\$\begingroup\$

I am attempting to implement the separating axis theorem in C#. I have a function that can calculate the minimum translation vector between two polygons. However, I can't seem to create a function that calculates the minimum translation vector between one polygon and multiple other polygons. Honestly, I've been working on this for months and am no closer to a solution and have not been able to find a solution online. There's always a few edge cases that do not return the correct result, leading to high priority bugs in my game.

Here are common edge cases that do not work correctly:

edge cases

Is there a well-known solution for this problem? All I can find is people saying "just perform the SAT on each polygon" but this rarely produces the minimum translation vector.

Any help would be highly appreciated.

Improve this question
\$\endgroup\$
2
  • \$\begingroup\$ One idea, that I've never actually got around to testing, is that some separation axes - the ones that would move you sideways into an adjacent polygon - could be flagged to never be considered as the minimum. Then some kind of repeated-test would give good results (possibly with some kind of FIFO and/or iteration limit to prevent getting stuck in a loop). \$\endgroup\$
    – Andrew Russell
    Jan 7, 2014 at 8:35
  • \$\begingroup\$ An even more difficult to solve version of this is when an edge of a shape is only partially covered by annother. For example in the top-right image, if the middle square extended out to the right, to be a larger rectangle. This is similar to the output of some code I use which takes tens of thousands of occupied/not-occupied cells and reduces that down to under a hundred larger collision shapes \$\endgroup\$
    – Richard Tingle
    Feb 6, 2014 at 11:42

1 Answer 1

Reset to default
2
\$\begingroup\$

Ideally, you don't build your environment out of polygons. You build it out of edges (which perhaps you calculate from a set of polygons). In your first example, for instance, there is a single diagonal edge; in the last example, the box is resting on a single horizontal edge.

The fact that your editor or tools use smaller, individual shapes to build a level should not impact the runtime.

A slightly simpler approach would simply remove "inner" edges of the base shapes. For your last example, there are two edges between the "floor" boxes; ignore these during collision detection.

You can find some better pictures and some implementation ideas by reading section 4.5 (edges and edge chains) in the Box2D documentation.

Improve this answer
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Using edges (particularly edges, it's slightly better with edge chains) has the major disadvantage that that it becomes very easy for physics objects to glitch inside the level geometry. \$\endgroup\$
    – Andrew Russell
    Jan 7, 2014 at 8:11
  • 1
    \$\begingroup\$ @AndrewRussell: those problems are avoided with the usual tunneling fixes. Make sure your moving objects have a fairly decent volume/area, keep their max speed per frame low enough so they can't move more than ~half their shortest dimension (or step it multiple times if you need it to move faster), avoid really sharp crevices and such in your level geometry, iterate the resolution multiple times until you converge on a "safe" final location, etc. \$\endgroup\$
    – Sean Middleditch
    Jan 7, 2014 at 17:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .