Yeah, that’s what I found, too. If the tile size is 64x64, there’s just not enough data to benefit from threads and synchronization will kill it. Also because the algorithm updates pixel’s surroundings, it means each thread must have a lot of room to work with (equal to the gap size). So if the gap size is 32px, it means one thread can touch any pixel of the tile and you cannot multi-thread at all.
On the other hand, increasing the tile size to 128px or more can help, but then it worsens the latency of lazy tile loading and makes cases like drag-fill much worse.
I am now focusing on a single, well-optimized path for 64px tile, lazy loading, and single-threaded. I have a few more optimization ideas that I want to try before publishing the MR. I will do a bit more R&D later, maybe then it would be a good moment to look at other code examples. For now, I really want to get this first version delivered as I believe it should be good enough already for many practical use cases.
I’ll try to host the images somewhere and share it here. It’s a bit large. Smaller images and small gap sizes perform fast already, so it’s mostly the problem when the image is big, or if there’s an unusual case like spray/hatching.
gap_test_low.png - I use this one to check how algorithm works at a small scale and how the behavior degrades with large gap sizes. Interesting cases here:
can it expand from corners to the full area?
can it miss some pixels at particular gap sizes?
(in both cases it’s not ideal for every gap size. It’s difficult to make it work universally from pixel art image to 4K).
fill_test_big.png - this is my main stress image, I can check here:
background fill around the character - worst performance is with a small gap size, because it will then seep everywhere
shirt fill near the sleeve - this will go into the spray and can perform really badly in some cases
drag filling on spray/hatching - can be really bad
face / arm / legs - these are easy cases and perform well almost everytime
fill_test.png - this is a smaller size image, should be more like a normal typical lineart, although the gaps are maybe a bit too big for a typical drawing.
I typically test with threshold 1, no anti-aliasing, and no other unusual options, just the basic fill. Then adjust the gap size from 1 to 32 px. I did lowered the cap to 32px, because the larger it is, the worse the performance hit. Going from 32px to 40px can have a dramatic effect.
One possible optimization for large images is checking if the whole patch + extra border is to be filled (no transparent pixels in the opacity map) and just fill it with memcpy or something.
I’ll keep it in mind. I wanted to experiment a bit with opacity map representations. It seemed to me the bottleneck is in the paint device iterator itself (reading the data in the first place), but I’ll be verifying it still.
Take heart, folks… I’m almost done with this thing I’m cleaning up the comments and writing the documentation (explain the algorithm in detail, with pictures). I should be done in a day or two (want to proof-read with a clear head, etc.).
But man, I spent good several hours trying all sorts of stuff, debugging, and removing code again when it didn’t work as I had hoped I fought tooth and nail for every few milliseconds But I think the results are now pretty darn good. I managed to optimize the drag-fill and the baseline algorithm, too.
Yes, I’m feeling pretty good about this. Can’t wait to share with y’all!
I don’t know about the release plans nor how long it will take to go through the code review process. It could take a week or two.
However, once the code is merged, it should be available in the nightly and probably the plus builds too. The latter are usually safe to use, I’m myself using a plus build regularly.
The MR contains a bunch of links, but for easier access, here’s also the link to the algorithm document:
I really wanted to push it over the finish line today, so forgive me if the wording is a bit awkward. I hope it still reads well and is informative.
Phew, what a wild ride it’s been! I hardly drew anything, didn’t play games, severely cut back on anime Now, only to survive the review feedback, and I can maybe go back to my usual routine. Need to pick up that pen again!
I’m a bit confused and checked your docs, what is the difference between ‘enclose and fill tool’ which isn’t part of the MR vs what is? That is where I’m confused about.
Enclose and fill is a different tool icon that you can use. It is used to mark parts of the image, and if these parts have closed areas, then the tool will fill them with color. Just check out the documentation.
My changes are added only for the bucket fill (contiguous fill) and contiguous selection tool (the magic wand).
The problem with your test is that the gap size is very large. If you select the gap size of 17 pixels, then the size of the gap in your line drawing cannot be larger than that. Judging from the video, it’s more like 200 pixels. Try a drawing with only subtle gaps.
Thanks, I guess I was thinking it would be like GIMP where it could be any arbitrary size. I noticed that on your MR you mentioned larger than 32 px, so maybe what I was trying might be possible later.
If you want the GIMP method, you can use the filter mentioned in this post. I think it’s a very good alternative that may work for images with large gaps.
You will find it in Filters > G'MIC > Black & White > Colorize Lineart [Smart Coloring].
Currently it will not. It was only added for the contiguous selection (the magic wand) and the contiguous fill (the bucket).
Enclose and fill is pretty complex already and it didn’t seem worth it to me to add this feature to it. We can revisit that based on the feedback, and the review isn’t done yet either.
I’m cleaning up the comments and writing the documentation (explain the algorithm in detail, with pictures). I should be done in a day or two (want to proof-read with a clear head, etc.).
I fought tooth and nail for every few milliseconds 
But I think the results are now pretty darn good. I managed to optimize the drag-fill and the baseline algorithm, too.
for a job well done.
