• Advertisement
Sign in to follow this  

Concave polygon to Convex polygons

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

Hi guys,

I have got the Separating Axis Theorem (SAT) working for collision detection between convex polygons, however, I can't get it to work with concave ones. I know the theory that concave polygons need to be split into convex ones as SAT doesn't work for concave polygons. The problem is, I don't know how to apply the splitting of concave to convex in code. I've come across numerous resources but next to no code examples of how this is actually done. If anyone can give me sample code, or a very detailed pseudo-code, it will be greatly appreciated.

Thanks

Share this post


Link to post
Share on other sites
Advertisement
Thanks YogurtEmperor but I was hoping I could get an answer here on the forum from anyone willing to help with sample code or pseudo-code. Thanks

Share this post


Link to post
Share on other sites
The reason no one else has replied is because no one wants to write 3 chapters of a book explaining how to do what you want to do when someone else already has.
The book has all the answers you need, plus it will tuck you into bed at night and check for monsters under the bed.


L. Spiro

Share this post


Link to post
Share on other sites
Somehow that reminds me.

What you actually want is ear clipping.

http://www.geometric...EarClipping.pdf

In 2D it is quite trivial to convex-ify polygons via ear clipping. After you break the polygon into triangles, recombine the triangles such that the maximum number of triangles are grouped together without becoming concave.


L. Spiro

Share this post


Link to post
Share on other sites
@Marks, Basically, the more variety you have in terms of landscape, generally, the nicer the look and feel of a game. I figured if I could sort out collision with concave polygons, then I don't have to worry about spending hours building complex concave shapes from a bunch of convex ones. But now, when I actually think of it, the idea of polygon triangulation is doing the exact opposite. I'm guessing I don't really achieve much?

@YogurtEmperor, thanks for the link. That is the sort of thing I had in mind.

Tell me, is it worth triangulating concave polygons for collision detection really? As stated in my response to Marks, I may as well spend the hours building concave polygons from convex polygons, and skip the step of triangulation all together. Question is, is the process of triangulation so expensive that I'll gain something if that process doesn't happen?

Share this post


Link to post
Share on other sites
(1) Basically, the more variety you have in terms of landscape, generally, the nicer the look and feel of a game. (2) I figured if I could sort out collision with concave polygons, then I don't have to worry about spending hours building complex concave shapes from a bunch of convex ones. But now, when I actually think of it, the idea of polygon triangulation is doing the exact opposite. (3) I'm guessing I don't really achieve much?
...

(4) is it worth triangulating concave polygons for collision detection really? (5) is the process of triangulation so expensive that I'll gain something if that process doesn't happen?
(1) You got your facts wrong. Many systems do not support concave volumes as well and this has not been limiting the industry for several years.
(2) Of course! Too bad concave collision detection is a couple order of magnitudes slower.
(3) Yes, exactly.
(4) Just look at the algorithms. Just look at them. Seriously.
(5) The process of triangulation is indeed expensive, but it is fired only once. Managing concave polys will make you suffer each frame. Edited by Krohm

Share this post


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

  • Advertisement