• Create Account

## Concave polygon to Convex polygons

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

9 replies to this topic

### #1richardawusi  Members

101
Like
0Likes
Like

Posted 25 November 2011 - 02:04 AM

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

### #2L. Spiro  Members

24837
Like
0Likes
Like

Posted 25 November 2011 - 02:09 AM

http://www.amazon.com/Real-Time-Collision-Detection-Interactive-Technology/dp/1558607323

L. Spiro

### #3richardawusi  Members

101
Like
0Likes
Like

Posted 26 November 2011 - 02:21 AM

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

### #4richardawusi  Members

101
Like
0Likes
Like

Posted 26 November 2011 - 02:34 AM

Oh, I'm looking for 2D, not 3D

### #5L. Spiro  Members

24837
Like
0Likes
Like

Posted 26 November 2011 - 03:39 AM

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

### #6MarkS  Members

2981
Like
0Likes
Like

Posted 27 November 2011 - 08:50 AM

Look up polygon triangulation.

Why are you using concave polygons again?

### #7L. Spiro  Members

24837
Like
0Likes
Like

Posted 27 November 2011 - 11:21 PM

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

### #8richardawusi  Members

101
Like
0Likes
Like

Posted 28 November 2011 - 01:28 AM

@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?

### #9MaxDZ8  Members

4976
Like
0Likes
Like

Posted 28 November 2011 - 01:45 AM

(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, 28 November 2011 - 01:46 AM.

Previously "Krohm"

### #10richardawusi  Members

101
Like
0Likes
Like

Posted 28 November 2011 - 04:15 AM

Great Krohm, thanks for the response. I believe you've given the answers I need

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.