Jump to content
  • Advertisement
Sign in to follow this  
legionalways

Does anyone know how to prove this algorithm for Collision Detection

This topic is 2485 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

There are two convex polygons(A and B) on a 2-D plane, each with M and N edges.
To test whether the two polygons collide, do as what follows:

For an arbitrary edge of one of the polygons, find a vector which is perpendicular to the edge.

Project polygon A onto this vector, using dot product to get the projection range ,lets say (minA, maxA)
For polygon B ,you get (minB, maxB)

Now you test whether the two ranges intersect.



[color="#ff0000"]Edited:
[color="#ff0000"]IF in one test , you find that the two projections don't overlap, you know there is a separating axis and polygon A and B don't collide.
[color="#ff0000"]IF you go through all the tests, and the projections always intersect, then polygon A and B overlap.

So my Question is : How can I get the Mathematical proof?

Share this post


Link to post
Share on other sites
Advertisement

There are two convex polygons(A and B) on a 2-D plane, each with M and N edges.
To test whether the two polygons collide, do as what follows:

For an arbitrary edge of one of the polygons, find a vector which is perpendicular to the edge.

Project polygon A onto this vector, using dot product to get the projection range ,lets say (minA, maxA)
For polygon B ,you get (minB, maxB)

Now you test whether the two ranges intersect.

So there will be M+N tests. If in one test, you find that the two ranges intersect, you know that polyon A and B collides .

if you go through all the tests but don't find two intersected ranges,it's sure that polygon A and B does not collide.


So my Question is : How can I get the Mathematical proof?

Why do you need a proof other than for homework ?

Share this post


Link to post
Share on other sites

There are two convex polygons(A and B) on a 2-D plane, each with M and N edges.
To test whether the two polygons collide, do as what follows:

For an arbitrary edge of one of the polygons, find a vector which is perpendicular to the edge.

Project polygon A onto this vector, using dot product to get the projection range ,lets say (minA, maxA)
For polygon B ,you get (minB, maxB)

Now you test whether the two ranges intersect.

So there will be M+N tests. If in one test, you find that the two ranges intersect, you know that polyon A and B collides .

if you go through all the tests but don't find two intersected ranges,it's sure that polygon A and B does not collide.


So my Question is : How can I get the Mathematical proof?


I don't think you'll find a proof because this technique does not work. (hint: try to think of an example where the projections overlap but the polygons do not intersect).

Note, if you're trying to describe a separating axis approach this is not it and your description is confusing/wrong.

-Josh

Share this post


Link to post
Share on other sites

So there will be M+N tests. If in one test, you find that the two ranges intersect, you know that polyon A and B collides .

if you go through all the tests but don't find two intersected ranges,it's sure that polygon A and B does not collide.


These are wrong. You can conclude the polygons dont intersect as soon as you find one edge for which the polygons don't intersect (that is the "separating axis"). They do intersect if the ranges intersect for ALL edges.

The proof would be something along the lines that you consider the projection along axis S a function proj_s(x). Now for two sets A and B if proj_s(A) and proj_s(B) are disjoint then the preimages A* and B* cannot intersect either and since A subset A* and B subset B* it follows A and B are also disjoint. Now the proof that you can conclude they do intersect if you check all edges is a different story :D (which means, I don't know the proof off the top of my head)

Share this post


Link to post
Share on other sites

[quote name='legionalways' timestamp='1324367518' post='4895621']



I don't think you'll find a proof because this technique does not work. (hint: try to think of an example where the projections overlap but the polygons do not intersect).

Note, if you're trying to describe a separating axis approach this is not it and your description is confusing/wrong.

-Josh
[/quote]

Yeah, I put it wrong. I have corrected it. What about now?

Share this post


Link to post
Share on other sites


Yeah, I put it wrong. I have corrected it. What about now?


Yes, it is a bit better now, although if you want a proof of the separating axis theorem it would be simpler to just state that. As for how to prove it, japro has suggested an approach you could try. Failing that the wikipedia article on the SAT is also pretty suggestive.

-Josh

Share this post


Link to post
Share on other sites
[s][color="#1C2837"]

[color="#1C2837"]

For an arbitrary edge of one of the polygons, find a vector which is perpendicular to the edge.


[color="#1C2837"]

[/quote]


[color="#1C2837"]



[color="#1C2837"]

Do you mean any vector that's perpendicular to the edge? Then your algorithm is still wrong. After all, the normal of a polygon is also perpendicular to all of its edge, and so it should be enough to just do two tests: one with the normal of your first polygon, and one with the normal of your second polygon.


[color="#1C2837"]



[/s][color="#1C2837"]

[s]Clearly this doesn't work though, since it's not so hard to think of two non intersection polygons, whose projections onto the subspace generated by their normals gives two intersecting lines.[/s]


Ignore this. I thought you were talking about 3D.

Share this post


Link to post
Share on other sites

So my Question is : How can I get the Mathematical proof?

You prove the separating axis test by a) looking at how many ways the two convex objects can come into contact, and then b) making sure you have tested for separating for all those possibilities. If, after you have performed all those tests, you have not found the objects separated, you must conclude they are intersecting.

For two convex polygons in 2D, you will find that the polygons can come into contact with their vertices and along their edges, and that it is sufficient to test separation with planes that are parallel to the edges of the polygons (or, equivalently, along axes that are parallel with the edge normals). This means you perform at most M + N separating axis tests for a 2D intersection test of a convex M-gon and a convex N-gon.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!