# should flood fill algorithm pay attention to existing alpha? #481

Closed
opened this issue Nov 4, 2015 · 5 comments

Projects
None yet
4 participants

### jeisner commented Nov 4, 2015

 Many brushes produce a stroke that has opaque pixels in the middle of the line, but fades away at the edges by using increasingly translucent pixels. If you outline a circle with such a brush, and then flood-fill its interior with an opaque color, the fill declines to overwrite the translucent pixels. Since the translucent pixels were barely there in the first place, it appears as if a gap has been left between the circle's outline and the circle's fill. Is there a sensible way to make the algorithm interpolate so that the interior really looks filled all the way to the edge? If you are filling with red (alpha=0.8) and you hit a pixel that is blue (alpha=0.3), then I think the fill should indeed change that pixel. It should now have alpha=0.8, and the color should be a blend -- 3/8 blue (from the old pixel) and 5/8 red (from the fill color). (I think this has the same effect as a red alpha=0.8 with a blue alpha=0.3 on top of it, right?) The question is where the fill algorithm should stop. Right now it seems to be blocked by any pixel that has alpha > 0. Perhaps if you're filling with alpha=0.8, then it should only be blocked by pixels that have alpha >= 0.8? Anything with alpha < 0.8 would be interpolated with the fill color; in particular, the fill color would be fully used when alpha=0. Warning: Under this heuristic, if you fill the interior enclosed by a translucent outline with an more opaque color, the opaque color will bleed through the translucent outline (interpolating) and get past it. I wonder, is that a problem? Or is it okay, even desirable? Note: On #474, in answer to a question from @achadwick, I gave my opinion that flood fill should use the current brush's alpha value. In other words, filling when the current brush is low-opacity should fill with translucent pixels. This is why I spoke above of filling with alpha=0.8. However, the present ticket is still relevant even under the current implementation, which can only fill with alpha=1.0. Note: The discussion above assumes that you clicked on a completely transparent pixel. If you click on a non-transparent pixel, then I suppose this interpolation isn't necessary. Either you are going to exactly fill the connected region that has identical color to what you clicked on (the current design), or the connected region that has the same stroke ID or brush settings to what you clicked on (as suggested on #474). In either case, the resulting color and alpha should just come from the current brush, although in colorize or alpha lock mode, this means that the existing color and alpha contribute information as well. I admit that if you fill the interior of the circle with red as above, and then re-fill it with a new color, the red/blue interpolated region will not be re-interpolated as one would like - it will just be changed to the new color, or not changed at all.
Member

### achadwick commented Nov 4, 2015

 @jeisner Do you have any sample code or proposed patches for any of this? Please make the discussion more concrete if you can. It sounds like you have some good ideas, but I don't have the time to test or develop any of this myself right now. Linking to real code implementing the algorithm you propose would be great. Testing stuff independently and seeing what works would be better. You may want to look at #296. BTW, the MyPaint issue tracker is not an open-ended discussion forum for all things MyPaint, and opening new issues for sub points of already hypothetical enhancements is beginning to get a little wearing. It will (trust me on this) result in the tracker getting very cluttered very quickly and unproductive for people searching for bugs. I also worry about maintainer burnout too! Can you maybe consolidate issues more, shoulder some of the development burden you are proposing? (I'm certainly not averse to enhancement requests, but I feel they should be progressed into working code as soon as they can be, or into something that somebody could pick up and work on at least. There is, naturally, an open issue about what this issue tracker should be: #365 (though right now I'm tending towards "anything which doesn't overwhelm me"! 🌊😄))
Author

### jeisner commented Nov 5, 2015

 @achadwick Yeah, sorry that I've been posting a lot. In fact I'm pretty much done with my beta test. I'd seen the request on the website to look at the beta, so I tried to systematically explore different features of the application. Flood fill is a new feature AFAIK, so I was testing it to see whether it behaves "correctly" in various circumstances. There are a couple of respects in which it didn't give the results that I had personally expected, so I posted about those. More generally, what I've been trying to help with is spotting current problems (candidate fixes for the upcoming release) and opportunities to streamline the UI (not as urgent, but when I noticed missing cases or odd interactions as I tested, I thought I should point them out). I've definitely appreciated your responses -- questions, discussion, patches. I understand that more adventurous suggestions may not be implemented, at least not soon. When posting, I've tried to be as concrete about design as I can be, to be helpful to anyone who is willing to pick up the idea now or later. At least there will be some notes around for them when they search. It is not out of the question that I might try to fix or enhance something myself, if I can do it without learning the whole codebase. For example, the present ticket might be mostly a localized change in lib/fill.cpp. But there are many interactions in a system this big and well-engineered. Since I'm a newcomer who doesn't necessarily understand how all the features and bits of implementation fit together, or why things are currently designed or implemented as they are, it would be unwise for me to attempt an enhancement unless a core developer first says, "Yeah, we'd like that and that's a good design." Regarding "consolidating issues more": My assumption has been that if two enhancements could reasonably be done separately, then they should be separate issues so that they can be closed separately. You'd prefer to keep them as one issue if they're thematically related, rather than two cross-referenced issues?

Member

### odysseywestra commented Nov 9, 2015

 This is basically asking for way to fill the gap left over when the fill tool is filling an area of a brush that does not have a hard edge. The solution @AtsusaKaneytza came up with was adding an expand x amount of pixels options as explained in #73 which is deferred till after 1.2 is out because strings are frozen currently. So I would say this is a duplicate of #73.

### jplloyd added a commit to jplloyd/mypaint that referenced this issue Jul 27, 2018

``` Floodfill refactoring, split module, new C++ impl ```
```Split out the python part of the floodfill algorithm to its own module.
Replace the C++ parts of the floodfill with a new implementation.
Improve fill performance by special handling of empty/uniform tiles.
Only write alpha channel for intermediate fill data.
Add new function to perform coloring and composition in the same step.
Alter pixel test to ignore rgb channels for 0-alpha target colors.

by the performance improvements.

Partially addresses mypaint#481 by altered transparency test,
but only covers the case where target color is _fully_ transparent.```
``` 7ae3452 ```

### jplloyd added a commit to jplloyd/mypaint that referenced this issue Jul 27, 2018

``` Add feathering to floodfill ```
```Implement fake gaussian blur using iterated box blurring.
Blur radius restricted to one tile width.
Update call chain and parameter documentation.

Partially addresses mypaint#481 as this enables
fills to be more easily blended into gradient-like outlines```
``` fc341c3 ```

### jplloyd added a commit to jplloyd/mypaint that referenced this issue Jul 27, 2018

``` Floodfill refactoring, split module, new C++ impl ```
```Split out the python part of the floodfill algorithm to its own module.
Replace the C++ parts of the floodfill with a new implementation.
Improve fill performance by special handling of empty/uniform tiles.
Only write alpha channel for intermediate fill data.
Add new function to perform coloring and composition in the same step.
Alter pixel test to ignore rgb channels for 0-alpha target colors.

by the performance improvements.

Partially addresses mypaint#481 by altered transparency test,
but only covers the case where target color is _fully_ transparent.```
``` 8128321 ```

### jplloyd added a commit to jplloyd/mypaint that referenced this issue Jul 27, 2018

``` Add feathering to floodfill ```
```Implement fake gaussian blur using iterated box blurring.
Blur radius restricted to one tile width.
Update call chain and parameter documentation.

Partially addresses mypaint#481 as this enables
fills to be more easily blended into gradient-like outlines```
``` 1edd993 ```

### jplloyd added a commit to jplloyd/mypaint that referenced this issue Jul 29, 2018

``` Floodfill refactoring, split module, new C++ impl ```
```Split out the python part of the floodfill algorithm to its own module.
Replace the C++ parts of the floodfill with a new implementation.
Improve fill performance by special handling of empty/uniform tiles.
Only write alpha channel for intermediate fill data.
Add new function to perform coloring and composition in the same step.
Alter pixel test to ignore rgb channels for 0-alpha target colors.

Partially addresses mypaint#885 and mypaint#157 by the performance improvements.

Partially addresses mypaint#481 by altered transparency test,
but only covers the case where target color is _fully_ transparent.```
``` c3513b5 ```

### jplloyd added a commit to jplloyd/mypaint that referenced this issue Jul 29, 2018

``` Add feathering to floodfill ```
```Implement fake gaussian blur using iterated box blurring.
Blur radius restricted to one tile width.
Update call chain and parameter documentation.

Partially addresses mypaint#481 as this enables fills to be more
``` e968e25 ```

### jplloyd added a commit to jplloyd/mypaint that referenced this issue Mar 24, 2019

``` Floodfill refactoring, split module, new C++ impl ```
```Split out the python part of the floodfill algorithm to its own module.
Replace the C++ parts of the floodfill with a new implementation.
Improve fill performance by special handling of empty/uniform tiles.
Only write alpha channel for intermediate fill data.
Add new function to perform coloring and composition in the same step.
Alter pixel test to ignore rgb channels for 0-alpha target colors.

Partially addresses mypaint#885 and mypaint#157 by the performance improvements.

Partially addresses mypaint#481 by altered transparency test,
but only covers the case where target color is _fully_ transparent.```
``` 09a6167 ```

### jplloyd added a commit to jplloyd/mypaint that referenced this issue Mar 24, 2019

``` Add feathering to floodfill ```
```Implement fake gaussian blur using iterated box blurring.
Blur radius restricted to one tile width.
Update call chain and parameter documentation.

Partially addresses mypaint#481 as this enables fills to be more
``` 29d8c4e ```

### jplloyd added a commit to jplloyd/mypaint that referenced this issue Apr 1, 2019

``` Floodfill refactoring, split module, new C++ impl ```
```Split out the python part of the floodfill algorithm to its own module.
Replace the C++ parts of the floodfill with a new implementation.
Improve fill performance by special handling of empty/uniform tiles.
Only write alpha channel for intermediate fill data.
Add new function to perform coloring and composition in the same step.
Alter pixel test to ignore rgb channels for 0-alpha target colors.

Partially addresses mypaint#885 and mypaint#157 by the performance improvements.

Partially addresses mypaint#481 by altered transparency test,
but only covers the case where target color is _fully_ transparent.```
``` 8b84ed1 ```

### jplloyd added a commit to jplloyd/mypaint that referenced this issue Apr 1, 2019

``` Add feathering to floodfill ```
```Implement fake gaussian blur using iterated box blurring.
Blur radius restricted to one tile width.
Update call chain and parameter documentation.

Partially addresses mypaint#481 as this enables fills to be more
``` 98676b1 ```

### jplloyd added a commit to jplloyd/mypaint that referenced this issue Jun 1, 2019

``` Floodfill refactoring, split module, new C++ impl ```
```Split out the python part of the floodfill algorithm to its own module.
Replace the C++ parts of the floodfill with a new implementation.
Improve fill performance by special handling of empty/uniform tiles.
Only write alpha channel for intermediate fill data.
Add new function to perform coloring and composition in the same step.
Alter pixel test to ignore rgb channels for 0-alpha target colors.

Partially addresses mypaint#885 and mypaint#157 by the performance improvements.

Partially addresses mypaint#481 by altered transparency test,
but only covers the case where target color is _fully_ transparent.```
``` 361493d ```

### jplloyd added a commit to jplloyd/mypaint that referenced this issue Jun 1, 2019

``` Add feathering to floodfill ```
```Implement fake gaussian blur using iterated box blurring.
Blur radius restricted to one tile width.
Update call chain and parameter documentation.

Partially addresses mypaint#481 as this enables fills to be more
``` 520c869 ```
Member

### jplloyd commented Jun 19, 2019

 I'm not sure if this should be closed, since there are multiple proposals here. The scenarios with the fuzzy outlines can now be approached by using a combination of offset and feathering to blend in to it. In the case of wanting to fill out from the inside of a fuzzy stroke or shape, one can now use an offset with alpha lock enabled to cover the gradient without making it opaque. As for filling with an alpha other than 1.0, I don't see a reason not to simply filling to a separate layer, whether above or below, and adjusting the opacity of that layer. Personally I would be quite confused if a seemingly unrelated tool changed behaviour after a brush switch.
Member

### jplloyd commented Jul 15, 2019

 Fill tool now has an independent opacity setting. I believe the addressable concerns here have now been addressed.