Instant flood fill with HTML Canvas
shaneosullivan.wordpress.com
shaneosullivan.wordpress.com
This part really resonated with me. Google promotes the absolute worst spammy shit these days. I have to browse tech forums to find clean simple games.
Last week I was trying to find a simple memory cards game and the search results were complete dog shit so I started building my own memory cards game. In a couple hours I made https://memorycardsgame.com/. Then browsing a svelte forum I found https://toddler-games.com which is much further ahead of mine but I'd never be able to find stuff like this by searching for it. Of course none of the good games are filled with a bunch of SEO spam which is kind of the point. Since Steve Jobs didn't let his kid use an iPad we've decided the game isn't needed now.
Nice app.
Nice! Small bit of feedback: when you click “restart” after winning, the emojis are replaced with new ones right before the flip animation plays, which briefly reveals the solution. I’m assuming that’s a bug and not an intentional hint, as it doesn’t happen the first time.
My 5 y/o is having great fun with the Crayola app and Cooking Mama, and, honestly, between each round, I'm waiting for an ad to pop, a nag screen to pay for stuff or review, a countdown or some other crap we're accustomed to on mobile games and no. Nothing. Just the full game and nothing else. It's a refreshing experience.
There's always DOSBox!
a potential drawback is that it seems like the paths could be several times larger than the original image (consider a checkerboard pattern, where each pixel is its own fill area, or the pathological spiral pattern i suggested in a comment below)
Here's an example https://en.m.wikipedia.org/wiki/Connected-component_labeling
https://scikit-image.org/docs/stable/api/skimage.measure.htm...
I guess you are doing the same thing and memoizing the graph ahead of time. Perhaps find an optimized implementation in wasm and save yourself some maintenance time.
If you would like to dynamically adjust the masks, the following algorithm should be O(sqrt(N)) lines of JavaScript executed for realistic cases:
Split the image up into monochromatic regions of at most 1000-4000 pixels (you want to regions to be roundish rather than long and stringy, so use breadth first search to create them). Then keep track of a graph of these regions with edges between adjacent regions. For a 2000x2000 pixel image, the graph should contain ~4000 nodes, so finding a monochromatic component would not take an appreciable amount of time.
Updating the graph after a fill operation is straightforward - just relabel the color associated with each changed region. The only point I'm uncertain of is whether canvas operations are fast enough that each region can have its own mask and up to 4000 draws as described in the blog post don't take too long. The individual masks wouldn't be very big, and the total number of pixels to be colored isn't any different to the blog post, so it may be possible.
If something is drawn with the pen tool, then every region it touches would need to be recalculated. Assuming the pen tool is circular and not substantially larger than 1000 pixels itself, this should be a fast operation as it won't overlap too many large regions and there are few enough regions we can iterate through all of them every frame for a bounding box test.
There are cases where this goes wrong - for example if the regions end up being very stretched. If there are 1000 1-pixel wide vertical lines, and the drawing tool allows a 1000 pixel horizontal line to be drawn in 1 frame, the algorithm described looks at a million pixels (possibly 4 times each as it checks for adjacency), which might be too slow. However, since this is aimed at a touchscreen, I'd be impressed if your children can and want to draw accurately enough to cause a problem. Further optimisations could work around this problem (and other problems such as having lots of 1-pixel regions that would bloat the graph).
devit's suggestions are also worth incorporating.
Since this algorithm only becomes interesting with edits, it's not really something I could implement as a pull request to the GH repo.
1. Use pointIdx instead of a string for fill keys. That's going to be way faster and memory efficient
2. There's no need to have separate added and visited. Just keep added and continue checking it before adding to the queue, and don't delete added entries
3. Even better, don't even use added but instead just check the output image data
4. Compute pointIdx incrementally by adding or subtracting 1 or width, only do a multiplication for the first point
5. Don't keep y coordinates in the loop, instead store the minimum and maximum pointIdx and then divide at the end to find the y coordinates (you still need to keep x to compute the x minimum and maximum if you need it, unless you can make the image have a power of two stride, in which case you can just mask pointIdx to compute x)
6. Use a black border instead of doing boundary checks
7. The % 5000 check is horribly slow since division is horribly slow. Use a power-of-two size and a bitwise and to be safe
8. Doing an update every 5000 pixels seems absurdly low. CPUs do billions of operations per second and a pixel should not take more than 100 CPU cycles with proper optimization, so even at around 100 fps you should be able to do in the magnitude of 100K pixels per frame, which means you shouldn't even need to do it incrementally or pre-process. If you really need incrementality you should use both a pixel number check and a timer and adaptively double or halve the pixel number if the timer check gives a too low or high time elapsed.
9. Using "chunks of pixel" is probably faster than single pixels and using horizontal groups of chunks even better, although that requires significantly more code
10. WebAssembly, with SIMD if available, is going to be faster than JavaScript
In general, this code has clearly not been written by someone experienced in writing optimized code, so I assume the pre-processing can also be greatly optimized (if it's even necessary after optimizing the filling code).
Also, there is no need to limit to 256 areas since you can use multiple images and all channels to store larger integers.
1. You're using a slow algorithm. This is almost certainly the case, looking at how slowly it run and at the order in which pixels get painted. The Wikipedia page on flood fill is enough to find a good algorithm.
2. Possibly, the overhead of individual canvas operations is high, so setting each pixel at once is slow. If this is the case, it would be partially ameliorated by using a span-based algorithm, but you could also run the algorithm on an offscreen byte array and then blit the result to canvas.
I would bet money that a 90s state-of-the-art algorithm running in JavaScript on an offscreen array will be perceived as instantaneous on a modern computer.
The requirement is that when the user clicks on a 2k x 2k image it takes 50ms or less, running on a cheap Android tablet. If a better algorithm, perhaps implemented in wasm, can achieve this, I’d love to discard all my complex code and just use it
I do hope a PR shows up in the next few days so the internet can stop having this debate and move on with a good library.
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.
Only the first parents should have had to make it. The fact that one of these good home grown ones is not at the top of any search engine is a failure of the internet.
web directories must make a return.
See for example: https://benchmarks.slaylines.io/
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)If you’ve seen a really fast wasm solution I’d love to replace the fill portion with it though.
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...
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
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
i agree that it's easy to better its performance substantially, but i wouldn't go so far as to say 'perform terribly', except in the sense that it's far from optimal. there are applications where it would be adequate
The code allocates data structures at least eight times per pixel, and tests pixels at least four times. It will perform badly in all languages and so cannot be used as a reliable indication of JS/Canvas performance.
there might even be a case where the single-loop sort is the right thing to use, despite its abominable performance, because it's simpler than bubble sort or insertion sort; i think it's 12 amd64 instructions, 40 bytes
for (i = 1; i < n; i++)
if (a[i-1] > a[i]) t = a[i], a[i] = a[i-1], a[i-1] = t, i = 0;
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.
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%... ). Because they don't work on binary image, they might be a better way to describe what you call 'enclosed space'.
There are faster fill algorithms than the above, described on Wikipedia, that don't need you to visit the whole image [1]. In particular, span-based filling.
I don't know what OP's original code is but maybe OP was calling a Canvas API method for every pixel (super bad).
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
You can add event listeners to the SVG's paths/groups and apply fill when clicked.
You can also modify the algorithm to not jump over edges if that matters to you, sacrificing its advantage in edge cases where there are thin connections between regions.
(I know, it's a dumb idea in this case; I'm posting it as a reminder to both myself and everyone else, that many problems can be solved by checking or caching every possible state.)
I see you have drawing tools there as well, but they seem to be ignored by flood filling (e.g. if I draw a closed circular border myself and use flood-fill on the empty centre, the fill will just paint over my circle border and continue filling to the boundaries of the initial region of the original image) - so they don't even make a counterpoint I was worrying they would.
It seems that doing this per-pixel loop on the CPU in JS is slow, but it's not too bad: the first click might take 300ms, subsequent clicks are just 100ms. While this is about ten times slower than I was hoping, it's still fast enough to seem responsive to most users. This is also at 4K resolution, because I wanted a realistic worst-case. It's much faster at 1080p since it has four times less pixels to work with.
You could of course do better with WebGL.
IMO, the canvas APIs are a little too esoteric for their own good. It’s almost like a stateful object, but all the commands are executed as side effects. Isn’t front end fun?
Please have a look at my project and let me know what you think! The source code is fully annotated for another brave soul who’s working with the dark arts of high performance canvas rendering.
- Project page: https://asciify.sister.software
https://paintz.app seems to be able to do this without precomputing all of the spaces you could flood.
The method in TFA is however faster for static images, after the preprocessing.
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.
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.
http://www.adammil.net/blog/v126_A_More_Efficient_Flood_Fill...
0: https://developer.mozilla.org/en-US/docs/Web/API/OffscreenCa...
https://github.com/shaneosullivan/example-canvas-fill/commit...
Not necessarily, because same color doesn't require same palette index. If you are going to preprocess the image anyway, you can assign one palette index to each connected component.
You could simply clear the mask of a bounding box around the changes, and recalculate the masks inside that bounding box. In addition to hitting the "edge" of a drawing area, the algorithm can now also bit the edge of the bounding box and encounter an outside mask - which means the inside mask and outside mask can be ORed to get a new composite mask.
You'd have to take care with the fact that an edit can join two previously-separate areas together, but that'd also be a simple OR. The more tricky scenario is an edit splitting an existing area in two. It is reasonably easy to determine that an edit is trying to split an area, but it is not immediately obvious to me how you'd efficiently determine that no connection between two halves exists outside the edit bounding box: how do you distinguish a "|" turning into a ":" from an "O" turning into a "C"?
EDIT: Later I also made a simple LOGO interpreter in VB6 for the same reasons. Turtle fun!
No need for complex pixel manipulation stuff
This also lets you do things like let the user move things around.
But of course I imagine it would be frustrating after a few times.
Might be fun to have a fill that is actually slower, but is parallelized so you can continue to draw/fill other sections as it happens.
Sure the target for this content is developers and not specifically kids, but plenty of 10 year olds program and may be seeing these ads when trying to write their own painting program.
So no, not hypocritical. Ads are fine, just keep them away from young kids.