Floodfill - gap closing demo


#1

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.


#2

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


#3

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.


#4

this flood fill is great!! :smiley:


#5

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


#6

Yeah I like this flood fill, it looks and functions how I’d expect it to. I really would love for this to officially be implemented soon!


#7

Time flies, and here’s an update on this:

The code is now clean and documented, with improved performance in some areas as well.

Heavy morphological operations (growing/shrinking) can now take advantage of multicore machines to distribute the workload - right now it’s pretty naive, but can still bring about 2x speedups for large loads.

Feathering is slightly faster and, more importantly, blurs the fill by the actual chosen radius.

Previously there was a case where a gap-closing fill could have no effect with the unseep* options turned on, due to it erasing the entire fill (usually very small areas). If this happens now, the unseeping is reverted, meaning that one doesn’t have to jump between the settings and the canvas to turn it off.

*(now called “retract seeps”, suggestions for better names appreciated)

If anyone wants to test, the code can be accessed from this branch: https://github.com/jplloyd/mypaint/tree/floodfill_new_features

I also want to try to make it possible to cancel long-running fills + getting feedback on the fill progress, perhaps with a dialog box popping up after 2 seconds or so.
Even though the performance scales better now, it’s still possible to get the old 20-second lags when using extreme settings on a huge/dense canvas.