Yet another Separating Axis Theorem Question

Quote:

Original post by brainydexter I am working in 2D and have been trying to get the SAT working for both collision detection and response. It works for static objects, but I can't understand as to how to apply it to moving objects. Can someone please help me with this .. Thanks

I'll just mention some of the good references that I'm familiar with:

1. Dave Eberly covers this in one or more of his books (I think), and in a PDF document on his website, geometrictools.com.

2. I think this is covered in Christer Ericson's book on collision detection as well.

3. One of our forum members, oliii, has written some demo code which he has made available online.

4. oliii, myself, and others have posted in quite a few threads on this topic in the past, often going into some detail about the details of the separating axis test (both the discrete and continuous versions). If you search the archives for phrases like 'dynamic SAT', 'continuous SAT', and 'swept SAT', you should be able to find some of these threads.

If that doesn't give you the info you need, then post back here with any specific problems you're running into, and we should be able to help out.

Coincidentally, when I was learning and trying to understand how SAT works, I read through all the references you mentioned.

Oliii's code and his (deprecated) html really helped me see through things. I have a few questions from his code. Probably they will help me do collision resolution..
(From his second example, for extending SAT to determine collision response by finding MTD):

1. In function:: separatedByAxis(...) ; calculateInterval(...) is called, with the projection of polygon vertices being found by (m_vertices * axis).
-> Here axis is not normalised, and thus, when I write similar code, I get obnoxiously large value of overlap which is later on calculated.

Similarly;
Vector sep = axis * (overlap / axis_length_squared);

Here shouldn't it be sqrt of axis_length_squared to find the MTD ?

2. In the documentation:

// makes sure the push vector is pushing A away from B
Vector D = A.Position – B.Position;
if (D dot MTD < 0.0f)
MTD = -MTD;

I didn't understand how this works... what does D dot MTD represent ?

3. Lastly, from what I understand, MTD is like the resultant velocity that one of the bodies should assume after the collision..is that correct ??

I'd really appreciate any help with this..

Thanks

that's old code but anyway...

Quote:

1. In function:: separatedByAxis(...) ; calculateInterval(...) is called, with the projection of polygon vertices being found by (m_vertices * axis). -> Here axis is not normalised, and thus, when I write similar code, I get obnoxiously large value of overlap which is later on calculated.

That's correct, the overlap is scaled by the length of the axis. To get a 'normalised' length, you would have to divide by the length of the axis, which involves a square root.

Quote:

Similarly; Vector sep = axis * (overlap / axis_length_squared); Here shouldn't it be sqrt of axis_length_squared to find the MTD ?

overlap is scaled by the axis length, axis is also not normalised and has a length. So if you divide but the length squared, you end up with a separation vector that with the scaling factors removed.

Quote:

2. In the documentation: // makes sure the push vector is pushing A away from B Vector D = A.Position – B.Position; if (D dot MTD < 0.0f) MTD = -MTD; I didn't understand how this works... what does D dot MTD represent ?

That's part of the code that had me re-think the algorithm (which is pretty rubbish in the first place).

With the new code and method, you do not need to do that check.

Here, it basically means that if the separation vector is going the wrong way (if it would make B actually move towards A instead of away from A), negate it for the desired effect.

As I say, it's actually part of what's wrong wiht the algorithm, as it is unnecessary if the algoritm was actually designed properly :)

here is the new code without all those caveats.

these posts should also give you more details on how and why it actually works (The code above is an indirect implementation of those principles).

some more discussions and code about the swept SAT. It's in 3D for boxes, but same thing really. It shows how easy it is to transpose the 2D algorithm into 3D.

Oh, its you Olii! Wanted to say big thanks for posting that code/docs online..its really helped me understand SAT!

I'll go through the link and post my doubts here, but I have a question on what you explained about the overlap.

" overlap is scaled by the axis length, axis is also not normalised and has a length. So if you divide but the length squared, you end up with a separation vector that with the scaling factors removed. "

I understood that the length of a vector v is found as:
|v| = sqrt( v.x * v.x + v.y * v.y)

Thus, when you write:
Vector sep = axis * (overlap / axis_length_squared);

How do you get the overlap scaled by the axis length ? Has it (overlap / axis_length_squared) got something to do with proportion, i.e. overlap in proportion to axis length ? If so, I still don't understand how would it be proportionate to the axis length ?

This might sound dumb, but I think I am missing out something really simple..

Take an example, if you decided to normalised the axis :

Vector separationAxis = edge0.crossProduct(edge1);
float axisLength = axis.length();
Vector normalisedAxis = axis / axisLength;

float overlap = (body1.vertex(0) - body2.vertex(3)).dotProduct(normalisedAxis);
float separationVector = normalisedAxis * overlap;

Now replace normalisedAxis by (separationAxis / axisLength);

float overlap = ((body1.vertex(0) - body2.vertex(3)).dotProduct(separationAxis / axisLength);
float separationVector = (separationAxis / axisLength) * overlap;
= separationAxis * (overlap / axisLength);
= separationAxis * (((body1.vertex(0) - body2.vertex(3)).dotProduct(separationAxis / axisLength) / axisLength);
= separationAxis * (((body1.vertex(0) - body2.vertex(3)).dotProduct(separationAxis) / (axisLength * axisLength));

I see what you're saying.. but I have some questions about what you posted on other thread and the code that you posted..

I read the posts at the other thread, the gomez article at gamasutra and your code for "Extending further for fast moving objects". I think I understand how the algorithm works and how it helps, but I have some doubts and want to make sure if what I am thinking is right or not. So here it is..

For static objects, we just find the Minimum Translation Distance (MTD) for resolving collision. The same doesn't cut it for moving objects, since there is an added component of velocity. We need a way to resolve the velocity(both magnitude and direction) of the moving object after collision resolution. Also, when the velocity is high enough; objects (A & B) should not be allowed to pass through each other.

If the objects are going to collide in a frame (due to their velocity), we want to find the volume swept so that they dont pass through each other. This is done with the help of finding the time at which they enter into collision. It follows from the concept of a point along a line defined by the transformation:

Xi = (1 - Ti) * Xo + Ti * X1 where X0 = initial position ; X1 = final position of body B and Ti = (0,1) => as time goes from 0 to 1; object goes from its initial position to the final position and somewhere in between it would intersect with the other body (coz of its velocity)

Now, this is from your(Oliii) code:: bool separatedByAxis_swept( (const Vector& axis, float d0, float d1, float v, CollisionInfo& info) ::
//...
float t0 = d0 / v;
float t1 = d1 / v;

d0 & d1 = overlap on left / right side
v = axis.Dot(Va - Vb); // projection of velocity along the axis

Thus, we get time from the generic formula:
Time = Distance / Speed (am i thinking correct here ???)
=> t = overlap / projected speed =>(time of intersection at left/right side)

This yields t0 and t1, (& assuming that the objects will collide because of the velocity, t0, t1 will be between (0,1) OR is it that only t0 will be between (0,1)..i think the latter one is true, since you sort it later on..but am not sure??? )

// sort values on axis
// so we have a valid swept interval
if(t0 > t1) { //swap t0 and t1 }
// order t0 and t1 increasingly => t0 will always be < t1 after this

// swept interval outside [0, 1] boundaries.
// polygons are too far apart
if(t0 > 1.0f || t1 < 0.0f)
=> because of the concept of the point moving between two points from t = 0 to 1

if (t0 > info.m_tenter)
{
info.m_tenter = t0;
info.m_Nenter = N0;
}
Trying to find the earliest time at which the two objects come into contact...shouldn't this be like the minimum of all the given times. I didn't understand this, since the same was written in the gomez article ???

if (t1 < info.m_tleave)
{
info.m_tleave = t1;
info.m_Nleave = N1;
}
Trying to find the earliest time at which the two objects leave each other..i have the same question as I had above for this case. It should be maximum of all times, but you seem to be calculating the minimum here???

if(info.m_collided)
{
Acoll.m_position += Acoll.m_velocity * info.m_tenter;
}
// This is just resolving the body along the resultant velocity..but where do you change the direction of the velocity???

I have spent lot of time trying to understand this, but am not 100% sure if I understand all of it correctly. I didn't want to write some code that I didn't understand. Also, I used this article earlier, but its just a short version of what you're doing..