Bucket Fill Tool Behavior Regression / Re-Implementation

[Jose-Moreno]

Issue Summary

Hi I've made a video to encompass two of the key features that should be brought back. Even back then (2016) I've been consistently asking for the fill tool to have this option of a layer selection or "target"

Currently the two main regressions or re-implementations, considering the tool has been refactored quite a bit, would be:

• [ ] Color Bleed: Bring back the function to automatically color a different layer based on the active layer that is being colored (e.g lineart)
  • [ ] Add the option to select up to which layer would the color transpose itself. By default it would always source and target the active layer.
  • [ ] Add the option to color multiple layers with the same layer "filter" e.g Source layer can be one or many and Target layers can be one or many.
• [ ] Color Spill: Bring back the pixel color expansion when filling the same area
  • [ ] Add an option toggle so this is not default behavior
  • [ ] Add a pixel expansion slider, or use the color tolerance to determine how much it can "bleed"

I think ideally this should be implemented before the tracing & coloring PR #1178 mainly so David's implementation can support itself on this existing behavior and become further simplified in the coloring part and since we always try to strive for simplicity yet for the tools to work functionally and thoroughly, one of the main issues I've been having with the pipeline process is that the thinning and the blending portion might only be needed for the color separation part, if we had the Color Bleed and Color Spill functionalities back as I explain in the video, of course this is subject to discussion as well, but I can only see it as a powerful asset and one that's been consistently requested by actual artists using Pencil2D consistently for their work.

Let me know what you think.

Video or Image Reference

https://youtu.be/VULg2ONoo9o

System Information

• Pencil2D Version: 0.5.4b

Some of the changes made to modify the original behavior were made in #687 by @CandyFace but I'll keep looking for other PR's that might have modified this further to help out have a better picture of the required work.

[davidlamhauge]

@Jose-Moreno I've looked at this video (again) and I don't really get it. You have two layers. You draw the circles on the Lineart layer. You do the first fill on the Lineart layer. Then you change layer to Color layer, and does the expansion fill. Is that right? Of the explanations above, I don't understand the Color Bleed. How do one use multiple source and target layers? Color spill should be fairly easy to implement. i would do it in a manner, where the Color layer always was colored based on the layer above. Then, when you made a fill, you could easily see the artefacts, and then you could click again, until the artefacts disappeared.

[Jose-Moreno]

@davidlamhauge Hi.

The Color Bleed that I show working in the video is how Pencil2D 0.5.4 had a way to literally color a second layer that was below, automatically, and without extra input on the user's behalf.

There was no need for naming conventions, or extra buttons. If you only had one layer, if would color the actual lineart layer instead (which is what we do now basically)

Ever since this was removed, I've always been vocal about how we should bring that back to avoid all the additional computations and interfaces from other methods.

Also to clear any confusion, before 0.6.0 the layer stack worked differently and the bottom most layer was always shown "above" everything and viceversa. So I'm not coloring the "color" layer by itself, i simply clicked on the "lineart" layer.

The color spill, or clicking several times to expand the fill, was also present and to me it was always an intuitive way to do things when getting rid of the "halos" after filling a feathered stroke, and I never understood why it was removed.

Regarding the multiple source and target layer ideas, here's the gist of it: To avoid repeating the same problems we had with the color bleed, having hard coded layer targets that can confuse the user, the proposal was that the user could pick which layer would act as a target, or recipient of this color fill, relative to the currently selected layer.

So if i select the lineart layer, pick the bucket tool, in the options panel i would find a "layer target" menu list that is filled with an array of all the other layers of the same type (e.g bitmap) including a "self layer" option.

If I choose to fill the color layer below lineart, I would STILL use the lineart layer as the alpha boundary to restrict where the color goes in the target layer.

As for having multiple layers colored, it's the same principle, but this would allow me to for example, pick several layers to be colored and several layers to be used as the source; it's an enhancement over the previous concept.

This would enable the user to make, for example, a single lineart layer as the source and have several other layers to be filled by levels, of course we would also need a way to quickly switch which level you're filling when using the bucket tool. In photoshop or krita when you click a place with several overlapping layers while pressing a modifier key, you can select which layer you're going to fill accordingly, so if we could use a source layer to define what is painted, that would make multi-level painting quick efficient.

However I initially thought the use case for a different idea, by having many lineart layers, and a single "color layer" that received input from all of them. So if I happily selected and filled different lineart layers in their respective strokes, this would end up in a single color layer if I wanted to.

Anyway, I hope that's more understandable. Thank you for taking the time to review this.

[davidlamhauge]

I've looked at this again, and it still puzzles me. I can't think of a way to get the expansion fill to work, if you color on the same layer as the artwork. If it's on a separate layer, it should be fairly easy to implement. Did the expansion fill work, when you filled on the same layer as the artwork?

[MrStevns]

For reference, here's the old floodfill code from Pencil 0.4.4b where the click to expand is present

void BitmapImage::floodFill(BitmapImage* targetImage, BitmapImage* fillImage, QPoint point, QRgb targetColour, QRgb replacementColour, int tolerance, bool extendFillImage) {
    QList<QPoint> queue; // queue all the pixels of the filled area (as they are found)
    int j, k; bool condition;
    BitmapImage* replaceImage;
    if(extendFillImage) {
        replaceImage = new BitmapImage(NULL, targetImage->boundaries.united(fillImage->boundaries), QColor(0,0,0,0));
    } else {
        targetImage->extend(fillImage->boundaries); // not necessary - here just to prevent some bug when we draw outside the targetImage - to be fixed
        replaceImage = new BitmapImage(NULL, fillImage->boundaries, QColor(0,0,0,0));
        replaceImage->extendable = false;
    }

    QPen myPen;
    myPen = QPen( QColor(replacementColour) , 1.0, Qt::SolidLine, Qt::RoundCap,Qt::RoundJoin);

    targetColour = targetImage->pixel(point.x(), point.y());
    queue.append( point );
    // ----- flood fill
    // ----- from the standard flood fill algorithm
    // ----- http://en.wikipedia.org/wiki/Flood_fill
    j = -1; k = 1;
    for(int i=0; i< queue.size(); i++ ) {
        point = queue.at(i);
        if(  replaceImage->pixel(point.x(), point.y()) != replacementColour  && rgbDistance(targetImage->pixel(point.x(), point.y()), targetColour) < tolerance ) {
            j = -1; condition =  (point.x() + j > targetImage->left());
            if(!extendFillImage) condition = condition && (point.x() + j > replaceImage->left());
            while( replaceImage->pixel(point.x()+j, point.y()) != replacementColour  && rgbDistance(targetImage->pixel( point.x()+j, point.y() ), targetColour) < tolerance && condition) {
                j = j - 1;
                condition =  (point.x() + j > targetImage->left());
                if(!extendFillImage) condition = condition && (point.x() + j > replaceImage->left());
            }

            k = 1; condition = ( point.x() + k < targetImage->right()-1);
            if(!extendFillImage) condition = condition && (point.x() + k < replaceImage->right()-1);
            while( replaceImage->pixel(point.x()+k, point.y()) != replacementColour  && rgbDistance(targetImage->pixel( point.x()+k, point.y() ), targetColour) < tolerance && condition) {
                k = k + 1;
                condition = ( point.x() + k < targetImage->right()-1);
                if(!extendFillImage) condition = condition && (point.x() + k < replaceImage->right()-1);
            }

            replaceImage->drawLine( QPointF(point.x()+j, point.y()), QPointF(point.x()+k, point.y()), myPen, QPainter::CompositionMode_SourceOver, false);

            for(int x = j+1; x < k; x++) {
                condition = point.y() - 1 > targetImage->top();
                if(!extendFillImage) condition = condition && (point.y() - 1 > replaceImage->top());
                if( condition && queue.size() < targetImage->height() * targetImage->width() ) {
                    if( replaceImage->pixel(point.x()+x, point.y()-1) != replacementColour) {
                        if(rgbDistance(targetImage->pixel( point.x()+x, point.y() - 1), targetColour) < tolerance) {
                            queue.append( point + QPoint(x,-1) );
                        } else {
                            replaceImage->setPixel( point.x()+x, point.y()-1, replacementColour);
                        }
                    }
                }
                condition = point.y() + 1 < targetImage->bottom();
                if(!extendFillImage) condition = condition && (point.y() + 1 < replaceImage->bottom());
                if( condition && queue.size() < targetImage->height() * targetImage->width() ) {
                    if( replaceImage->pixel(point.x()+x, point.y()+1) != replacementColour) {
                        if(rgbDistance(targetImage->pixel( point.x()+x, point.y() + 1), targetColour) < tolerance) {
                            queue.append( point + QPoint(x, 1) );
                        } else {
                            replaceImage->setPixel( point.x()+x, point.y()+1, replacementColour);
                        }
                    }
                }
            }
        }
    }       
    fillImage->paste(replaceImage);
    delete replaceImage;
}

and its usage:

            if( toolMode == BUCKET) {
                BitmapImage* sourceImage = ((LayerBitmap*)layer)->getLastBitmapImageAtFrame(editor->currentFrame, 0);
                Layer* targetLayer = layer; // by default
                int layerNumber = editor->currentLayer; // by default
                if( editor->currentLayer > 0) {
                    Layer* layer2 = editor->getCurrentLayer(-1);
                    if(layer2->type == Layer::BITMAP) {
                        targetLayer = layer2;
                        layerNumber = layerNumber - 1;
                    }
                }
                BitmapImage* targetImage = ((LayerBitmap*)targetLayer)->getLastBitmapImageAtFrame(editor->currentFrame, 0);
                BitmapImage::floodFill( sourceImage, targetImage, lastPoint.toPoint(), qRgba(0,0,0,0), brush.colour.rgba(), 10*10, true);
                setModified(layerNumber, editor->currentFrame);
            }

[davidlamhauge]

@Jose-Moreno, I would like to work on this now. I don't know if you've seen my question from July 2020. I forgot to mark it with you name, so chances are that you've not seen it. (in the following : spill fill = expansion fill.) To have a source layer with your line art/drawing, and select a target layer to the spill fill coloring, should be fairly easy to implement. To have a source layer and multiple target layers is not so easy, and I'm having a hard time to understand why someone would want that? To have spill fill on the same layer as the line art will not be possible. If someone else can implement, then please be my guest. I can't. The best thing (for me, at least) is if we could talk things over on Discord, so I'm sure we understand each other. Is that possible, or are you in a busy period?

[scribblemaniac]

To have spill fill on the same layer as the line art will not be possible. If someone else can implement, then please be my guest. I can't.

This actually shouldn't be any more difficult than doing it on another layer. All you have to do is draw your fill on a new image, and then either paste it on the current layer or another layer depending on where the target is.

The real challenge is probably going to be expanding the fill area. Conceptually it's very simple, but I anticipate that implementing it in an efficient manner will be very difficult. The current scanline fill algorithm is good, but it does not lend itself well to expansion to the left or upwards especially.

[davidlamhauge]

I don't really get it. Sorry. If I fill on current layer and paste, like you say, what do I do then, if the user wants to expand the fill area? At this point the image is gone, and the paste is done. What is it I don't see or understand?

[scribblemaniac]

@davidlamhauge I think we're both envisioning this working in a different way. The way I imagine this implemented is that there would be a slider in the tool settings for fill expansion, and then it would expand the fill by that much at the time it is being filled. So if your filling on the current layer it would go something like this:

1. Users clicks on a target pixel.
2. Find the region matching the target pixel withing some threshold specified in the tool settings.
3. Expand the region by some number of pixels specified in the tool settings.
4. Fill region with the current color, either on the current layer or another layer.

Doing it this way, you would not be able to change the expansion after the fact. The so called "color spill" behavior would actually be accomplished as a side effect of how the region selection and expansion works. When you click the same region multiple times, you will naturally be selecting the previously filled region because it will all be the same color, and then you will be expanding it by the expansion amount, so each time it will increase in size by that amount on it's own.

Thinking about this does lead me to an important question about color bleeding and how everyone here is expecting it to behave. What would the tool be looking at for finding the initial region: the current layer, or the current layer combined with the fill layer. Consider for example that you have a fully enclosed circle which you then fill on a layer below. Then you erase a section of the circle outline, and then fill it again. Should it be filling just the colored area, or should it be filling everything outside the new gap as well? Separately, what about if a user tries to fill an opaque region such as their lines? Are we going to let it silently fill underneath and give the user the impression that the fill tool is not doing anything?

[davidlamhauge]

Yeah, it's hard to know what we mean with the words. So, first of all, from now on I think I'll call it FloodFill and ExpandFill. FloodFill is what we have now and ExpandFill is what should be re-implemented. Just to be sure @scribblemaniac , that I understand you right: If we do ExpandFill on the same layer, it will in reality be filled on another image, and pasted on the original afterwards. If you're not happy with the result, then you can Undo, try a higher value on the slider, and ExpandFill again. Is that right? I hope so. If you do ExpandFill on a separate layer, then you can do a fill, and then press again to expand the first fill. As long as your fill-color equals the color on the pixel you press, this will continue. This is how I've come to understand it. If I'm not corrected, I think I'll start working on it tomorrow or the day after.

[davidlamhauge]

What would the tool be looking at for finding the initial region:

I just realized that I didn't address your questions, @scribblemaniac . I think we have covered the same-layer fill. If we choose fill on a separate layer, we have a source layer with the artwork, and a target layer, for the fill. The expand fill will first of all look for a transparent pixel on the source layer. If you click somewhere on the source layer that is not transparent, there should be no fill. If the pixel on the source layer is transparent, it will investigate the same pixel on the target layer: 1) If the target pixel is transparent, it will do a regular fill on the target layer, based on the artwork on the source layer. 2) if the target pixel color is equal to the fill color, it makes an expand color with one or more pixels, as selected on the slider. That could be from 1-5, or something. 3) If the target pixel color is different from the fill color, it replaces the color with the new fill color.

That's how I understand it. Am I correct @Jose-Moreno ?

[scribblemaniac]

@davidlamhauge, @Jose-Moreno and I discussed this topic in a recent call. I don't feel qualified to give a full summary of that conversation, but I bring up some key points I and and elaborate on them a bit.

First I want to review how the expand and bleed features (as I will be calling them in this post), were implemented in ancient (0.5.x) times. The fill would always be expanded by exactly one pixel beyond the region the matches the target color within the given threshold, and there was no setting to change this expansion. If there was a bitmap layer below the current layer, this would effectively enable the bleed behavior. This bleeding would select a region based only on the current (source) layer, and would fill the layer below (target layer), expanded by one pixel from the region selected from the source layer. Now if bleeding was disabled, it would fill the region, and one pixel around it with exactly the same color. If you click on that region again, it naturally selects everything that was just filled, because everything in that fill area has the same color as your current target pixel. It was then expanded by 1 pixel, resulting in a total expansion of 2 from region selected the first time the fill was done. So you could click repeatedly to expand the fill more.

Now to how I think it should be done now. I think the algorithm used back then was largely on the right track, but the following changes should be made to it:

• Make the default fill behavior only fill to the current layer. Bleeding can be enabled with a setting in the tool options. In my opinion this option should be a combobox which allows you to: select fix any bitmap layer as the target layer (although this raises the question of what should happen when the project changes), or set it to the current layer, or set it to an arbitrary offset from the current layer (layer above, layer below, etc.).
• Add a tool option setting for the amount of expansion in pixels (0 by default?). This would be a slider and spin box combo similar to the brush size or feather settings.
• A warning is shown if bleed is enabled and the flood fill is entirely obscured by the current layer. I do worry that some people are going to set the bleeding on one project, forget about it, and then won't understand why it's isn't filling right on another project. If there's absolutely no visual indication that the tool is doing anything, then I think it might be acceptable to have a dismissible warning dialog.
• A feathering option. I am surprised this has not been brought up yet. Another slider which would allow the edge of the fill to be feathered would be nice, and is something fairly common in other programs. This may be out of scope for these changes, but if we keep it in mind while we implement this we may be able to make it easier to implement in the future.

Now one other point I wanted to touch upon is related to the second last change. I do believe that the bleeding should work even if the target pixel on the source layer is opaque. Here is my main proposed motivation for such a behavior. Imagine you have already been working on a Pencil2D project for a while and filling it with the existing fill tool. There is haloing around your fills because you used a feathered brush. Now you upgrade to a new and improved version of Pencil2D which has bleed and expand features. You've already filled in some of your work, but you want to take advantage of the bleed/expand to clean up the edges of the fill. You should be able to set the expand to something large enough to go under your stroke's feather, set up a fill layer for bleeding, and fill and expand existing filled areas on a layer below. This will result in cleaner lines than expanding the fill on the current layer (ie. without bleeding) because you won't be replacing part of the stroke with the fill color but rather putting it underneath the stroke, which presumably has translucent edges.

[davidlamhauge]

It was a very good, informative and constructive session we had yesterday @scribblemaniac and @Jose-Moreno. Thanks! Because of the time zone challenge, I had to go at one point, and I was not present when the feathering option was discussed. I don't know why we would want that option, and I have no idea on how to code it, and I'm also uncertain about the fill beneath filled areas, so I've un-assigned me from the issue for now. That opens up for some one else to give it a try. I might give it a try at a later point, if no one else can, but right now I don't feel confident to take on the task.

[davidlamhauge]

As said, I've un-assigned myself from this issue. That doesn't mean that I'm not thinking of it, and now I've done a solution that I can understand. You'll find a video here: https://youtu.be/2H4_wdXhRlY

I don't say this is THE solution. It could be a input, a part of the solution, or something that could be rewritten to become a solution. I don't know.

[Jose-Moreno]

@davidlamhauge I saw your video. I think it looks great and it's a great step forward 👏 It's basically what I'd expect of a "fill expand" option. I can't comment on the internals of the implementation, but visually it looks like it gets the job done.

There were certainly some spots that seemed to have a slightly different result under the 3px rule, like the bottom left corner of the first drawing in the video where you zoomed in, but I think that's a minor issue in aggregate. Other software also have similar problems and what they do is implement other tools to finalize difficult spots to fill.

I'd like to know as well what the others thing of it, but so far so good 💪