Sign in to follow this  

MTD for concave polygons

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

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...

Share this post


Link to post
Share on other sites
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.


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>.)

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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. ;) )

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Quote:
Seriously, why did I need FMOD to run that?

^^ Sorry for that :-D I used my 2D engine (which is actually rather a OpenGL, SDL, DevIL, FRMOD wrapper) as a framework for this app. Of course that was stupid, but I'm so lazy... I already created a new demo framework using NOTHING than OpenGL ;-) So the next demo won't be bigger than a few kb.

Thanks for your good comments! I'll try to fix all the problems.
But right now I'm also implementing rigid-body-dynamics (which I didn't really understand), so the whole thing will take a while :-D

Share this post


Link to post
Share on other sites
New file

Here's the new version (this time only about 44 kb) :-D
I din't add any special features but this time you can see the MTD (objects aren't moving any more). That way it's much easier to find those nasty bugs...

(The old download has been disabled)

Share this post


Link to post
Share on other sites
the problem with concave polygons is, that no matter your algorithm to seperate them, i bet i can always find i situation in which it will produce no or nonsensical results.

the problem with convex or rather unions of convex polygons is that you can easily find out how to seperate two polygons, but that doesnt mean the entire union will be seperated.

personally i think the most robust approach to collision detection involves partitioning into convex regions, aswell as precalculating and giving each region a normal, or direction of ejection, so that when one object penetrates the other, you apply a force/impulse proportional to the amount of penetration in the direction indicated.

Share this post


Link to post
Share on other sites
@Eelco
I think I must agree here. That stuff gets far too complicated to handle for me :-(
So I'll quit! From now on I'll use convex polygons instead...

Share this post


Link to post
Share on other sites
I ran the demo,
I'm not sure I know what you mean by MTD anymore...
There are a lot of cases where the two shapes would still be overlapping if moved according to the line that was drawn. Maybe I missed something here...

Share this post


Link to post
Share on other sites

This topic is 4577 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.

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