4 ms·
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
by kragen 3y ago
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)
- shaneos 3y agoIf 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 agoNot 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 agoi 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 agoprobably 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 agoI 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 agoyou'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 agoactually 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 agobtw, 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
- Falvyu 3y agoYou 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 agoThanks, 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 agoI 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'.
- thrashh 3y agoThere'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 3y agoI 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
- johnfn 3y agoI've tried writing a fast flood fill in JS and it's a lot more challenging than you and GP make it out to be. If it's really so straightforward, you should produce code. Otherwise, these comments don't add much to the discussion.
- kragen 3y agoi'd be surprised if someone could do it within the editing window for an hn comment, but it doesn't seem like more than a day or two of work for double-digit megapixel fill rates
- johnfn 3y agoA proper flood fill needs to iterate over an enormous ImageData object (or at the very least a huge 2d array) and page in/out memory as appropriate. Your code appears to just increment a variable. This is not a valid comparison.
- kragen 3y agothe comment you are replying to explains that already, right above the code the question of memory access time is quite deep in shane's example of flood-filling a 2048 × 2048 image in 16ms, the image is 16 mebibytes; if you have less ram than that, so that you have to page in and out (as your comment says you do), you are not going to be able to do the computation fast enough. but my hand-me-down cellphone has 256 times that much ram so i guess you're using a pentium pro 200 or something, in which case you aren't going to be able to run a browser that supports canvas assuming you're using a computer from the current millennium, one which has enough ram to run a browser that supports canvas, you won't need to do any paging, but you do need to think about dram bandwidth. probably the required bandwidth to dram is 2 gigabytes per second (one read and one write), while typical current ddr4 systems provide on the order of 30 or 40 gigabytes per second. that assumes you can keep the memory access reasonably sequential (if your l2 cache is less than those 16 mebibytes). this is usually the case with a simple line-by-line flood-fill algorithm, like the one used by gw-basic 40 years ago, but there are pathological images where it is not consider a 1-pixel-black/1-pixel-white square double spiral that fills the full 4 mebipixels. whether a fill in the white covers all the white or just half of it depends on every single black pixel, so algorithms that can do this with better locality and a reasonable amount of parallelism are inherently going to be relatively hairy but images like that cause problems for shane's existing algorithm too because they will make shane's web worker spin for a long time