pouët.net

Fill the interior of a silhouette where lines.

category: code [glöplog]
If it is possible, I need a fast and simple way to fill a n-gon from a silhouette. The only thing I have is a silhouette of a n-gon. Lines may cross so I don't need a floodfill, it will just fill one section unless it is possible to find all interior points.

Wikipedia have some page on Even-odd rule, but I don't understand the Python code, I write in C. Is it possible however to do it without vectors (or rays pointing) and just the silhouette image?

Here's what I mean:

BB Image

The polygon shows that there are two special cases of when to fill and not. One where the first point where two lines meet are ignored, and the other where it is not. My failed attempt shows that it works on the first case, but on the second the filling does not start until the second.

Im trying to avoid as many obstacles as possible and find the most simple algorithm, trying to do everything in one go, not using too advanced scaline--approach that requires to many arrays.
added on the 2019-02-08 17:01:52 by rudi rudi
Maybe recursion?
You call the routine from an interior pixel (that might be the tricky part), it sets the point, and tries to call itself in the four directions if possible and not yet filled.
added on the 2019-02-08 17:50:56 by baah baah
You might want to get the full picture of 3D-FUNdamentalz! So here´s a YouCube-playlist with everything you need to know! I chose the video i think should be about your problem...but its from my bookmarks, so i am not exactly sure, could be +-1 or 2 videos from there, maybe just watch it all! ;)
https://www.youtube.com/watch?v=9A5TVh6kPLA&list=PLqCJpWy5Fohe8ucwhksiv9hTF5sfid8lA&index=6
basically it´s about starting a polygon one pixel offset on x ;)
the problem is that at some point there is just one pixel, which is the corner of two vertices meeting, but at this point the pixel is inside the polygon. but if there is another polygon crossing this point, then it should not be filled.

but the image i posted shows not where another polygon crossing but where the edge is just one pixel. there are two cases of that shown in the image where one point is convex and the other is concave. its difficult to know which is which when working on independent scanlines, so maybe one could have a temporary variable for some of the edges? also question is could one just store temporary for the first edges (i.e the edges on the far left side, since the scanline is working from left to right).
added on the 2019-02-08 19:01:45 by rudi rudi
baah: thats just floodfill, and it wont work for larger polygons, the stack will just get filled up quite fast right and issue an overflow. its not actually floodfill that i am out after, because one can draw crossing lines all over and some parts will have hulls in them.
added on the 2019-02-08 19:04:11 by rudi rudi
just cut it down as polys and fill it, whats the problem ?
added on the 2019-02-08 19:05:35 by skarab skarab
xor
drops mic
word
added on the 2019-02-08 19:28:13 by EvilOne EvilOne
Quote:
just cut it down as polys and fill it, whats the problem ?
Skia does this, but even then it's a complicated problem.
The non-zero rule comes to the rescue.

If all you have is pixels then basically all you can do is tracing the outline and memorize for each scanline where the outline is. Then you could apply a simple scanline fill on that.
Holes might be possible by using an even-odd-(on-off)-approach but would be mutually exclusive with self-overlapping polygons.
added on the 2019-02-09 00:47:47 by T$ T$
@rudi : sorry, I've not read correctly.
added on the 2019-02-09 05:32:51 by baah baah
Code:bool currentpixel; 0=black 1=white bool lastpxstate; bool inside=0; int blkcount=0; int lastscanlinearray[arraylimit]; int bw[arraylimit]; pixelset; if(inside ==0) { if(lastpxstate != currentpixel) inside=1; } else { if(lastpxstate != currentpixel) inside=0; blkcount++; } bw[blkcount*2-1]++; if(mod(blkcount,2)>0) pixelset = 0: else pixelset = 1; if(bw[blkcount*2-1]>lastscanlinearray[blkcount*2-1]) pixelset = !pixelset;

written while almost sleeping..
i don't think this gonna work but here's my piece of pseudocode
added on the 2019-02-09 06:53:21 by pitapoto pitapoto
aaaaand i realized last three line for point check is total nonsense
added on the 2019-02-09 07:02:44 by pitapoto pitapoto
also blkcount *2+1 for all instead of blkcount*2-1
added on the 2019-02-09 07:05:06 by pitapoto pitapoto
I think -2^8 pseudocoded it for you...almost.
But really: watch that playlist i posted...answers all your upcoming questions! ;)
hardie: ok
added on the 2019-02-09 12:08:42 by rudi rudi
Starchaser ok, thought it was easy
added on the 2019-02-09 13:26:01 by skarab skarab
not sure if gluTesselate could make it
added on the 2019-02-09 13:26:38 by skarab skarab
Do you have the points of the polygon or do you only have the bitmap image of it?
added on the 2019-02-10 12:49:56 by rloaderro rloaderro
rloaderro: Only the bitmap image at the moment. I can get the vertices with a little twiddling though. I hoped there was a trick with just the bitmap of the silhouette. Either it is possible or it is not.
added on the 2019-02-10 20:43:05 by rudi rudi
another approach would be an inverse flood fill: just mark the exterior of the polygon using a flood fill, and in a second everything not filled are the actual pixels to be filled.

Can be optimized by memorizing only the start/stop fill points, then it basically ends up at the classing scanline on/off list, just that the list is generated by traversing pixels rather than the polyline vectors
added on the 2019-02-10 22:18:16 by T$ T$
my bad, I should have used a better word than silhouette. its the edges of a figure is what I mean. I should have been more clear on that. Here's another "extreme" example:

BB Image

so is it possible to know which of the polygons to fill if its just a bitmap, or must one have the edge-directions?
added on the 2019-02-10 23:23:48 by rudi rudi
and the result would be something like this:

BB Image
added on the 2019-02-10 23:29:36 by rudi rudi

login