4 ms·

Seems like there must be a better way? https://paintz.app https://paintz.app seems to be able to do this without precomputing all of the spaces you could flood

Seems like there must be a better way? https://paintz.app https://paintz.app seems to be able to do this without precomputing all of the spaces you could flood.

occamrazor 3y ago
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.
- shaneos 3y ago
  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
evan_ 3y ago
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 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.
- londons_explore 3y ago
  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.
  - yetanotherloser 3y ago
    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 :-(
  - eastof 3y ago
    Wouldn't you get a super pixelated version of your original image back? Downscaling is lossy.
    - ajuc 3y ago
      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.
dvh 3y ago
There is a option in getContext called willReadFrequently that specifies that pixels are read often maybe that would help.
- shaneos 3y ago
  Author here: in the app I use that, it seems to help alright
  - acqq 3y ago
    What are your thoughts on this? http://www.adammil.net/blog/v126_A_More_Efficient_Flood_Fill.html http://www.adammil.net/blog/v126_A_More_Efficient_Flood_Fill...
    - shaneos 3y ago
      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
      - acqq 3y ago
        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).
- londons_explore 3y ago
  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.

Seems like there must be a better way? https://paintz.app https://paintz.app seems to be able to do this without precomputing all of the spaces you could flood.

occamrazor 3y ago

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.

shaneos 3y ago
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

evan_ 3y ago

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 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.

londons_explore 3y ago
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.
- yetanotherloser 3y ago
  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 :-(
- eastof 3y ago
  Wouldn't you get a super pixelated version of your original image back? Downscaling is lossy.
  - ajuc 3y ago
    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.

dvh 3y ago

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

shaneos 3y ago
Author here: in the app I use that, it seems to help alright
- acqq 3y ago
  What are your thoughts on this? http://www.adammil.net/blog/v126_A_More_Efficient_Flood_Fill.html http://www.adammil.net/blog/v126_A_More_Efficient_Flood_Fill...
  - shaneos 3y ago
    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
    - acqq 3y ago
      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).
londons_explore 3y ago
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.