Sign in to follow this  

[SAT] translation vector

This topic is 2848 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello there, I have read several tutorials on SAT (metanet and the great gamedev resource posted on March) and thanks to those I had almost no problem in writing an algorithm for detection of rotated AABBs. For some reason though the resolving part has not clicked yet. I will explain myself: After checking the overlaps an all axes and finding the axis where the minimum overlap happens I have a problem finding the vector that will push one of the polygons away. Basically, starting from the max and min dotproducts on each axes, how do I find that final distance vector?

Share this post


Link to post
Share on other sites
It's super complicated. So much more complicated than SAT alone.

It involves comparing points to planes, edges to planes, and edges to edges. Download any open source physics engine and take a look at their "box box" intersection code. It's massive. The SAT part is ~15 lines. The contact point and separation code is 500+.

You should probably use an existing collision detection library.

Share this post


Link to post
Share on other sites
you can make it simpler by storing, for each axis you test, the amount of overlap between the two intervals, and the axis itself.

If you look at the metanet demos, the amount of overlap between intervals is shown for each axis.

Then you simply take the overlap amount that is the mimimum. Combined with the axis associated with the overlap, that gives you the MTD.

Share this post


Link to post
Share on other sites
Quote:
Original post by oliii
you can make it simpler by storing, for each axis you test, the amount of overlap between the two intervals, and the axis itself.

If you look at the metanet demos, the amount of overlap between intervals is shown for each axis.

Then you simply take the overlap amount that is the mimimum. Combined with the axis associated with the overlap, that gives you the MTD.


Hi oliii thanks for your reply and your tutorials! ( which I can't find anymore :( )

That is exactly what I do:

1. Get the axes
2. Project the polygons' vertices (polys are simple rectangles in my case)
3. Find the maximum and minimum vertex projected for each polygon
4. Get the dot products of maximum and minimum vertices and the axes vectors.
5. Use these dot products to see what is the minimum overlap

While explaining my code I've found out that it works only when the distance vector direction between the 2 polygons is positive.

Share this post


Link to post
Share on other sites
The direction of the axis should not matter, as the signs sort themselves out.

Assuming you have your separation axes normalised (you can also work with non-normalised axes, but then the maths is a little bit more complicated).

Quote:

bool IntervalsOverlap(const Vector& axis, float mina, float maxa, float minb, float maxb, Vector& mtd, float& mtdLength)
{
// the two intervals do not overlap.
if(mina > maxb || maxa < minb)
return false;

// find the amount of intersection between the intervals.
// if interval [mina, maxa] is on the 'left' of interval [minb, maxb],
// the intersection amount will be negative, else the interval amount will
// be positive. That way, object B can be pushed away from A in the
// correct direction.
float intersectionDepth = (mina < minb)? (maxa - minb) : (mina - maxb);

// if the intersection amount on that axis is smaller than the current mtd
// we found, or the mtd hasn't been initialised yet (mtdLength < 0
// is used to signal an invalid mtd), our current mtd will be
// a combination of the axis and the intersection amount on that axis.
// As more axes are being tested, the final mtd will be the axis with the
// least amount of intersection.
if((intersectionDepth < mtdLength) || (mtdLength < 0.0f))
{
mtd = axis * intersectionDepth;
mtdLength = fabs(intersectionDepth);
}
return true;
}

Share this post


Link to post
Share on other sites
here are some examples :)

here would the code with non-normalised axes. For example, if you have an edge made of two vertices va and vb, e = (vb - va), and the normal of that edge, non-normalised would be vector(-e.y, e.x). Then you can use that vector directly for the SAT without 'expensive' normalisations (although really, it's not that much of a problem).

Quote:

bool IntervalsOverlap(const Vector& axis, float mina, float maxa, float minb, float maxb, Vector& mtd, float& mtdLengthSquared, Vector& mtdDirection)
{
// the two intervals do not overlap.
if(mina > maxb || maxa < minb)
return false;

// find the amount of intersection between the intervals.
// if interval [mina, maxa] is on the 'left' of interval [minb, maxb],
// the intersection amount will be negative, else the interval amount will
// be positive. That way, object B can be pushed away from A in the
// correct direction.
// note : since the axis is not normalised the quantities mina, maxa,
// minb, maxb will be scaled by the axis length.
float intersectionDepthScaled = (mina < minb)? (maxa - minb) : (mina - maxb);

// square length of axis
float axisLengthSquared = axis.dotProduct(axis);

// intersection depth on that axis, but squared.
float intersectionDepthSquared = (intersectionDepthScaled * intersectionDepthScaled) / axisLengthSquared;

// if the intersection amount on that axis is smaller than the current mtd
// we found, or the mtd hasn't been initialised yet (mtdLengthSquared < 0
// is used to signal an invalid mtd), our current mtd will be
// a combination of the axis and the intersection amount on that axis.
// As more axes are being tested, the final mtd will be the axis with the
// least amount of intersection.
if((intersectionDepthSquared < mtdLengthSquared) || (mtdLengthSquared < 0.0f))
{
mtd = axis * (intersectionDepthScaled / axisLengthSquared);
mtdLengthSquared = intersectionDepthSquared;
mtdDirection = axis * (intersectionDepthScaled < 0.0f)? -1.0f : 1.0f;
}
return true;
}


the mtd vector is 'mtd', the mtdLengthSquared is used to cache the length of the mtd, but squared, so we can use that quickly for comparisons, the mtdDirection is the direction of the mtd, basically the normal of collision.

If the mtd becomes very small, it is probably not wise to use the mtd itself as the normal of collision (as if you try to normalise it, you will get a divide by nearly zero and a loss of precision).

Share this post


Link to post
Share on other sites
Hey oliii,

Meant to reply to you in the last days but I wanted to make sure the code was REALLY working :)

Anyway, I think I've found a different method with non normalized vectors.

I couldn't understand well the use of squared length in your case but here's my procedure anyway:

Quote:


//find the axes
//only two each as they are rectangles :)
axes.push(getAxis(a.vertices, 1, 2));
axes.push(getAxis(a.vertices, 1, 0));
axes.push(getAxis(b.vertices, 1, 2));
axes.push(getAxis(b.vertices, 1, 0));

//check the four axes
for (var i:int = 0;i < axes.length; i++) {
//projectPointsToAxis return the dotproduct of
//the vertex vector and the axis vector
//use this scalar value to compare the length of the
//projections on the projected axis
var ap:Point = projectPointsToAxis(a.vertices, axes[i]);
var bp:Point = projectPointsToAxis(b.vertices, axes[i]);
collisionOnAxis = getInterval(ap, bp);
//if there isn't an overlap on any of the axis then there is definetely no collision on the others!
if (bp.x > ap.y || ap.x > bp.y) return null;
//the direction of the vector
var dir:Number = (collisionOnAxis < 0) ? -1 : 1;
collisionOnAxis = Math.abs(collisionOnAxis)

// This will be used to calculate the minimum translation vector
if (collisionOnAxis < minCollisionOnAxis) {
minCollisionOnAxis = collisionOnAxis;
translationAxis = axes[i];

//project back the found distance
var len:Number = (translationAxis.x * translationAxis.x) + (translationAxis.y * translationAxis.y);
translation.x = minCollisionOnAxis / len * translationAxis.x;
translation.y = minCollisionOnAxis / len * translationAxis.y;
translation.x *= dir;
translation.y *= dir;
}



Whadya think? :)

Share this post


Link to post
Share on other sites
I wonder why people always use interval projection (at least for face normals). You can do the following which is very simple:

For each face on convex A/B
Get Plane P For This Face
Get Support Vertex S In The Negative Direction Of Plane Normal On Convex B/A
Compute Distance Of S to P And Find Your Penetration/Separation



While iterating your faces you just keep track of the axis of minimum penetration. If you find a separating axis you have an early exit. The MTD is than just the penetration and the MTV is the plane normal.

In 3D testing the edge cases is a little bit more involved, but you can extend to idea of a supporting point to supporting edges or even faces. A necessary condition for two edges to realize a contact is that the associated arcs (duals) on the Gauss-Map must intersect. This basically means geometrically that the edges build a face on the Minkowski sum.

HTH,
-Dirk

Share this post


Link to post
Share on other sites
Quote:
Original post by DonDickieD
I wonder why people always use interval projection (at least for face normals). You can do the following which is very simple:

For each face on convex A/B
Get Plane P For This Face
Get Support Vertex S In The Negative Direction Of Plane Normal On Convex B/A
Compute Distance Of S to P And Find Your Penetration/Separation



While iterating your faces you just keep track of the axis of minimum penetration. If you find a separating axis you have an early exit. The MTD is than just the penetration and the MTV is the plane normal.

In 3D testing the edge cases is a little bit more involved, but you can extend to idea of a supporting point to supporting edges or even faces. A necessary condition for two edges to realize a contact is that the associated arcs (duals) on the Gauss-Map must intersect. This basically means geometrically that the edges build a face on the Minkowski sum.

HTH,
-Dirk


True. I suppose that could apply to the swept test as well.

Share this post


Link to post
Share on other sites

This topic is 2848 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this