Polygonal Decomposition – Concavity Support

About Monkey 2 Forums Monkey 2 Code Library Polygonal Decomposition – Concavity Support

This topic contains 7 replies, has 3 voices, and was last updated by  abakobo 4 months ago.

Viewing 8 posts - 1 through 8 (of 8 total)
  • Author
    Posts
  • #15932

    Abe _King_
    Participant

    This will convert a generic Vec2D list, assumed polygon, and convert it into a list of convex polygons. It has a very simple interface, it literally only uses one function. I’m not certain this has been done, but the more the merrier!

    You can find the source in this Gisthttps://gist.github.com/Ghouly-The-Ghost/d8d2c9973ff7dc120d94b356730c75f9

     

    This is how you use it!

     

    I want to add thanks to the guys behind HaxePunk, that’s the reason I was able to write this! Special thanks to Matrefeytontias who is responsible for the algorithm and the source code I translated. He even wrote an article over the process over here:

    https://gamedevnotesblog.wordpress.com/2017/10/29/designing-algorithms-intuitively-convex-decomposition-of-simple-polygons/

    #15935

    DruggedBunny
    Participant

    Interesting, saved!

    There’s a vaguely similar module in the Ted2Go Module Manager (under Build menu), png2polygon, might be of interest if you haven’t seen it — produces polygons from PNG images, worked really well as far as I recall.

    #15942

    abakobo
    Participant

    LOL! You could not do it at a better time for me as I was going to use Mark Bayazit’s algorithm for this purpose (https://mpen.ca/406/bayazit). I suppose you do it for box2d. Have you implemented the max number of vertices=8 ?

    I’m working on a box2dxt function to decompose complex polygons and I’ve nearly finished the step of decomposing complex poly to simple polys now! so now I need concave decomp (and reduction to 8 vertices).

    You can see pictures (attached) of the “decomplexification” of complex polys 😉 Now I have to split and convex decomp it!

    So… great thx!

    Attachments:
    #15945

    DruggedBunny
    Participant

    [EDIT: Oopsie, ha ha.]

    #15946

    Abe _King_
    Participant

    @abakobo My intentions for making this actually weren’t for Box2d, although I was thinking it would be fairly useful in the future if I wanted to use it with Box2D.

    I actually needed this for textured polygons which I have got working – shown here: https://www.youtube.com/watch?v=fp1nCmfV-aw&feature=youtu.be

    This splits it up into a stack of convex polygons though, and if you needed to break them down into less than 8 vertices I would imagine the step of splitting an already convex polygon would be pretty simple.

    This is not a proof . . . but I believe, since all diagonals of a convex polygon lie inside of it, that if you split a convex polygon from any vertex to another you’ll end up with two convex polygons. So it should be easy to do using some recursive function. And I suppose you could re-use this function if you are not confident it will always be convex – since this code guarantees one.

    #15949

    abakobo
    Participant

    Ah Ok shader stufff!?

    Yes splitting a convex to convex is pretty straightforward… thx again.

    #15950

    Abe _King_
    Participant

    @abakobo –removed wrong reply— No shaders involved there! All primitive work, with special thanks to Ethernauts for his help 🙂

    #16007

    abakobo
    Participant

    I have finnnallly finished the complex polygon (positive)partitionning. I had made a lot of mistakes and the problem was a bit difficult. But it’s there. It just won’t allow collinear&intersecting segment at the “edge” of the poly.
    If anybody wants to try it, the code is attached. Run polytoolstest.monkey2 for demo. It is not decomposing to convex polys yet.

Viewing 8 posts - 1 through 8 (of 8 total)

You must be logged in to reply to this topic.