MTD for concave polygons
Author
Sadly I couldn't find ANYTHING on this topic...so I had to ask here :-D
Is there a simple/fast way to find the minimum vector to seperate two intersecting, arbitrary shaped polygons (in 2D)?
My first idea was:
Find all points of polygon A inside Polygon B. Now calculate the distance from each of these points to each of B's borders. Then find the minimum of these distances.
Take the point and border belonging to this minimum and create a vector having the length dist(point_to_border) and an orientation perpendicular to the border. That would be the MTD.
I'm pretty sure that this would owrk, but it seems to be way too much work ;-)
So is ther a better solution?
Thanks for your help...
Your method won't work, since it is possible to have two polygons that overlap and yet neither has points within the other. This is possible even with triangles. See crude illustration below. A represents the corners of triangle A and B represents the corners of triangle B. Using a point-in-polygon test, you would discover here that A is outside of B and B is outside of A, e.g., point-in polygon test isn't insufficent and for this case, your algorithm would fail immediately.
(Edited for formatting.)
(Again edited for formatting. Something about backslashes....)
(More formatting experimenting....why must it be so obscure.)
(Well, shit, slashes refuse to format correctly so I've switched over to periods. Lets see if that works, <fumes>.)
B . . A----.---.----A . . . . .. .. .. .. . . . . B----.---.----B . . A(Edited for formatting.)
(Again edited for formatting. Something about backslashes....)
(More formatting experimenting....why must it be so obscure.)
(Well, shit, slashes refuse to format correctly so I've switched over to periods. Lets see if that works, <fumes>.)
Hi,
To find the MTD between two CONVEX polygons you can check up the "separation axis" theorem. That theorem will handle cases like the above.
but I don't know of any theorem for CONCAVE polygons yet. The problem is in a case like this, where the vector does not have to be perpendicular to any specific edge.
Anyway, if you find anything, would you mind sharing your results here? I am also very interested.
Best of Luck
-Cuppo
To find the MTD between two CONVEX polygons you can check up the "separation axis" theorem. That theorem will handle cases like the above.
but I don't know of any theorem for CONCAVE polygons yet. The problem is in a case like this, where the vector does not have to be perpendicular to any specific edge.
________| || || || ___|_| . | .| . |__.___________________| . . || .____. ||____________________________|Anyway, if you find anything, would you mind sharing your results here? I am also very interested.
Best of Luck
-Cuppo
Author
Quote:Anyway, if you find anything, would you mind sharing your results here? I am also very interested.
LOL :-) Of course I will (IF I find something) ;-)
@grhodes_at_work
Humm! That's an interesting idea...SHIT :-D
But maybe I can add some additional testing to my Algorithm (maybe do an border/border check?). Of course that will slow everything down a bit....but maybe that can be optimized...I'll give it a try!
Thank's for your replies!
Even worst than that your algorithm will fail even with two convex polygons, just consider one polygon complete included on a larger one, distance calculation will not tell you anything.
How about splitting the concave polygon into a set of convex ones? Then the separating axis will be the worst of the two sets, there could be more than just one separating plane.
I think this is how the physics engines do it.
How about splitting the concave polygon into a set of convex ones? Then the separating axis will be the worst of the two sets, there could be more than just one separating plane.
I think this is how the physics engines do it.
Splitting up the concave polygon is not as easy as you think. Taking the longest vector would not work for the above problem that I posted. Also it would fail for a case like this too.
The shortest MTD vectors would both point toward the middle of the concave shape, neither is correct.
I hope a solution presents itself eventually. I'm really relying on this thread now ;).
-Cuppo
(Damn. I hate doing ASCII art...You better read this post. ;) )
_____________. . . . . . . . . . . ______._______ . | . | . |_____._______| . . . . . . . ..____________.The shortest MTD vectors would both point toward the middle of the concave shape, neither is correct.
I hope a solution presents itself eventually. I'm really relying on this thread now ;).
-Cuppo
(Damn. I hate doing ASCII art...You better read this post. ;) )
Since triangles are convex polygons. Splitting a concave polygon into array of convex of polygons is easy, just triangulate the polygon. There are many algorithms for doing that in the net.
But if you do not want to do it algorithmically, it is also possible doing it by design and has nicer partitioning.
And about not working sure it works.
The case you show will first calculate a plane to the side, but after one or two step it will soon get the closest distance outside in the direction toward the solution. Also you are presenting an extreme case. Usually this thing works in a way the polygon are separated to begin with, and the goal is to prevent the interpenetration.
This is not the case with the proposed solution.
Like I said this is something that really works and most popular physics engines with robust collision already do.
But if you do not want to do it algorithmically, it is also possible doing it by design and has nicer partitioning.
And about not working sure it works.
The case you show will first calculate a plane to the side, but after one or two step it will soon get the closest distance outside in the direction toward the solution. Also you are presenting an extreme case. Usually this thing works in a way the polygon are separated to begin with, and the goal is to prevent the interpenetration.
This is not the case with the proposed solution.
Like I said this is something that really works and most popular physics engines with robust collision already do.
Author
Here's a little something I assembled today. www.vankurt.de/files/mtd.zip
(hope there aren't too many DLLs missing) ;-)
Be careful: if you move the mouse too fast the problem discussed earlier will apper: the objects get stuck in each other. But if you handle things nice and slow everything seems to work fine...
So there are two solutions to the problem. But I'm not sure which is the faster/simpler one:
1) As mentioned above break every polygon into several convex ones, and use a completely different algorithm (seperating axis?)
2) Take time into consideration: use the previous and current position of every vertex to build a line segment. Then test this one against the other polygon to find earlier collisions...
Any other ideas? :-D
What do you think?
(hope there aren't too many DLLs missing) ;-)
Be careful: if you move the mouse too fast the problem discussed earlier will apper: the objects get stuck in each other. But if you handle things nice and slow everything seems to work fine...
So there are two solutions to the problem. But I'm not sure which is the faster/simpler one:
1) As mentioned above break every polygon into several convex ones, and use a completely different algorithm (seperating axis?)
2) Take time into consideration: use the previous and current position of every vertex to build a line segment. Then test this one against the other polygon to find earlier collisions...
Any other ideas? :-D
What do you think?
That works pretty well, it was fun to play with it trying to break it. I did manage to break it when doing vertex-vertex collisions (which are degenerate) which are a big pain to get working nicely. These rarely happen in simulation but having loose ends is bad. You'll also need to fix the movement problem because that turns out in physical simulations quite often if you don't keep a very small timestep.
What I couldn't test was if parallel lines were handled correctly, but I expect they are.
Seriously, why did I need FMOD to run that? [smile]
What I couldn't test was if parallel lines were handled correctly, but I expect they are.
Seriously, why did I need FMOD to run that? [smile]
Very encouraging results given the time you spend on it.
I found that it is easy to convex vertex penetrate other convex vertex, but since that is one of the simplest test, I think you work will be very good when completed.
I was skeptical to test this at first but the results are not bad at all. Kept it up.
I found that it is easy to convex vertex penetrate other convex vertex, but since that is one of the simplest test, I think you work will be very good when completed.
I was skeptical to test this at first but the results are not bad at all. Kept it up.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
