[SAT] translation vector
Author
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?
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.
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.
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.
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.
That's true i guess what i had trouble with was the contact point (there are potentially many), not the separation.
Author
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.
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).
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;}
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).
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).
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).
Author
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:
Whadya think? :)
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 axisvar ap:Point = projectPointsToAxis(a.vertices, axes);var bp:Point = projectPointsToAxis(b.vertices, axes);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 vectorvar dir:Number = (collisionOnAxis < 0) ? -1 : 1;collisionOnAxis = Math.abs(collisionOnAxis)// This will be used to calculate the minimum translation vectorif (collisionOnAxis < minCollisionOnAxis) {minCollisionOnAxis = collisionOnAxis;translationAxis = axes;//project back the found distancevar 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? :)
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
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
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
