Explaining the fill function: An HTML5 canvas Flood Fill that doesn’t kill the browser

I took the longest time implementing the fill tool  on Mandalagaba. How hard could it be? Recurse through pixels looking for a color and update them to a new color.

While this method certainly works and is easy to implement, it is also extremely slow. Slow in a way that hangs the browser, yielding infamous messages from the browser.

Screen-Shot-2018-06-22-at-10.01.53-AM.png

Here we’ll take a look at various Javascript flood fill implementations along with their drawbacks. Jump to #4 if you are only interested in the best one.

In all cases, the code is available in the example iframe, look for the function flood_fill.

Screen_Shot_2018-06-23_at_3_07_40_PM.png

1. Simple Recursive

Not much to explain here, we simply recursively call the function on adjacent pixels when they match the color we are trying to fill over.

See example of the recursive technique by clicking on this link.

It’s reasonably fast but the problem with this one is that any fill area slightly large yields too much recursion which breaks subsequent JS. This Canvas box is 200x200px and at 300x300px, Firefox complained about:

Screen-Shot-2018-06-22-at-1.47.31-PM.png

It’s easy to see how this implementation will not satisfy a reasonably featured paint program. Even if your browser let you stack more function on the heap, I would bet it would lead to slowness.

2. Iterative

We simply take the previous idea of looking at adjacent pixels and filling them, and make it iterative instead so the function calls don’t get stacked to a ceiling.

See example of the iterative technique by clicking on this link.

The problem with this is is that is is sloooow. So slow it stalls browser. Most of time is spent having to keep track of pixels_stack. Recursion doesn’t have that need but as we’ve seen, it has other issues.

3. Recursive-Iterative (AKA catch-your-breath iterative)

This is a twist on #2 which every so often, recurses on itself via a setTimeout to let the browser catch it breath a little. It also yields a cool visual effect.

See example of the recursive-iterative technique by clicking on this link.

I really like the visual effect, and it makes the slowness tolerable. But the issue is that Mandalagaba has a network engine and allows for re-rendering of one’s work. So synchronization is a big deal, and you know what makes synchronization easy? Not having to worry about it.

So as long as I can help it, my life is a lot easier if the operations the users can perform are atomic. Operations need to be able to be processed one after the other counting on the fact that the ones that came before have completed.

The first 2 solutions are atomic but suck; this 3rd one, however cool it may be, isn’t.

4. The Holy Grail

 

I’m not sure where this algorithm originated from, but I’ve gotten to know it on this web page which explains it very well (with GIFs!). It is iterative and goes about finding pixels to fill in a much smarter way.

See example of the holy grail by clicking on this link.

That’s it, no drawback here 🙂 I’ve tested it on large canvasses and this is what is implemented on Mandalagaba. Now of course, in a real application there is a ton more complexity dealing with smoothing edges and blending alpha. I only wanted to expose boiled down versions of these algorithms so they are easier to wrap your mind around.

Feel free to ask questions in the comments.

(This text was originally written on Ben's amazing blog)