Filling self-intersecting polygons

[Random_62]

I currently have a pretty simple simulation in which a body is made up of moving vertices. Drawing the outline of the body is fine and can be done using the polygon function. When filling the body though, there are problems. The body can self intersect which means that using the triangulation function then drawing doesn't work.

[dusoft]

Can you provide more info, maybe a screenshot or a bit of code?

[Random_62]

Can you provide more info, maybe a screenshot or a bit of code?

The object can deform into shapes like these:

Concave.png (5.55 KiB) Viewed 3136 times

Self-intersecting.png (5.39 KiB) Viewed 3136 times

When I go into the draw loop I simply pass the object into the love.graphics.polygon function to draw the outline, but since the object can deform into basically any shape (like in the self-intersecting image), I can't triangulate the polygon and then fill each triangle to fill the polygon.

[dusoft]

Try this library, I think it features your case:
https://github.com/Ark223/ClipperLua

[RNavega]

When I go into the draw loop I simply pass the object into the love.graphics.polygon function to draw the outline, but since the object can deform into basically any shape (like in the self-intersecting image), I can't triangulate the polygon and then fill each triangle to fill the polygon.

I'm sure it's more complicated than what I'm thinking, but each self-intersection point defines a new polygon. In your bottom image, there are two polygons for example, touching at the self-intersection point.

So I think an algorithm to find these subpolygons would be something like:
- As a preprocess step, create tables representing the 'edges' of the polygon, stored in a linked-list structure, such that each edge has a "next" field that points to the next edge (that shares one of its vertices), and a "previous" field that points to the previous edge (that shares the other vertex).
- Go through the list of all possible edge intersections. This should be like a Python set() structure (no duplicates exist, only unique members). Each member is a pair of edge references that can potentially intersect, ordered by ID (the first edge in the polygon first in the pair, so like with 5 edges A, B, C, D, E, you have pairs {A, C}, {A, D}, {B, E}, {B, D}, {C, E}). An edge can only intersect with edges other than its .next or .previous edges, that is, it can't intersect with its direct neighbors.
- For every intersection point, two subpolygons must exist (or be created, if they haven't been yet). So one division (say, between intersectable edges A, C) starts at the earlier edge in the pair (A), then goes to the intersection point, then goes the older edge on the pair (C), and continues through its .next edge until it cycles back to the first edge, forming a closed subpolygon. The other subpolygon is found by continuing through the .next of the first edge, until you travel back to the second edge in the intersection.
- It's possible that a large polygon can self-intersect with more than one edge pair, but it's better to leave this as an improvement once you have single intersection working great.

Intersection sketch.jpg (26.46 KiB) Viewed 2858 times

[Rigachupe]

Are you filling the polygon with something else than a color? If just color then you can do it like in this example:

-- Defining a table with the coordinates. Three vertices x1,y1,x2,y2,x3,y3 means it will be a triangle.
local vertices = {100,100, 200,100, 150,200}

-- Passing the table to the function as a second argument.
love.graphics.setColor(0,1,0,1)
love.graphics.polygon("fill", vertices)

And when you need to draw the outline you can use this:
love.graphics.setColor(1,0,0,1)
love.graphics.setLineWidth(3.0)
love.graphics.polygon("line", vertices)

[dusoft]

That would work for drawing, but if he needs to work with Shapes, then polygons must have maximum of 8 vertices.