Floodfill - gap closing demo


I yap on about the approach, results and caveats for about 8 minutes

There are many approaches to handling gaps in outlines when performing a flood fill. One is to dilate (grow) the obstructing pixels of the encountered tiles prior to running the fill, but that will lead to loss of information for sharp corners and areas that are narrower than the maximum gap closing radius used. Another is to perform a segmentation of the source image in one way or another, and use user-provided guides to decide whether or not to include certain areas.

The approach I’m using in this demo simply consists of a separate pass on the tiles encountered, calculating the tolerance function for the input pixels and then using that information to perform a distance-constrained search for particular kinds of gaps, assigning the resulting distance value to pixels on a line between the fill-obstructing pixels (the endpoints of the gap)

That data is then used during a four-way (non-scanline, unfortunately) fill to decide on when to stop filling if a gap is encountered.

Human-guided techniques à la GMIC:s colorize operation are definitely more appropriate for detail-rich line art with a lot of internal structure, but this simple approach seems to give pretty nice results in many scenarios.


Great video, I don’t use flood tool much but I have noticed it is super slow before. This looks like a nice improvement!


There is a quirk in the current flood fill algorithm that (at least on my machine) makes the fill slower seemingly as a function of the position of the starting point. I created examples where performing a fill starting at the bottom left takes about 1 second but starting at the top right takes 20-25 seconds. This curiosity was what got me to look at the code in the first place. The quirk is fixed here (and also in a separate pull request in case this is never included).

That being said, the gap-closing makes the process scale much worse than regular flood fill. Running an example with an area of roughly 2000x2000 pixels I get ~0.2 seconds for the regular fill and ~0.9 for the gap closing (on a laptop with an i7-3635QM from 2012).

The ideal would be to have a method of determining the existence and position of gaps before running the fill, such that they could be marked in the destination tiles, and then run the regular scanline fill afterwards.


this flood fill is great!! :smiley:


Thank you! I hope that I can make the new code great as well. Right now it is a bit of a mess.