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.
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.
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)
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.
Well, seeing as this year goes on for less than another two weeks, I think it’s quite unlikely.
I’m afraid I haven’t been very proactive about getting this into the main branch.
Don’t think there are any functional show stoppers, but I’m not sure if anyone else has even built and tested this - at any rate nobody has informed me if they have (any bug reports appreciated). The changes/additions also constitute a fair amount of new code, and it probably needs some style tweaks and documentation improvements prior to inclusion.
Beyond that, I should really try to improve the user interface to accommodate the new functionality - things like being able to disable/enable gap closing by pressing some modifier key, or canvas click-drag to adjust tolerance/offset values.
Hi,
I am hoping to port your algorithm to Android (Java).
Do you you think it’s an advantage using the C++ library, or would you just as well write everything in Python (or Java)?
First thing to note here is that the full algorithm (C++ and Python) is somewhat tied to the tile-based canvas concept that MyPaint uses, but that can be adapted. The short answer to your question is that if you only want to support moderate canvas sizes (say 2000x2000 pixels), well written Java should be good enough. I would not recommend trying to implement it in pure Python, because even with numpy I think you’d run into performance bottlenecks with the array searches/manipulations.
You should also look into the GMIC auto-fill implementation and GIMP’s adaptation of that algorithm. It might be more suitable for lower-hz cpu’s with multiple cores (which Android cpu’s tend to be).
That approach is more sophisticated than mine, but possible harder to run without full pre-processing. One reason I implemented this algorithm in the way I did was to avoid having to pre-process more than one tile at a time, since images in MyPaint can be quite huge.
