Separating axis theorem for rectangles: what's the projection's direction?
Author
Consider a separating axis test for two rectangles that overlap. Now say I'm testing the rectangles on the axes stemming from their left and right sides--rectA.LeftNormal, rectA.RightNormal, rectB.LeftNormal, and rectB.RightNormal. These axes are all parallel.
Every one of these axes will show the same amount of overlap when the rectangles are projected onto them. If the projection vector is determined by the direction of the axis exhibiting the minimum overlap (as it says in http://www.harveycartel.org/metanet/tutorials/tutorialA.html, secion 1, "calculating the projection vector"), how do I know which of my axes (left- or right-facing) to use? It seems ambiguous.
Put another way, take the interactive example on that page involving the red and blue rectangles. Position the rectangles such that their centers coincide. How does the example know that the projection is leftward rather than rightward?
--
Jeff S.
for the SAT, if you have two faces that are parallel, it doesn't matter if the axis goes one way or another. For the case of a rectangle, you do not need to use the leftNormal AND the rightNormal. Either one will be fine.
If you coincide the two centres, then you can't really tell if the overlap will be left or right (as the amount of overlap on both sides will be equal). It's then arbitrary.
It's the same problem if, for example, you have a left overlap and a top overlap equal. You just take any of the two. But the chances of having that occur would be pretty slim.
Have the boxes [Amin, Amax] and [Bmin, Bmax].
Amin = (0, 0)
Amax = (10, 5)
Bmin = (8, 1)
Bmax = (20, 10)
from that you can tell the MTD will be (-2, 0). You'll need to push the box A 2 pixels to the left to separate them.
take the axis = rightNormal = (1, 0).
now take axis = lefNormal = (-1, 0)
so, both axis yield the same result. the signs cancel each other out.
[Edited by - oliii on January 29, 2009 3:44:08 AM]
If you coincide the two centres, then you can't really tell if the overlap will be left or right (as the amount of overlap on both sides will be equal). It's then arbitrary.
It's the same problem if, for example, you have a left overlap and a top overlap equal. You just take any of the two. But the chances of having that occur would be pretty slim.
Have the boxes [Amin, Amax] and [Bmin, Bmax].
Amin = (0, 0)
Amax = (10, 5)
Bmin = (8, 1)
Bmax = (20, 10)
from that you can tell the MTD will be (-2, 0). You'll need to push the box A 2 pixels to the left to separate them.
take the axis = rightNormal = (1, 0).
float a0 = A.minBound(axis) = Amin.x = 0float a1 = A.maxBound(axis) = Amax.x = 10float b0 = B.minBound(axis) = Bmin.x = 8float b1 = B.maxBound(axis) = Bmax.x = 20float d0 = (a1 - b0) = 2float d1 = (b1 - a0) = 20if(d0 < 0 || d1 < 0) return false; // no overlap// take minimum overlap of the twoif(d0 < d1){ // d0 side. the good side! MTD = -d0 * axis = (-2, 0);}else{ // d1 side. MTD = d1 * axis = (20, 0);}now take axis = lefNormal = (-1, 0)
float a0 = A.minBound(axis) = Amax.x = -10float a1 = A.maxBound(axis) = Amin.x = 0float b0 = B.minBound(axis) = Bmax.x = -20float b1 = B.maxBound(axis) = Bmin.x = -8float d0 = (a1 - b0) = 20float d1 = (b1 - a0) = 2if(d0 < 0 || d1 < 0) return false; // no overlap// take minimum overlap of the twoif(d0 < d1){ // d0 side. MTD = -d0 * axis = (20, 0);}else{ // d1 side. the good side! MTD = d1 * axis = (-2, 0);}so, both axis yield the same result. the signs cancel each other out.
[Edited by - oliii on January 29, 2009 3:44:08 AM]
Author
Quote:Original post by oliii
take the axis = rightNormal = (1, 0).float a0 = axis.dotProduct(Amin) = 0float a1 = axis.dotProduct(Amax) = 10float b0 = axis.dotProduct(Bmin) = 8float b1 = axis.dotProduct(Bmax) = 20float d0 = (a1 - b0) = 2float d1 = (b1 - a0) = 20if(d0 < 0 || d1 < 0) return false; // no overlap// take minimum overlap of the twoif(d0 < d1){ // d0 side. the good side! MTD = -d0 * axis = (-2, 0);}else{ // d1 side. MTD = d1 * axis = (20, 0);}
Hm. My implementation turned out to be pretty different. I never considered the case where d0 > d1 (the bad side) because it didn't seem to represent an overlap. That is, the only overlap I observed between rectA and rectB was the 8-10 region, and the only overlap I observed between rectB and rectA was the same 8-10 region. That resulted in ambiguity when deciding which way to move rectA.
Looks like I'm misunderstanding the SAT.
--
Jeff S.
Quote:
. I never considered the case where d0 > d1 (the bad side) because it didn't seem to represent an overlap.
It represents if the interval A intersects interval B near a0, or a1.
It will overlap near a0 if b1 is near a0, and b1 > a0.
It will overlap near a1 if b0 is near a1, and b0 < a1.
So in effect, you take the min of (a1 - b0) and (b1 - a0), and making sure (a1 > b0 and b1 > a0) achieves that.
The 'bad' side is hard to visualise, as as you say, it's not visually intuitive. But it's just a simplifications of the maths required to detect which side the intersection occurs. But it's all consistent whatever the direction of your axis (and even length if you don't fancy normalisation).
Author
Quote:Original post by oliii
It represents if the interval A intersects interval B near a0, or a1.
I'm still trying hard to get this... what confuses me is that you seem to use a different heuristic--a special case--for each direction. For the right normal, you calculate Amax - Bmin and Bmax - Amin, but for the left normal you calculate Amin - Bmax and Bmin - Amax. I don't understand the semantic; this seems like an odd special case because some of my polygons may not have opposing normals like this (a triangle, for instance).
So I can't see how to put this into a *general-purpose* algorithm. It's as if I'd have to prepare this algorithm by first iterating over each of my polygons normals to find all pairs that are exactly opposite each other; by doing so I'd know those pairs of normals for which I'd have to run this (seemingly) special case.
--
Jeff S.
with the SAT, you need to find the projection interval of an object along an axis. That involves finding the min and max bounds of the object along the axis.
in the first example, where the projection axis goes to the positive X axis, the min bound is Amin and Bmin, and the max bound is Amax and Bmax.
However, in the second example, the axis goes in the opposite direction. So the max bound on object A, going towards (-X), will be Amin, and the min bound on A, going towards (-X), will be Amax.
basically,
a0 = min(A.Vertex[].dotProduct(Axis))
a1 = max(A.Vertex[].dotProduct(Axis))
b0 = min(B.Vertex[].dotProduct(Axis))
b1 = max(B.Vertex[].dotProduct(Axis))
EDIT : I've changed the code. Sorry about that.
in the first example, where the projection axis goes to the positive X axis, the min bound is Amin and Bmin, and the max bound is Amax and Bmax.
However, in the second example, the axis goes in the opposite direction. So the max bound on object A, going towards (-X), will be Amin, and the min bound on A, going towards (-X), will be Amax.
basically,
a0 = min(A.Vertex[].dotProduct(Axis))
a1 = max(A.Vertex[].dotProduct(Axis))
b0 = min(B.Vertex[].dotProduct(Axis))
b1 = max(B.Vertex[].dotProduct(Axis))
EDIT : I've changed the code. Sorry about that.
void calculateIntervals(const Vector& axis, const Vector* vertices, int verticesCount, float& minBound, float& maxBound){ minBound = maxBound = vertices[0].dotProduct(axis); for(int i = 1; i < verticesCount; i ++) { float d = vertices.dotProduct(axis); if(d < minBound) { minBound = d; } else if(d > maxBound) { maxBound = d; } }}void AABBox::calculateIntervals(const Vector& axis, float& minBound, float& maxBound){ Vector centre = (m_max + m_min) * 0.5f; Vector halfsize = (m_max - m_min) * 0.5f; float p = centre.dotProduct(axis); float r = halfsize.x * fabs(axis.x) + halfsize.y * fabs(axis.y); minBound = p - r; maxBound = p + r;}[Edited by - oliii on January 29, 2009 5:36:58 AM]
Author
Quote:Original post by oliii
so, both axis yield the same result. the signs cancel each other out.
That did it! Once you fixed the code I was able to get my toolkit working. (I know this is late getting back, but I'm trying to get in the habit of bringing closure to threads. :)
For each (unit) axis in both my polygons, I kept track of the minimum overlap magnitude computed with your code, resulting in a list of (axis, minimumMagnitude) pairs. Then I iterated over all the pairs and found that one axis*minimumMagnitude multiplication that resulted in the smallest vector, which I returned as the collision response vector.
Next step: friction... how to slow or stop a character from sliding down the slope!
--
Jeff S.
glad to be of help.
You can get away with the calculations without normalising the SAT axes (you have to work with squared quantities), and also, find the smallest vector as you test every axis in succession.
Static friction is tricky, but in short, you have a coefficient of friction (in the range [0, 1]), and a plane to stand on. Then you project your forces (vwould it work with velocities at the point of impact?) along the normal of the plane and the tangent of the plane into Fn and Ft, and if (Ft / Fn) < coeff_of_static_friction, then your character should not move along the tangent plane.
just for fun
You can get away with the calculations without normalising the SAT axes (you have to work with squared quantities), and also, find the smallest vector as you test every axis in succession.
Static friction is tricky, but in short, you have a coefficient of friction (in the range [0, 1]), and a plane to stand on. Then you project your forces (vwould it work with velocities at the point of impact?) along the normal of the plane and the tangent of the plane into Fn and Ft, and if (Ft / Fn) < coeff_of_static_friction, then your character should not move along the tangent plane.
just for fun
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement