2
\$\begingroup\$

I've just successfully implemented Separating Axis Theorem (SAT) in my game but I was wondering how do I find the penetration vector? I heard it can be useful for collision response. e.g. The harder they collide the harder the response.

I want the penetration vector so I apply it to the position of an object when it is current penetrating an other so I can move it back outside of the other object's bounds.

Here is my code so far.

Any help would be much appreciated,

Thanks in advance.

\$\endgroup\$
3
\$\begingroup\$

The classic way to do this is the GJK algorithm. It's a fairly complicated algorithm with a lot of moving parts, so might be tricky to implement. However, there are many implementations out there on the Web that you might be able to adapt.

A simpler way to get an approximate penetration vector might be to leverage the SAT itself; when you iterate over all the possible separating axes and check for overlap on each, keep track of which axis has the shortest overlap and use that as the penetration vector.

\$\endgroup\$
  • \$\begingroup\$ Yeah I'm sure I could use what I already have to find it, So you said look at the overlaps and find the shortest one? Then what multiply the overlap by the axis? \$\endgroup\$ – Joshua Barnett Mar 14 '12 at 17:22
  • \$\begingroup\$ @SyntheCypher Exactly. The normalized axis multiplied with the shortest overlap will yield the penetration vector. \$\endgroup\$ – bummzack Mar 14 '12 at 18:29
  • \$\begingroup\$ Ok well I tried that and I get a vector back but, it doesn't give me the exact x and y I need to move an object by to stop them from intersecting. :( \$\endgroup\$ – Joshua Barnett Mar 14 '12 at 22:34
  • \$\begingroup\$ @SyntheCypher The vector this produces should separate the two objects. It may not separate them in the best possible way, but if everything is working correctly the objects should definitely come out separated after one of them is translated by this vector. \$\endgroup\$ – Nathan Reed Mar 14 '12 at 23:45
  • 1
    \$\begingroup\$ @heishe I don't think the SAT method necessarily always separates along the shortest possible distance, since it only considers a fixed set of axes. I could be wrong, but I'd be surprised if it comes out that way. (Now, whether you actually want the shortest possible distance is another question. You might prefer to use the penetration along the objects' relative velocity, so you can back up the objects to the actual time of collision and handle it at that point, rather than allowing interpenetration at all.) \$\endgroup\$ – Nathan Reed Mar 15 '12 at 7:09
1
\$\begingroup\$

You should be already calculating it, atleast kind of. When projecting shapes onto a normal you're checking if two projections are overlapping. To make this information more usefull, you should store that value, that value is the distance the two shapes need to be moved in a given direction to avoid collision. Now to calculate the actual penetration vector all you have to do is check which value was the smallest and that's your penetration vector. That's all.

\$\endgroup\$
  • \$\begingroup\$ In addition, you should check out this link: codezealot.org/archives/55#sat-mtv \$\endgroup\$ – TravisG Mar 15 '12 at 6:44
  • \$\begingroup\$ I have done but no one has explained how this method works "Collider.getDistance(m_min, other.m_max);" \$\endgroup\$ – Joshua Barnett Mar 29 '12 at 16:12

Your Answer

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

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