4 ms·

If a wasm algorithm can run in under 16ms for arbitrarily large images that would be amazing. Hard to beat pre-computing all possible fills however, as the user

If a wasm algorithm can run in under 16ms for arbitrarily large images that would be amazing. Hard to beat pre-computing all possible fills however, as the user perceives it as instant. If you’ve seen a really fast wasm solution I’d love to replace the fill portion with it though.

kragen 3y ago
[flagged]
- shaneos 3y ago
  Not trolling. I haven’t played with wasm at all. Perhaps if it can fill a 2k x 2k pixel image super fast it would be indistinguishable from my solution. If someone had coded this and open sourced it I’d love to use it
  - gfd 3y ago
    i used opencv.js a few years ago and it was fast enough to process videos frame by frame for stuff way more complicated than just floodfill. See https://docs.opencv.org/4.7.0/d5/d10/tutorial_js_root.html https://docs.opencv.org/4.7.0/d5/d10/tutorial_js_root.html
  - kragen 3y ago
    probably fill rates of 240 megapixels per second are going to be hard to reach consistently in javascript but 60 (1k × 1k) seems likely achievable without much in the way of tricks
irskep 3y ago
I think people in this thread are being much too optimistic about browser performance. Writing a loop isn't the issue; memory access patterns are. Canvas implementations are just not well suited for the flood fill problem space. (I spent some time with flood fills + canvas ten years ago when I was working on the now-dead library Literally Canvas, but I assume that experience is pretty far out of date now.) Precomputing fill areas is a really good idea for the situation you're in! Edit: actually it was 7 years https://github.com/irskep/literallycanvas-pro-tools/blob/master/src/tools/PaintBucket.js https://github.com/irskep/literallycanvas-pro-tools/blob/mas...
- kragen 3y ago
  you're calling fillRect in your inner loop it also has 10 other method and function calls in it, one of which allocates a new 4-element array also it's maintaining a stack of pixels to paint instead of looping over a scan line each iteration of the loop paints one pixel i don't think canvas memory access patterns are the root of the performance problem i'm not saying it's bad code, just that it doesn't justify your conclusion
  - kragen 3y ago
    actually on further examination i think each four iterations of the loop paint one pixel in the most common case, because each pixel in a large filled area gets visited from each of its neighbors
    - kragen 3y ago
      btw, i want to point out that shaneos's request for an 'algorithm [that] can run in under 16ms for arbitrarily large images' is obviously constructed to be impossible no flood-fill algorithm can run in less than 16ms, or less than any finite time, for arbitrarily large images; they necessarily require at least linear work and, even with arbitrary parallelism (itself impossible in a finite universe), logarithmic time you need to bound the image size if you are going to bound the execution time so this is not a good faith request; it is, rather, a deliberately impossible task, like spinning straw into gold, finding an acre of land between the salt water and the beach, making a cambric shirt with no seams or needlework, or reaping a crop with a sickle of leather unfortunately my previous comment pointing this out has been flagged and is therefore generally no longer visible; i consider this sort of response to a purely logical argument of impossibility to be astoundingly mean-spirited and contemptible
- ghusbands 3y ago
  No, JS and Canvas aren't the issue, there; the code you wrote will perform terribly in any language on any platform. You used a four-way recursive per-pixel fill algorithm. You should probably do a bit of reading on flood fill algorithms (maybe read the Wikipedia flood fill article).
Falvyu 3y ago
You can probably make the process extremely fast by replacing the flood-fill approach with a something based on a Connected-Component Labeling algorithm ( https://en.wikipedia.org/wiki/Connected-component_labeling https://en.wikipedia.org/wiki/Connected-component_labeling ). There's a good amount of literature on the subject and it's often included in computer vision libraries (e.g. OpenCV). You'd first threshold the image by checking if a pixel is 'close enough' to the clicked pixel. This will create a B&W image. Then you call the CCL on this binary image to produce a labelled image: each pixel will contain the id of its component (i.e. which enclosed space it belongs to). Once you have this, it's just a matter of replacing colors on the canvas for pixels with the same id as the clicked pixels. Obviously, that's just the 'theory' part. If you can find a good library that includes one then you'll have to integrate it. Otherwise, you'll have to re-implement that in Javascript, which is easier said than done and may also not reach the desired performance.
- shaneos 3y ago
  Thanks, I’ll take a look at the article. This generally sounds very similar to my pre processing algorithm, setting the id of the enclosing area into each pixel so a fast/instant operation can be applied. Am I missing something though? In my solution, the only thing that happens when the user clicks is a fillRect() call. Is your suggestion similarly fast on click?
  - Falvyu 3y ago
    I think the main difference is that the CCL would compute 'enclosed areas' on the fly. To be more specific, it would first create a mask (black & white) of pixels that are similar to the clicked pixel, and then find connections between foreground/white pixels. I don't work in web development but accelerating CCL algorithms do happen to be my area of expertise. While their execution time depends on the image content, you can expect them to be in the tens of milliseconds for a 4K image, at least for the 'modern' one you can find in OpenCV, and on current consumer-level CPUs, without multi-threading. Of course, implementing these newer algorithms isn't straightforward. That's why you should instead use something like OpenCV if you have the option to. Moreover, if CCL doesn't fit what you're looking for then you can also check out watershed algorithms ( https://en.wikipedia.org/wiki/Watershed_%28image_processing%29 https://en.wikipedia.org/wiki/Watershed_%28image_processing%... ). Because they don't work on binary image, they might be a better way to describe what you call 'enclosed space'.

kragen 3y ago

[flagged]

shaneos 3y ago
Not trolling. I haven’t played with wasm at all. Perhaps if it can fill a 2k x 2k pixel image super fast it would be indistinguishable from my solution. If someone had coded this and open sourced it I’d love to use it
- gfd 3y ago
  i used opencv.js a few years ago and it was fast enough to process videos frame by frame for stuff way more complicated than just floodfill. See https://docs.opencv.org/4.7.0/d5/d10/tutorial_js_root.html https://docs.opencv.org/4.7.0/d5/d10/tutorial_js_root.html
- kragen 3y ago
  probably fill rates of 240 megapixels per second are going to be hard to reach consistently in javascript but 60 (1k × 1k) seems likely achievable without much in the way of tricks

irskep 3y ago

I think people in this thread are being much too optimistic about browser performance. Writing a loop isn't the issue; memory access patterns are. Canvas implementations are just not well suited for the flood fill problem space. (I spent some time with flood fills + canvas ten years ago when I was working on the now-dead library Literally Canvas, but I assume that experience is pretty far out of date now.) Precomputing fill areas is a really good idea for the situation you're in! Edit: actually it was 7 years https://github.com/irskep/literallycanvas-pro-tools/blob/master/src/tools/PaintBucket.js https://github.com/irskep/literallycanvas-pro-tools/blob/mas...

kragen 3y ago
you're calling fillRect in your inner loop it also has 10 other method and function calls in it, one of which allocates a new 4-element array also it's maintaining a stack of pixels to paint instead of looping over a scan line each iteration of the loop paints one pixel i don't think canvas memory access patterns are the root of the performance problem i'm not saying it's bad code, just that it doesn't justify your conclusion
- kragen 3y ago
  actually on further examination i think each four iterations of the loop paint one pixel in the most common case, because each pixel in a large filled area gets visited from each of its neighbors
  - kragen 3y ago
    btw, i want to point out that shaneos's request for an 'algorithm [that] can run in under 16ms for arbitrarily large images' is obviously constructed to be impossible no flood-fill algorithm can run in less than 16ms, or less than any finite time, for arbitrarily large images; they necessarily require at least linear work and, even with arbitrary parallelism (itself impossible in a finite universe), logarithmic time you need to bound the image size if you are going to bound the execution time so this is not a good faith request; it is, rather, a deliberately impossible task, like spinning straw into gold, finding an acre of land between the salt water and the beach, making a cambric shirt with no seams or needlework, or reaping a crop with a sickle of leather unfortunately my previous comment pointing this out has been flagged and is therefore generally no longer visible; i consider this sort of response to a purely logical argument of impossibility to be astoundingly mean-spirited and contemptible
ghusbands 3y ago
No, JS and Canvas aren't the issue, there; the code you wrote will perform terribly in any language on any platform. You used a four-way recursive per-pixel fill algorithm. You should probably do a bit of reading on flood fill algorithms (maybe read the Wikipedia flood fill article).

Falvyu 3y ago

You can probably make the process extremely fast by replacing the flood-fill approach with a something based on a Connected-Component Labeling algorithm ( https://en.wikipedia.org/wiki/Connected-component_labeling https://en.wikipedia.org/wiki/Connected-component_labeling ). There's a good amount of literature on the subject and it's often included in computer vision libraries (e.g. OpenCV). You'd first threshold the image by checking if a pixel is 'close enough' to the clicked pixel. This will create a B&W image. Then you call the CCL on this binary image to produce a labelled image: each pixel will contain the id of its component (i.e. which enclosed space it belongs to). Once you have this, it's just a matter of replacing colors on the canvas for pixels with the same id as the clicked pixels. Obviously, that's just the 'theory' part. If you can find a good library that includes one then you'll have to integrate it. Otherwise, you'll have to re-implement that in Javascript, which is easier said than done and may also not reach the desired performance.

shaneos 3y ago
Thanks, I’ll take a look at the article. This generally sounds very similar to my pre processing algorithm, setting the id of the enclosing area into each pixel so a fast/instant operation can be applied. Am I missing something though? In my solution, the only thing that happens when the user clicks is a fillRect() call. Is your suggestion similarly fast on click?
- Falvyu 3y ago
  I think the main difference is that the CCL would compute 'enclosed areas' on the fly. To be more specific, it would first create a mask (black & white) of pixels that are similar to the clicked pixel, and then find connections between foreground/white pixels. I don't work in web development but accelerating CCL algorithms do happen to be my area of expertise. While their execution time depends on the image content, you can expect them to be in the tens of milliseconds for a 4K image, at least for the 'modern' one you can find in OpenCV, and on current consumer-level CPUs, without multi-threading. Of course, implementing these newer algorithms isn't straightforward. That's why you should instead use something like OpenCV if you have the option to. Moreover, if CCL doesn't fit what you're looking for then you can also check out watershed algorithms ( https://en.wikipedia.org/wiki/Watershed_%28image_processing%29 https://en.wikipedia.org/wiki/Watershed_%28image_processing%... ). Because they don't work on binary image, they might be a better way to describe what you call 'enclosed space'.