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:
-
We define two temporary textures to track our fill-in-progress.
-
We draw a white pixel into the first temporary texture at the seed position of our flood.
-
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.
-
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.
-
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.
- 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.
