Skip to content

Implement a gap closing contiguous fill

Maciej Jesionowski requested to merge yavn/krita:close-gap-fill into master

Gap closing fill for Krita. Finally! 🎉

This patch modifies the behavior of the scanline fill algorithm to cooperatively work with a gap closing flood fill. This method can make use of a "gap distance map" to identify the lineart gaps and stop the fill before spilling.

The core distance search algorithm was adopted from MyPaint.

Modified tools:

  • contiguous (bucket) fill - can now specify a gap size up to 32 px
  • contiguous selection tool - same, but for creating a selection that stops on gaps

Excluded:

  • enclose and fill tool - it is already rather complex, but uses a similar code path underneath. Maybe revisit at a different time.

Also adds regression tests to check the fill's behavior on a small resolution test image.

I believe there are still some opportunities for optimization, but this initial version should be good enough for a lot of use cases.

Additional information

This MR implements the feature request from: https://krita-artists.org/t/close-gap-in-fill-tool/32043

I provided a fairly in-depth explanation of the feature's purpose, the algorithm, and some implementation details here: Gap closing fill for Krita. Please check it if the implementation seems confusing. I'm also discussing the discarded ideas there.

For deeper context, I'm also providing the historical branch that has the removed code for multi-threading and similar: history-close-gap-fill

There are also test images that can be used to validate the behavior and for performance measurement: example files

This took me about 1.5 months to complete, so I hope the work is useful. 😅 Fingers crossed. I'll dutifully work through the review comments.

Test Plan

To test the feature, you can make use of the contiguous fill or selection tools, then modify the tool options to use a non-zero "close gap" size. Here's a shot of this UI element:

image

Formalities Checklist

  • I confirmed this builds. (Windows and Linux appimage)
  • I confirmed Krita ran and the relevant functions work. (Windows and Ubuntu)
  • I tested the relevant unit tests and can confirm they are not broken.
  • I made sure my commits build individually and have good descriptions as per KDE guidelines.
  • I made sure my code conforms to the standards set in the HACKING file.
  • I can confirm the code is licensed and attributed appropriately, and that unattributed code is mine, as per KDE Licensing Policy.

Reminder: the reviewer is responsible for merging the patch, this is to ensure at the least two people can build the patch. In case a patch breaks the build, both the author and the reviewer should be contacted to fix the build. If this is not possible, the commits shall be reverted, and a notification with the reasoning and any relevant logs shall be sent to the mailing list, kimageshop@kde.org.

Edited by Maciej Jesionowski

Merge request reports