Jump to content
• What is your GameDev Story?

• Advertisement

MTD for concave polygons

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

Share on other sites
Advertisement
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

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

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

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

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

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

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

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

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

Share on other sites

• Advertisement
• Advertisement
• What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

(You must login to your GameDev.net account.)

• Popular Now

• 15
• 9
• 11
• 9
• 9
• Advertisement
• Forum Statistics

• Total Topics
634137
• Total Posts
3015757
×

Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!