[HN Gopher] Instant flood fill with HTML Canvas
___________________________________________________________________
Instant flood fill with HTML Canvas
Author : shaneos
Score : 59 points
Date : 2023-05-23 19:18 UTC (3 hours ago)
(HTM) web link (shaneosullivan.wordpress.com)
(TXT) w3m dump (shaneosullivan.wordpress.com)
| ianlevesque wrote:
| Ha, painting tablet app feels like a rite of passage for
| programmer parents. Here's mine from that era
| https://paints.netlify.app/
|
| Where it got really interesting later was when one of my kids
| asked how I made it, how it worked, how they could add new
| features. So it grew a bunch of adorable haphazard hacks that my
| oldest implemented.
| shaneos wrote:
| Very cute! I started out with basically this, and my kids kept
| asking me for more and more features :-). Recently they asked
| to make animations, and that took a chunk of time to get right.
| I'm looking forward to whatever they ask for as they grow more
| advanced!
| sharikous wrote:
| Wonderful, the fact that it runs as expected in multi touch
| devices has not gone unnoticed!
| Waterluvian wrote:
| When it comes to performance, I find you really need to
| experiment with HTML Canvas. Some of the interfaces can be
| hundreds to thousands of times slower for manipulating the canvas
| than others.
| zachrip wrote:
| This works well for the problem space - does it work well for a
| drawing app where the canvas is always changing?
| shaneos wrote:
| It can be made work. Precompute the image when the flood fill
| tool is activated and it's fine, since you only have to do it
| once
| ZiiS wrote:
| Tbh adding a background pixel only needs to check its four
| surrounding to see if it joined seperate areas, adding a
| fourground is harder I expect you need Dijkstra.
| rattray wrote:
| Interesting - what behavior would you want there? Statically
| filled area, or a shifting area depending on the other pixels?
| RandallBrown wrote:
| For an app like this I would expect it to be static.
| Basically the same behavior MS Paint has had for decades.
| kragen wrote:
| the summary is that they preprocess the image to partition it
| into a disjoint set of fillable regions, but i feel like this
| maybe has to be redone whenever you mutate the image
|
| maybe other optimization approaches would yield a flood-fill
| algorithm that just runs fast enough in js; wasm can surely do it
|
| like i feel like you can probably loop over the pixels in a scan
| line until you encounter an obstacle at several tens of
| megapixels per second
|
| as the dumbest possible test of js perf, this code (admittedly
| not accessing an imagedata object) gets about 250 million
| iterations per second on my 2.6 gigahertz palmtop in firefox
| function tri(n) { let x = 0, y = n; while(y--) x += y; return x }
| s = new Date(); console.log(tri(10_000_000)); console.log(new
| Date() - s)
| thrashh wrote:
| There's no reason a JIT'd runtime is going to find this job
| challenging or slow at all.
|
| I don't know what OP's original code is but maybe OP was
| calling a Canvas API method for every pixel (super bad).
| shaneos wrote:
| I wasn't calling per pixel :-) even when just visiting each
| pixel once it would still take 50 - 100ms to fill a large
| image which the user perceives as lag. I wanted it to be
| instant
| shaneos wrote:
| 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.
| irskep wrote:
| 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. (To be
| fair, I last 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/mas...
| kragen wrote:
| 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 wrote:
| you say
|
| > _If a wasm algorithm can run in under 16ms for arbitrarily
| large images that would be amazing_
|
| that would indeed be amazing, because nothing that might
| change every pixel can run in any fixed period of time on a
| fixed number of processors for arbitrarily large images; it's
| necessarily linear time in the worst case, if not worse
|
| so there is no way that can be a sincere sentence
| shaneos wrote:
| 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 wrote:
| 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
| ninepoints wrote:
| Surprised "jump flooding" hasn't been mentioned yet, which is the
| common technique to accelerate this sort of thing (used for color
| fills, signed distance field construction, outlines, etc.).
| shaneos wrote:
| Author here: I'm loving all the suggestions of ways that this
| might be achievable in either a faster or simpler method! The
| code is open source at https://github.com/shaneosullivan/example-
| canvas-fill and I'd love to see you hackers improve on it and
| share it with everyone. Any and all improvements I'll happily use
| going forward in my app.
| TazeTSchnitzel wrote:
| Why does it need separate mask images? Couldn't you use the
| indices in the alpha layer to do the flood-fill by looping over
| every pixel in the image and changing the colour if the index
| matches? It would save memory, right? That per-pixel loop should
| be fast enough, since there's just one pass and it's simple
| enough any JS JIT ought to be able to optimise it.
| shaneos wrote:
| The speed is achieved by getting use the fillRect() command
| with globalCompositeOperation. This is a single draw operation
| rather than a per pixel algorithm while the user waits.
| Anything more involved than with would, I think, be slower as
| perceived by the user
| chrisweekly wrote:
| This reminds me of an iOS puzzle game I really enjoyed a year or
| two ago called "Kami 2". Picture a canvas with geometric shapes
| in a few different colors. The goal is to paint the whole canvas
| in one color, armed with a limited number of "fill" operations.
| Highly recommended.
| RandallBrown wrote:
| 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.
| occamrazor wrote:
| 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 wrote:
| 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_ wrote:
| 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.
| londons_explore wrote:
| 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 wrote:
| 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 :-(
| dvh wrote:
| There is a option in getContext called willReadFrequently that
| specifies that pixels are read often maybe that would help.
| shaneos wrote:
| Author here: in the app I use that, it seems to help alright
| acqq wrote:
| What are your thoughts on this?
|
| http://www.adammil.net/blog/v126_A_More_Efficient_Flood_Fil
| l...
| londons_explore wrote:
| 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.
___________________________________________________________________
(page generated 2023-05-23 23:00 UTC)