Shader FloodFill Alogrithm

Question

I'm new to openGL and shaders.

Is there a way to implement shader algorithms for floodfills?

Basically, I have a picture with outlines and i want to fill the insides of where the user touches it

Answer 1

The above method was not only outdated for 2017, but extra-ordinarily slow. There are dedicated algorithms to do what you're talking about on the GPU that take maximal advantage of GPU parallelism.

There are several methods for filling an area on the GPU, but it greatly depends on your situation. Technically this is called "connected component labelling" unfortunately there's a huge disconnect between the game dev world and academia, so you likely aren't going to find this kind of information in the game dev space.

The idea is that you label each pixel in your image with an ID, figure out what is connected to it, and then label the whole thing as the parent ID. Then when you actually fill things, you just check each pixel with the ID you wanted to fill

When the user interacts with the image, the bucket tool touches some pixel, that pixel gets a connected components ID that corresponds with many pixels, and then you just check for each pixel whether it matches the bucket pixel, and set it to the bucket color.

The algorithm described in the below resources works via splitting the work up into row blocks that the GPU processes in parrallel.

First turn your image into a binary image (where your border is = 1, and where it isn't = 0). The algorithm then works via processing labels for each element in each row, calculated at the start via the actual linear address id (0,1,2,3...) only labelling starting segments. Then parent labels are created bewteen rows, each row taking the lowest linear address id that is connected to each contigous segment as it's parent id. Then this process repeats for borders between groups of rows.

Finally, now that the parent ID has been figure out for all rows for all segments, connected component labels can be flattened to only the parent ID.

There's a lot of "the rest of the owl" in what I just said, so you you'll need to read the paper to understand how it works fully, but the main thing to understand is this isn't an iterative image algorithm that only works in parallel on the frontier, it's completed in a discrete number of steps.

See this PDF for more details, there are several algorithms to look at as well, timing is shown below.

https://developer.download.nvidia.com/video/gputechconf/gtc/2019/presentation/s9111-a-new-direct-connected-component-labeling-and-analysis-algorithm-for-gpus.pdf

and this paper of the same thing:

https://hal.science/hal-01923784/document

Github https://github.com/DanielPlayne/playne-equivalence-algorithm

8 way version (cardinal plus diagonal connections between each pixel)

https://github.com/FolkeV/CUDA_CCL?tab=readme-ov-file

While the examples are in cuda, with the proper feature set, this should translate rather directly to compute shaders. Note that to take advantage of this algorithm you're going to need access to subgroup operations, this requires vendor specific OpenGL extensions IIRC or enabling subgroup support in vulkan (since 1.1 ie 2018), in addition to atomic operations.

Answer 2

As Bálint noted in a previous answer, shaders are designed to be highly parallel, which makes them an awkward fit for flood-filling.

In parallel execution, the GPU's many cores are making decisions about what colour to paint each pixel for gobs of pixels all at once. Since these decisions happen at the same time, the outcome of one can't depend on the outcome of the other. If it did, the whole thing would grind to a halt and we'd use only a tiny sliver of its power computing a few pixels at a time in dependency order. Shader languages deliberately make it difficult to express this kind of dependency, so we get the most out of our graphics hardware.

But that's a challenge for algorithms like flood fill. Knowing whether the fill reaches pixel (x, y) depends on whether the fill reached at least one of its neighbouring pixels (x - 1, y) (x + 1, y) (x, y - 1) (x, y + 1). And each of those depends on their neighbours.... Usually on the CPU we plow through this recursively or with a queue/stack, but that's not an option for pixel/fragment shaders.

(Compute shaders let us break this rule a bit, but it's not exactly a free lunch there either - I'll let someone with more experience in compute explain how that style could be applied in this case. Thankfully, Krupip rose to that challenge and shared some more efficient algorithms that work with compute shaders, with some pre-processing steps to identify connected regions)

But even if you're not comfortable wading into compute shaders and academic papers just yet, all is not lost! Instead of trying to completely solve each pixel in dependency order, we can instead incrementally / partially solve a subset of the image in parallel, and iterate.

More sophisticated algorithms can work on bigger chunks of the image at a time, but here's a simple naïve method that does the job for small images without any pre-processing:

1. We define two temporary textures to track our fill-in-progress.

2. We draw a white pixel into the first temporary texture at the seed position of our flood.

3. We "blit" from this first temporary texture into our second temporary, with a shader that:

   i. Reads the outline texture to decide if the current pixel being shaded is a line. If so, abort (return black / not-filled)

   ii. Reads the corresponding pixel and its immediate neighbours from the first temporary texture. If any of them are white / filled, then return the same. Otherwise return black / not filled.

This is a kind of dilate filter, except it's limited by the outline texture. Run just once, it will bleed our initial seed pixel out into a diamond or square of pixels, depending on which neighbours you count.

3. Now we blit back from the second texture into the first one, using the same shader - we've just exchanged the input and output textures.

4. Keep blitting back and forth. Each blit spreads our fill a bit further until the area is filled.

To keep it simple you can set a maximum number of passes based on the size you expect your fill areas to be, and stop after that many. A more advanced solution could use GPU queries to identify the first blit where no new pixels are filled.

5. Lastly, render back into your outline texture, tinting it to the fill colour wherever the most-recently-updated temporary texture says should be filled.

Obviously all this iterative blitting takes time, which is why Bálint advised against doing it this way. But keeping this work GPU side isn't automatically wrong - sometimes you might choose to do it that way if the CPU is too busy with something else, or to avoid a stall when shunting the data back and forth.

(Animation by Finlay McWalter, via Wikipedia, CC BY-SA 4.0)

You can also make this blitting back and forth work for you, by spreading it over several frames and showing the player the colour spreading out from the location they chose. This both avoids a slowdown while you do all the blitting, and gives a neat-looking visual effect, if that works for your context. ;)

There are other things you can do to speed this up, like masking each execution pass to the portion of the image that could change, or downsampling and filling a smaller-scale image, then upsampling and running the full-res flood fill on hopefully just a few remaining gaps.

Performance is always contextual though, so I'd recommend trying it in a simple way first, then post a new question if it's not performing the way you want, and we can give customized feedback on how to improve it.