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
Concave polygon to Convex polygons
http://www.amazon.com/Real-Time-Collision-Detection-Interactive-Technology/dp/1558607323
L. Spiro
L. Spiro
Author
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
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
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
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
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
Author
@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?
@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?
(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?(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.
...
(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?
(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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
