Jump to content

  • Log In with Google      Sign In   
  • 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.


  • You cannot reply to this topic
9 replies to this topic

#1   Members   -  Reputation: 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

#2   Crossbones+   -  Reputation: 24139

Like
0Likes
Like

Posted 25 November 2011 - 02:09 AM

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


L. Spiro

#3   Members   -  Reputation: 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

#4   Members   -  Reputation: 101

Like
0Likes
Like

Posted 26 November 2011 - 02:34 AM

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

#5   Crossbones+   -  Reputation: 24139

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

#6   Crossbones+   -  Reputation: 2782

Like
0Likes
Like

Posted 27 November 2011 - 08:50 AM

Look up polygon triangulation.

Why are you using concave polygons again?Posted Image

#7   Crossbones+   -  Reputation: 24139

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

#8   Members   -  Reputation: 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?

#9   Crossbones+   -  Reputation: 4967

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"


#10   Members   -  Reputation: 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 Posted Image




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.




PARTNERS