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:
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.
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:
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.
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.
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.
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
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).
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).
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.
just cut it down as polys and fill it, whats the problem ?
xor
drops mic
word
drops mic
word
Quote:
Skia does this, but even then it's a complicated problem.just cut it down as polys and fill it, whats the 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.
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.
@rudi : sorry, I've not read correctly.
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
aaaaand i realized last three line for point check is total nonsense
also blkcount *2+1 for all instead of blkcount*2-1
I think -2^8 pseudocoded it for you...almost.
But really: watch that playlist i posted...answers all your upcoming questions! ;)
But really: watch that playlist i posted...answers all your upcoming questions! ;)
hardie: ok
Maybe some of these articles will help you:
http://hugi.scene.org/online/coding/hugi%2027%20-%20coding%20corner%20darkblade%20polygon%20drawing%20-%20part%201.htm
http://hugi.scene.org/online/coding/hugi%2027%20-%20coding%20corner%20darkblade%20polygon%20drawing%20-%20part%202.htm
http://hugi.scene.org/online/coding/hugi%2016%20-%20co3d15.htm
http://hugi.scene.org/online/coding/hugi%2027%20-%20coding%20corner%20darkblade%20polygon%20drawing%20-%20part%201.htm
http://hugi.scene.org/online/coding/hugi%2027%20-%20coding%20corner%20darkblade%20polygon%20drawing%20-%20part%202.htm
http://hugi.scene.org/online/coding/hugi%2016%20-%20co3d15.htm
Starchaser ok, thought it was easy
not sure if gluTesselate could make it
Do you have the points of the polygon or do you only have the bitmap image of it?
Perhaps useful
GPC – General Polygon Clipper library
GPC – General Polygon Clipper library
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.
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
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
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:
so is it possible to know which of the polygons to fill if its just a bitmap, or must one have the edge-directions?
so is it possible to know which of the polygons to fill if its just a bitmap, or must one have the edge-directions?
and the result would be something like this:
