Sign in to follow this  
flounder

What corner does the SAT use?

Recommended Posts

flounder    100
I'm trying to find out what corner and/or wall the separating axis theorem uses to give a vector and magnitude to push 2 polygons apart. This might help explain: The picture shows that the vector the SAT gives to push the 2 polygons apart is the same as the closest point from the corner of the triangle inside the square, to one of the walls of the square. The only way i can think of to determine what corner and wall is being used is to check each corner for it's closest point against each wall and find the closest matching vector to the escape vector. However this is probably much less efficient than finding it out through the SAT, and can lead to finding wrong corners. Does anyone know of a method for finding the corner and wall used for the escape vector through the SAT?

Share this post


Link to post
Share on other sites
jyk    2094
There are two problems to be solved here: finding the minimum distance/direction pair that will resolve the intersection, and finding the features that will be in contact (e.g. the vertex and edge in your diagram) once the intersection is resolved.

In some contexts only the first of these two is needed, e.g. you want to resolve the intersection but don't need any information about the contact features themselves. The SAT can be implemented so as to provide this information by keeping track of the depth of penetration along each axis that is tested, and returning the minimum of these values along with the associated axis.

If you need contact features (say, as input to a physics simulator), an additional step is required. The easiest method is to determine for each shape the relevant support feature along the minimum axis returned by the previous step (in your diagram this would again be the vertex and edge that you've indicated). Then, clip these features together to find the actual contact manifold.

Share this post


Link to post
Share on other sites
flounder    100
Yes, contact features are what i'm looking for. From what you said, it sounds like i can find the wall i'm looking for by keeping track of the wall used to generate the axis that provides the minimum separation distance. And the vertex (corner) i'm looking for can be found by keeping track of the endpoint vertex closest to that wall. (what i mean by endpoint vertex, is 1 of the 2 vertice's that are used to generate the 1 D silhouette) Does that sound right?

Share this post


Link to post
Share on other sites
jyk    2094
Quote:
Original post by flounder
Does that sound right?
More or less :)

Since in 2D the minimum separating axis will always be normal to an edge of one of the polygons, that means one of the support features will always be a polygon edge, just as you suggested.

As for the other support feature, it will generally be a vertex, but could be an edge as well. You could ignore this latter case, or perform edge clipping in this case to find the contact manifold (most easily represented as two points that define a line segment).

In the vertex case, the best way to find the correct vertex is simply to find the vertex that projects maximally (or minimally, as the case may be) onto the minimum separating axis. This may be equivalent to what you said, but I thought I'd restate it just for clarity.

Share this post


Link to post
Share on other sites
flounder    100
(Sorry for the long time it took me to respond, but...)

I've got the vertex/wall selection to work 99% of the time. The times that it doesn't work, the situation looks like this:



Point A is the chosen vector, and wall BE is sometimes picked instead of CD. I think this is because those walls generate the same 1D values and some floating point error allows BE to be picked over CD (floating point error would explain why BE and CD seem to be picked at random). I was thinking a possible solution to this is to:
1) perform collision, find candidate walls and vertex's
2) if the candidate vertex has more than 1 valid escape vector, pick the wall that has the longest escape vector.

I'm pretty sure someone else has run into this problem, but i haven't seen any solutions to it yet. I just came up with the idea i had above, so i still have to think about any problems it will have, let alone if it will work. Has anyone else asked about this? and can you see any flaws in my idea?

Share this post


Link to post
Share on other sites
jyk    2094
In your example, is the selected axis the axis of the blue box that is perpendicular to BE and CD? If so, I'm not clear on why the projections of BE and CD would have similar values.

Also, if the axis is as specified above, you shouldn't have to query for the blue box's support feature anyway; you know it a priori from the results of the separating axis test.

Perhaps I'm misreading your diagram or post though.

Share this post


Link to post
Share on other sites
oliii    2196
Note that you can find the MTD directly using the result from the SAT tests, and that should return the precise MTD. There is no need to do a post-process to find the MTD when there is an intersection.

Once you have the MTD, you can find the supporting walls / vertices.

say you have vertices A[] for polygon A, B[] for polygon B, and a MTD vector, that will push A away from B.

Support(A) = max(A[i] dot MTD), 0 <= i < Anum
Support(B) = min(B[i] dot MTD), 0 <= i < Bnum

Note that you have to consider cases where you have several points that would qualify as a supporting feature, so you have to use a small tolerance. For 2D polygons, that should give you a wall, or a vertex, so either one or two points of support.

you will therefore have 4 potential cases
1) wall vs vertex
2) vertex vs wall
3) wall vs wall
4) vertex vs vertex

case 4) is highly unlikely, and is more like a bug. in 2D, there will always be at least one wall.

case 1) and 2) are trivial. The pairing point of contact is simply the vertex +/- MTD vector.

case 3) will require you do do a bit of clipping maths to find the pairing points of contact, but in 2D it's straight forward. That will give you two pairs of points of contact (4 points in total).

with that, it's pretty much all the information you need and that you can get from the SAT test.

Share this post


Link to post
Share on other sites
flounder    100
BE and CD are parallel, so their perpendicular values (and 1D comparisons) are also the same. I think i might be able to fix this by changing how i pick the walls/points, i currently:
1) Test each axis
2) find points that generate 1D values for other polygon
3) record the point that has the smallest overlap
4) when picking the actual escape vector, i use the axis being used at the time and the recorded point.

I might be able to fix this by also recording what the minimum and maximum points for the polygon with the axis were.

Share this post


Link to post
Share on other sites
jyk    2094
Quote:
Original post by flounder
BE and CD are parallel, so their perpendicular values (and 1D comparisons) are also the same. I think i might be able to fix this by changing how i pick the walls/points, i currently:
1) Test each axis
2) find points that generate 1D values for other polygon
3) record the point that has the smallest overlap
4) when picking the actual escape vector, i use the axis being used at the time and the recorded point.

I might be able to fix this by also recording what the minimum and maximum points for the polygon with the axis were.
Something seems a bit off here - I still don't understand why BE and CD would have the same projections. Remember, you only have 4 axes to test (the basis vectors of the two boxes), and in your example at least there should only be one axis that is perpendicular to BE and CD; furthermore the projections of these edges onto that axis shouldn't be anywhere close to the same value. So I may be misunderstanding something here about your diagram or explanation.

In any case, it sounds like you're making things a bit harder than they need to be. Since in 2D there are no cross-product tests, the minimum separating axis will always be an axis from one of the boxes. The minimum and maximum support features along such an axis are known a priori, and will always be a pair of edges from the box. Given the minimum axis and information about what 'side' (in 1D space) the intersection occurred on, you can deduce the support feature through simple logic. No projections or comparisons are necessary.

So, in the 2D oriented box test, one of the support features will always be an edge from one of the boxes (which effectively eliminates the troublesome vertex-vertex case from consideration). That leaves only the support feature for the other box. Generally it will be a vertex, but if the boxes are oriented in nearly the same way it may be an edge. In this latter case, as has been mentioned, you can clip the two edges together to find a pair of points representing the contact manifold.

I don't know if that clears things up at all. It can be a little confusing, but the key point here is that (as was mentioned earlier) you may be doing more work than necessary.

Share this post


Link to post
Share on other sites
flounder    100
Quote:
Original post by jyk
Something seems a bit off here - I still don't understand why BE and CD would have the same projections.


BE and CD have the same perpendicular values, so will create the same 1D values. Maybe we mean different things by "projections"?



@oliii: so do you mean finding the MTD and then looping through each vertex and testing if it pushes against a wall in the same direction and magnitude as the MTD?

I've implemented what i mentioned above and it works, though it seems that the way i'm doing it could be done better.

Share this post


Link to post
Share on other sites

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