Floodfill features - updates

Developer's Area
,
1

After far too long I will inform anyone who is interested about the state of the new* futuristic flood fill functionality™.

To recap, the old new features were:

dilation/erosion - being able to grow or shrink the fill by setting an offset
feathering - being able to blur the fill
gap closing - being able to not seep through gaps smaller than an adjustable size (while still filling into corners)

Since then, I’ve also added the ability to use the erase and lock alpha modes when using the fill tool, which can be useful when it is easier to block-brush a region and remove contiguous sections on the outside of it. Both of these could previously be accomplished by working on a separate layer and then using blending modes and layer groups to mask, but this is definitely more ergonomic.

I have also finally got around to building and testing on a Windows VM and apart from needing to figure out (or more likely, just conditionally disable) multiprocessing for morph operations, it all seems to work fine after a couple of easily squashed bugs were dealt with.

There are a couple more things I want to do in this area (selectable constant source layer, better option adjustment), but for now I think the change set is large enough as it is.

* Guaranteed no more than 50 years old

1 Like
2

You should look into @dothiko work into the floodfil as well. He had some interesting ways to expand upon it as well.

3

Yes! Reading and testing his branches was one of the first things I did. The only problem with his approach to morphological operations (dilation/erosion) is quadratic complexity. To be fair, that does not really matter for small offsets (which in practice will cover most use cases), but leads to severe slowdowns for larger ones.

His grabcut fill prototype is very interesting, but since it is essentially a separate mode I think a finished version of that could be added at a future point independent of any changes to the current tool set.

4

Here are the new strings that would be added with this patch set (each bullet point is a separate string):

  • Offset:
  • The distance in pixels to grow or shrink the fill
  • Feather:
  • The amount of blur to apply to the fill
  • Use gap detection
  • Try to detect gaps and not fill past them.
    Note: this can be a lot slower than the regular fill,
    only enable when you really need it.
  • Max gap size:
  • The size of the largest gaps that can be detected
  • Prevent seeping
  • Try to prevent the fill from seeping into the gaps

(that’s it)

If anyone has any feedback or suggested changes about this I would be grateful. It’s easy to think that something is descriptive when you have been working on it for a while, when it’s really not. E.g. I changed “Retract seeps” to “Prevent seeping” to reflect what the option is supposed to achieve, rather than how it achieves it.

I also have a question about new strings, if anyone knows.
Should updated translation files be part of the pull request? Is it ok to generate them as a part of a separate commit or should I rebase to include them at the commits where the strings were originally added?

Also, apologies for some github issues being littered with references to commits which are no longer part of any active branch, I mistakenly thought that force pushing and branch deletion would clean those up.

5

I’ll just answer this myself, based on a cursory look at the logs. It seems that the po-files are updated in one go as part of a string-freeze commit. Maybe this approach is common enough to not warrant documenting (or maybe I just didn’t find said documentation).

On the fill side, I went ahead and added static source selection, meaning that you can select any layer or layer group to act as the fill reference, regardless of which layer you are working on (filling into). The default is and “sample merged” overrides it.
Static fill references are very nifty when you need multiple fill layers and want to be able to work with each layer independently (without hiding/unhiding all the time, as might be necessary when using “sample merged”).

It’s basically like working with “sample merged” enabled but with a lot more flexibility (no need to disable backgrounds for example). You can even get the ordinary “sample merged” behaviour without the background layer included, by creating a single layer group containing the rest of the layer tree (including the fill layers) and setting that topmost group as the fill reference.

As an aside, I added keyboard toggling for gap detection, fill reference layer (between and <previous choice, if any>, and sample merged. The three are toggled by double tapping (within 0.5s) the left Shift, Control and Alt keys respectively. For obvious reasons, this will not make it into an actual release, but is useful for testing things out.

6

No new features, but nevertheless some important and useful changes.

I have added unit tests for fill- and morphological operations, for both correctness and performance measuring. Correctness tests are mostly performed by calculating and comparing exact bounding boxes for outlines and the resulting filled tiles. The input data is read from a static set of outlines in an .ora file (one outline per layer, grouped by type).

Needless to say, it is very nice having a test suite to run between changes.

I have also made an experimental implementation of threaded morphing (growing/shrinking) in C++, which allows for big performance boosts for large fills on multi-core cpus (4-5x in some cases) and has the added benefit of (hopefully) working on Windows. I have used the Python multiprocessing module for this previously, but it seems tricky to get that to work well (or at all) on Windows.

7

Since last time, I’ve mostly improved code structure and quality, but wait, don’t go just yet!

The performance of large gap-closing fills is now greatly improved where large empty surfaces are involved. It’s easy to skip large areas of tiles when performing regular fills, but a little bit trickier with the gap-closing fill (more elaborate conditions, basically). Nevertheless, this is really good when failing to set the gap distance sufficiently high, and leaking through into the whole canvas (if said canvas is very large).

Speaking of such scenarios, I’ve added a “limit to view” option, which prevents the fill from going outside the current view (or rather, outside the smallest rectangle that can fit the current view). This is useful for e.g. tuning gap closing options, checking if/where there is a leak in the first place, and doing things like erasing without wasting time on things you don’t want erased (or where there is nothing to erase).

There’s also a new optimization that hopefully doesn’t mess with anything else, which can make “sample merged” (with background disabled) and the new source layer modes run a lot faster for large empty areas.

Apart from that, I also spent a few hours over the past two days implementing threaded compositing, and have learned that (barring any mistakes in my implementation) there is basically no performance benefit to be had there (and most often, degradation). Bit of a shame, but not wholly unexpected.

8

I have tried my hand at gif-making (which I’m told is all the rage these days) to demo some of the new features.

Filling based on a selected source layer (or layer group)

Using the erase mode to clean up a region from the outside

Drag-select fill (!)

9

Now i see the flood fill tool is perfect x3
i’m thinking about learning python to improve mypaint feature (like making selection tool) do you have any advice, where should i start from or what i need to know? thank ya :smiley:

10

Thank you! It’s far from perfect, but a great deal more useful than it was.

As for learning python, my recommendations would depend on your level of experience with other languages and programming in general. My general advice would be to build up a gradual understanding of the syntax, data structures, built-in facilities and standard library - mostly through playing around with small personal projects, but also by reading (and doing) tutorials and the reference documentation.
You don’t need to learn a ton of computer science, but rudimentary complexity theory is very useful to have under your belt.

In the specific case of mypaint, the user interface code is pretty much exclusively python (if you don’t count the libraries it depends on), but the backend (the core data structures and algorithms) consists of both python and C/C++. When you see a call from python into mypaintlib - it is using functions/structures implemented in C/C++.

If you want to explore the code base, I would recommend installing PyCharm Community edition and learning the code navigation capabilities of that IDE - it will make it a lot easier to get an overview of how things fit together than manually jumping around between different files (which is what I did for a long time).

Also, don’t be discouraged if you realize that a problem is more complicated than you initially thought - this is almost always the case. Don’t be afraid to make mistakes, at least not after learning and using version control. :slight_smile:

1 Like
11

Thank for your advice, very helpful x3
yah when i explored Mypaint source, i manually jumped around those files lol xD

12

I have implemented cancelling and status updates for fill operations. If the fill runs for longer than a set time period, a dialog window appears informing the user of the status of the operation (which stage it is in, how many tiles are filled (if filling), number of tiles to process (morphing, blurring, compositing) and the percentage of completion for the stage. If the user presses escape or the cancel button on the dialog (or closes the dialog), the fill is cancelled pretty much immediately and any changes it had time to do are undone.

I would like feedback/opinions on a couple of issues related to this, one perhaps more technical than the others.

First: how slow is too slow? Half a second? One second? The tricky issue here is to avoid starting the dialog when the time remaining for the fill is too short to even react to it - this is not possible to determine with certainty, except for in the compositing (final) stage (with reasonable error margins). Though harmless, it might be annoying to see a dialog flash.

Secondly: Should a cancelled fill that is not run via a redo command affect the redo stack? Clearly such a fill should not be added to the undo stack - there is nothing to undo, the redo stack is a different issue. Krita clears the redo stack even for cancelled operations. It’s not strictly necessary, but perhaps expected?

The options here (for a cancelled, non redo-run, fill) are:
1: Clear the redo stack and do nothing with it
2: Don’t touch the redo stack, if you reached this point by undoing a bunch of changes, you can still redo them if you cancel the operation.
3: Clear the redo stack and put the cancelled operation on it - this might make sense if you cancelled a long-running op accidentally, but the fill still has to be redone upon running a “redo”.

Personally I favour 1 for consistency, but am interested in other thoughts.

Finally, on a more technical note: Is the Escape-key emergency exit still necessary, and if so , can it be moved to key press instead of key release? This functionality was added over ten years ago, so I’m not hopeful that anyone knows all the details of its addition, but the issue is that if you press escape to cancel the fill, and don’t release the key before the fill cancelling is done, the subsequent release triggers the emergency exit, which from the users perspective would just be a switch to regular brush mode they did not ask for.

Moving it to the press callback would avoid the issue. I can see why it was written into release (for convenience), but no reason it cannot be moved to press with some adjustments.

13

This feature is merged in master! I will be uploading an appimage and pre-release installers in a few minutes. Thank you @jpll and @dothiko !

I had a couple thoughts after finally playing with this thing for a bit. Right now it uses the composite mode of the Brush mode (more or less). I was wondering what you think about exposing a composite mode dropdown with all or many of the composite mode options? Super cool that you have it already rigged to allow any of the modes, though!

Another idea, could be to dig into the current brush settings to figure out if the user is using Pigment mode instead of linear, or even a blend of several modes? Would it make sense overlay several fills for the active brush modes? Maybe overkill. But maybe we could use the current brush opacity (or a separate slider) to let a user fill an area with semi-transparent paint?

Of course, what got me thinking was when I noticed the blending was linear RGB instead of the non-linear pigment. So for the moment I’ve hard-coded the mode to 21 in my dev build. The difference is very obvious when using the feathering option (the left is linear and the right is the pigment mode):

https://i.imgur.com/2UGHwnf.png

In any case, awesome work!

1 Like
14

Yes, I was thinking about that as well. The only reason not to include it would perhaps be “choice overload” for new users. Some other conditional stuff in the back end would need updating as well, since right now it only assumes “Normal”, “Destination out”, and “Source atop” modes for some skip optimizations. We would also have to consider how this should work with the erase and alpha locking modes.

This idea, among others, was floated in this feature request.

Personally I think it’s better to have explicit per-tool settings for things like this. I know I would be confused if the fill tool started to act differently just because I’d switched brushes.

My own workflow almost always involves having the fill on separate layers and changing opacity is naturally no issue there, but if there are use cases where a separate opacity setting would be useful, I can add it.

Edit: Apparently this functionality exists in Krita, both for blend modes and opacity. Each tool uses its own opacity setting, whereas the blend mode is seemingly global. Also, in Krita the eraser mode seems to override the other blend modes (which seems reasonable).

For combining alpha locking with arbitrary blend modes in MyPaint, this would either require two composition passes or amending the blend functions.

15

Ah, yes, many exceptions and weird issues trying to combine all those modes. I guess for alpha locking we could wrap up the compositing with DestinationIn mode? It gets very confusing :wink:

I see what you mean, a new layer lets you use whatever layer mode you want and opacity… It’s really cool you can select another layer as the source, although that doesn’t seem to work for alpha locking or eraser (not even sure how eraser could possible work there, but alpha locking seems at least possible).

All this starts to expose the difference between compositing operations and blending operations… which we can only really combine (for now) via layer groups. Ah well, it’s looks good enough for now! :slight_smile:

16

Both alpha locking and erasing does work when using another source layer (second gif above gives one demonstration), but one has to keep in mind that we are filling with reference to the source layer, but acting on the active layer.

Erasing from an empty layer never produces anything of course, so if the selected layer is empty, there is nothing to erase (and the comp is skipped). Same with alpha locking for empty areas.

Apart from existing empty layers, the only other case where erase and alpha locking definitely makes no sense is when using the “New Layer” toggle. In order to not waste time, the actual fill is skipped if erase or alpha locking is enabled in combination with this toggle. I should perhaps add some warning sign with an explanation in the UI for that scenario as well (the new layer is still created, just a new empty layer).

This can definitely be confusing and I’ll make sure to include some examples of how it works, and what kind of things it can be used for, when writing user docs.

Edit: I just realized that some strangeness on your dev build might be caused by conditionals not assuming the use of Pigment mode for compositing. I’ll robustify any such conditionals tomorrow.
Edit 2: Yep, a compositing skip assumed that:
(mode != CombineNormal) ≡ (mode == SourceAtop || mode == DestinationOut)
Meanwhile the mode docstring erroneously advertised that it accepted any mode, fixing it now.
Edit 3: Arbitrary blend modes and adjustable opacity is now implemented (not thoroughly tested as of writing). It didn’t clutter up the UI as much as I feared and the double-pass compositing for alpha locking is quite clean.

1 Like
17

Awesome, thanks for adding those extra features! It’s really pretty fun to fill with low opacity and different modes just to see what happens. All the modes look pretty good so far, although I can’t really vouch for the Destination/Source modes as I’m still not entirely sure how they work! :stuck_out_tongue:

18

I’ve always the thought the names to be a bit too jargon-y for something user facing, but I guess there’s value in following conventions as well.

Destination Out ~ masking out / erase that which overlaps w. fill
Destination In ~ masking in / erase everything that does not overlap w. fill
Destination Atop ~ CombineNormal + masking in on top / erase pixels not overlapping, compose overlapping pixels on top of new fill.
Source Atop ~ mask fill / alpha locking, the fill only affects non-transparent areas it overlaps

Destination Out and Source Atop should arguably be removed from the dropdown, since those modes are covered by the erase and alpha locking (with normal mode) blend mode modifiers.