Hacker News Reader

Comment by RandallBrown | Hacker News Reader

Seems like there must be a better way?

https://paintz.app seems to be able to do this without precomputing all of the spaces you could flood.

The naive method is slow because it repaints the image several times. A faster way is a sort of double buffering: copy the image to an array, perform the fill on the array, copy the array to the canvas image data.

The method in TFA is however faster for static images, after the preprocessing.

There’s a trade off between speed and showing progress to the user. I find it better to show slow progress rather than wait 500 - 1000ms to do it faster, but it depends on the use case

Wikipedia lists a bunch of Flood Fill algorithms. It looks like they all involve some form of checking every pixel one-by-one:

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

I was hoping the author had figured out some clever solution involving some implementation detail of HTML Canvas.

For a typical users use case, I bet you could downscale the image 16x (using the GPU, and therefore very fast), flood fill on the much smaller image (using slow javascript over each pixel), then expand the image up to the original size and reprocess just the border pixels (and there aren't many border pixels compared to the total filled area).

This method might not produce perfect results when the paint can 'escape' through a tiny gap that isn't visible on the downscaled version... But at the same time, I suspect most users don't actually want the paint to escape through a tiny gap, so that might be the right behaviour.

Been a long time since I was a kid playing with Deluxe Paint, but "fill except where I missed a tiny gap" would have been exactly what I wished the fill tool would do! I don't think I've used a fill tool in earnest since :-(

Wouldn't you get a super pixelated version of your original image back? Downscaling is lossy.

You wouldn't upscale, you'd fill 16x16 blocks in original image iterating over downscaled image and if the block wasn't all the same color you'd process it normally. In fact you don't need to flood fill in downscaled image, just do edge detection.

There is a option in getContext called willReadFrequently that specifies that pixels are read often maybe that would help.

Author here: in the app I use that, it seems to help alright

What are your thoughts on this?

http://www.adammil.net/blog/v126_A_More_Efficient_Flood_Fill...

Thanks for the link, it’s great write up. I’ll play with his algorithm to see how it works for me, it may speed up the pre-processing. Its still slower to the user than using the pre generated masks however

I'd expect that you could achieve the speed that won't be perceptibly different from the "preprocessed". The modern browsers JIT the JS code and the canvas abstractions map correctly to the hardware. A better fill algorithm (cache friendly -- the traversal has to be as much as possible through the points which are actually one after another in memory and avoiding unnecessary calls or adding to some structures when loops are enough) and avoiding unnecessary canvas updates should result in instantaneous-enough responses? Using masks is probably a good/necessary idea to provide complex fill patterns, but I'd expect the masks could be made on-demand, which then makes the freehand drawing possible (which would invalidate the precomputed masks).

willReadFrequently disables the use of the GPU. All canvas operations will be software rendered on the javascript thread. The actual operations happen not when you make the draw() call, but when you read any pixel of the canvas.

Reply on news.ycombinator.com