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

Sponsor:

#2 L. Spiro   Crossbones+   -  Reputation: 13391

Like
0Likes
Like

Posted 25 November 2011 - 02:09 AM

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


L. Spiro
It is amazing how often people try to be unique, and yet they are always trying to make others be like them. - L. Spiro 2011
I spent most of my life learning the courage it takes to go out and get what I want. Now that I have it, I am not sure exactly what it is that I want. - L. Spiro 2013
I went to my local Subway once to find some guy yelling at the staff. When someone finally came to take my order and asked, “May I help you?”, I replied, “Yeah, I’ll have one asshole to go.”
L. Spiro Engine: http://lspiroengine.com
L. Spiro Engine Forums: http://lspiroengine.com/forums

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

Like
0Likes
Like

Posted 26 November 2011 - 02:34 AM

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

#5 L. Spiro   Crossbones+   -  Reputation: 13391

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
It is amazing how often people try to be unique, and yet they are always trying to make others be like them. - L. Spiro 2011
I spent most of my life learning the courage it takes to go out and get what I want. Now that I have it, I am not sure exactly what it is that I want. - L. Spiro 2013
I went to my local Subway once to find some guy yelling at the staff. When someone finally came to take my order and asked, “May I help you?”, I replied, “Yeah, I’ll have one asshole to go.”
L. Spiro Engine: http://lspiroengine.com
L. Spiro Engine Forums: http://lspiroengine.com/forums

#6 MarkS   Prime Members   -  Reputation: 882

Like
0Likes
Like

Posted 27 November 2011 - 08:50 AM

Look up polygon triangulation.

Why are you using concave polygons again?Posted Image

#7 L. Spiro   Crossbones+   -  Reputation: 13391

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
It is amazing how often people try to be unique, and yet they are always trying to make others be like them. - L. Spiro 2011
I spent most of my life learning the courage it takes to go out and get what I want. Now that I have it, I am not sure exactly what it is that I want. - L. Spiro 2013
I went to my local Subway once to find some guy yelling at the staff. When someone finally came to take my order and asked, “May I help you?”, I replied, “Yeah, I’ll have one asshole to go.”
L. Spiro Engine: http://lspiroengine.com
L. Spiro Engine Forums: http://lspiroengine.com/forums

#8 richardawusi   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 Krohm   Crossbones+   -  Reputation: 3064

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.


#10 richardawusi   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