You could do instant flood-fill on a slow PC in the early 90s. There is no need to precompute this. The possible issues are:
1. You're using a slow algorithm. This is almost certainly the case, looking at how slowly it run and at the order in which pixels get painted. The Wikipedia page on flood fill is enough to find a good algorithm.
2. Possibly, the overhead of individual canvas operations is high, so setting each pixel at once is slow. If this is the case, it would be partially ameliorated by using a span-based algorithm, but you could also run the algorithm on an offscreen byte array and then blit the result to canvas.
I would bet money that a 90s state-of-the-art algorithm running in JavaScript on an offscreen array will be perceived as instantaneous on a modern computer.
Note that you loose 1-2 orders of magnitude just by the screen resolution (in the early nineties we used 640x480, sometimes even 320x200 vs 4K nowadays). Another order of magnitude is lost by using a more high level programming language, which sure you could probably optimize down to factor 2-3. Plus sublinear scaling of stuff like memory latency since the 90s. All in all I agree we should be able to do better, but it is by no means trivial.
If you are right that would be amazing! The demo code is open source, please send a PR with such a flood fill implemented.
The requirement is that when the user clicks on a 2k x 2k image it takes 50ms or less, running on a cheap Android tablet. If a better algorithm, perhaps implemented in wasm, can achieve this, I’d love to discard all my complex code and just use it
I love that everybody commenting here here emphatically insists that you must be doing it wrong, but real-world solutions are nowhere to be found. I admire your commitment to keeping a positive tone, but you'd be justified in feeling some frustration.
I do hope a PR shows up in the next few days so the internet can stop having this debate and move on with a good library.
There are fast segment based fill algorithms from the seventies or very early eighties in the literature and reprinted in the first volume of Graphics Gems. They work very well and do not require the call stack or amount of computation of simpler methods.
1. You're using a slow algorithm. This is almost certainly the case, looking at how slowly it run and at the order in which pixels get painted. The Wikipedia page on flood fill is enough to find a good algorithm.
2. Possibly, the overhead of individual canvas operations is high, so setting each pixel at once is slow. If this is the case, it would be partially ameliorated by using a span-based algorithm, but you could also run the algorithm on an offscreen byte array and then blit the result to canvas.
I would bet money that a 90s state-of-the-art algorithm running in JavaScript on an offscreen array will be perceived as instantaneous on a modern computer.