Flood Fill to also fill up non-closed spaces

[pimhendriks]

I was just reading about the Flood Fill algorithm on Wikipedia.. I know; of all places.

https://en.wikipedia.org/wiki/Flood_fill

The difference I am seeing is, in Designer currently, all islands need to be closed off by a black border yet in the article we see images like this. Does this lie in future for the Flood Fill node?

[divi.cig]

i might be intentionally misunderstanding your question here, but how are those areas not closed off by a black border?

[justaviking]

i might be intentionally misunderstanding your question here, but how are those areas not closed off by a black border?

I was wondering the same thing.

[pimhendriks]

I jumbled my phrasing a little bit but I'm talking about the fact that the current Flood Fill node can't deal with this.

to

[Esger van der Post]

The flood fill node works a bit different from the examples you're showing. For one thing, it doesn't just fill in an area with 1 solid color, but actually generates uv coordinates which are dependent on the size of the filled in area, so this brings a lot more complexity into the mix. Also, designer isn't very good at iterative processes, while the gifs you show would require thousands of iterations. The floodfill node only seems to use 20 steps, which they've apparently managed by taking incrementaly larger steps, as you can see here. But this means it only goes in 1 direction.


However I think it should be possible to recreate something similar to your second gif by using distance nodes. I may give that a go myself, as it seems fun to experiment with. I already know it will be a bit performance heavy though, and also you'd have to specify a point from which the flooding starts (much like in your examples)

[Esger van der Post]

Actually, scratch that last bit. The distance node works a little bit different than I thought =/

[pimhendriks]

You might be right Eggfruit, but I'd really like some insight from one of the devs on this.

[Cyrille Damez]

One should never say never, but I am afraid it is very unlikely to happen. As far as I know, the ability to fill arbitrary shapes with "holes" requires a real flood fill algorithm, which probably cannot be implemented efficiently. For those interested in the theory, this is because filling such areas requires some sort of way to create and keep track of "branches" in the filling process, and therefore needs to use some sort of branching recursion or a stack.

[pimhendriks]

Thanks for chipping in Cyrille! So a real flood fill is not possible but what about a multi-directional (+X/-X/+Y/-Y) substitute against a (big) performance hit (probably)?

[Esger van der Post]

Allegorithmic's method may be near impossible for this, but I couldn't help myself and tried recreating one of the classic methods (the left one of your gifs).


As I mentioned, this requires quite a few samples to do.
Filling this island took 2048 pixel processors for a total of 12288 samples *per pixel*.
Filling this star requires twice as many. It would take less at lower resolutions though.


This could be optimized a bit though.
I could hopefully somehow take a lot more samples per pixel processor, which would speed it up a little and maybe add some "cheaty" functionality to jump x amount of pixels per sample. Or maybe by starting at a very low resolution and turn it up every x number of steps.
Filling all islands with different colors is probably possible without needing more samples, but fancy stuff like gradients is a no-go.
Maybe I can find some time here and there over the next couple of days/weeks.

[Sergey Danchenko]

I guess my Randomize Mask node implements something close to a Flood Fill algorithm as in the OP. It's a brute force approach with some optimizations, but it's quick enough to be usable on practice. As a benefit, it can tackle almost any shape given enough iterations  .

It was designed to fill an array of islands with random luminance values (but keep this value the same inside a given island) to create a random luminance mask from/for bitmap images.

On images attached below you can see how the node will spread values across shapes in iterations, with the end result in the last frame.

Some time later I've found that a random angle gradient can be applied to such shapes using additional processing (see last image).

The node mentioned above is released and thoroughly commented, so anyone interested can take a peek inside. 

By the way, Eggfruit, you've pretty much described how Randomize Mask node come together. It's a bunch of Pixel Processor nodes with something like "ray casting" functionality. Each Pixel Processor samples a number of pixels (I've stopped at up to 8 px per iteration) to the left/right/top/bottom from current coordinate and stops if it finds a black one (i.e. island border). Then it assumes min or max sampled value as a value for a processed pixel. In this way, min/max pixels can be spread throughout the islands without crossing the island's borders. To optimize it, you indeed can reduce resolution at which computations are being made, and it will drastically affect performance in a good way.

Some links:

https://forum.allegorithmic.com/index.php/topic,5158.0.html
https://forum.allegorithmic.com/index.php/topic,16547.0.html
https://www.artstation.com/artwork/1alxX

[Esger van der Post]

Oh man, I can't believe I completely forgot about this thread. I've even been using your optimized auto levels for ages.
Your randomize mask is definitely has some nice optimization with the resolution stepping. And I like your contraction filter to prevent bleeding between cells. I was really struggling with that.

Did you ever get around putting your slope mask up for download? Even if it still has some issues I'd be very interested in playing around with it

[Sergey Danchenko]

No, I've stopped working on it since Flood Fill was released. The node is functional, but requires some love on the organizational side. Judging from this topic, it looks like the node still may be useful for some cases where Flood Fill can't operate properly. I'll look into finishing and releasing it. 

[pimhendriks]

Hey Sergey, I'm happily surprised to see you drop in! I remember reading your communication with Pawel but hadn't realized I was looking for the same solution. Thanks again for that write-up, for your appearance here and this incredibly well documented node setup. You reached a very good solution for this.

Please do consider a temp or full node release. It definitely has an advantageous position over the current flood fill at a computational cost.

[Sergey Danchenko]

  Looks like my gradient node won't support tiling for now. It does work with donut-like shapes, but I can't figure out how to make the gradient to wrap correctly on islands that located on both sides of the mask (i.e. that need to tile). Can't have everything at the same time, eh?.. 

The most unfortunate thing is that I'm pretty confident it can be done, but at this time I'm lacking a required math background to make it happen.