10 ms·

Instant flood fill with HTML Canvas

• zachrip 3y ago
  This works well for the problem space - does it work well for a drawing app where the canvas is always changing?
  • rattray 3y ago
    Interesting – what behavior would you want there? Statically filled area, or a shifting area depending on the other pixels?
    • RandallBrown 3y ago
      For an app like this I would expect it to be static. Basically the same behavior MS Paint has had for decades.
  • shaneos 3y ago
    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 3y ago
    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.
  • crote 3y ago
    Modifying it to work with a changing canvas shouldn't be too difficult. 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"?
• RandallBrown 3y ago
  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.
• ianlevesque 3y ago
  Ha, painting tablet app feels like a rite of passage for programmer parents. Here's mine from that era https://paints.netlify.app/ 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.
  • sharikous 3y ago
    Wonderful, the fact that it runs as expected in multi touch devices has not gone unnoticed!
    • ianlevesque 3y ago
      That’s really essential, even if only for the clumsy thumb left on the screen with a naive grip. Being able to finger paint with all ten fingers is a bonus.
      • shaneos 3y ago
        Yes, ignoring the palm resting on the screen is essential. Doing that along with allowing zooming and pen input takes some creative thinking. It’s non trivial
  • shaneos 3y ago
    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!
    • arp242 3y ago
      Your kids sound high maintenance; I would consider returning them if they're still within the warranty period.
      • 3y ago
• 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 ago
    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
• TazeTSchnitzel 3y ago
  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 3y ago
    The speed is achieved by using 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 this would, I think, be slower as perceived by the user
    • TeMPOraL 3y ago
      Makes me wonder if this could be even faster, if you cheated and just generated copies of the masks already colored, for every color available. From looking at the video, I see you have 10-11 colors available at any given moment with possibility of changing them to, presumably, arbitrary RGB value. That means you only need to keep 11 color variants of each mask, which should still fit in RAM. You also need to be able to replace a single group of masks with a new set of masks faster than the user can switch colors in the custom color picker. (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.)
      • shaneos 3y ago
        The user can select from thousands of colours unfortunately :-) Tap the top left icon in the app, or just play with it for fun! https://kidzfun.art https://kidzfun.art
        • TeMPOraL 3y ago
          Sure, but at any given moment, they can use only ~12 of them (+ the rainbow thing, now that I played a bit and know how it works). Meaning, you can keep 12 pre-filled variants of each mask, one for each color on the main palette, and recolor all masks of a given color when the user picks a new one from the top-left color picker. I bet you can do this update faster than they can dismiss the color picker and tap on the canvas. 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.
• chrisweekly 3y ago
  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.
• Waterluvian 3y ago
  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.
  • rikroots 3y ago
    It's not just the Canvas API that surprises, it's also how browser JS engines choose to implement those APIs. What works well in Chrome can often cause grief in Firefox or Safari. Working with canvas elements today often feels like frontend development back in the 2000s See for example: https://benchmarks.slaylines.io/ https://benchmarks.slaylines.io/
• ninepoints 3y ago
  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.).
  • ghusbands 3y ago
    Jump-flooding is inexact and can jump over significant edges. The runtimes claimed are also incorrect - as it sets every pixel, it is O(N^2) in the image dimensions, just like flood-filling. If you're working with an image and setting pixels, you cannot avoid being O(N^2) in the dimensions of the filled area.
    • account42 3y ago
      Jump-flooding is an algorithm suited for GPUs where you run operations for all pixels "simultaneously" which is why the complexity is often given in number of iterations and not number of operations. Naive flood fill fits this model badly and a GPU implementation would have a complexity of O(N^3) as you expand your fill region border by only one pixel width each iteration so you will need O(N) iterations for sufficiently large regions but you need to look at ALL pixels every time. You could force a CPU-like computation where you keep a stack of visited pixels to expand out from but that would actually end up slower for all reasonable sizes on the GPU unless your regions are much smaller than the image. 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.
• shaneos 3y ago
  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 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.
  • masswerk 3y ago
    I wonder, if assembling an array of paths for outlines may improve things. You can check for a point being in inside path, use paths as hit areas, and you can apply fills. Notably, there wouldn't be any need for keeping various mask images in memory anymore. (You wouldn't want any curves in this paths, just pixel outlines. It may become a bit tricky with complex paths and negative shapes, though, which may be addressed by composing a mask image on-the-fly.)
    • kragen 3y ago
      these are interesting ideas! 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)
  • KRAKRISMOTT 3y ago
    Look up the connected regions algorithm (DFS), it might be useful. Here's an example https://en.m.wikipedia.org/wiki/Connected-component_labeling https://en.m.wikipedia.org/wiki/Connected-component_labeling https://scikit-image.org/docs/stable/api/skimage.measure.html#skimage.measure.label 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.
  • sb8244 3y ago
    Sorta random question, but what do you use to generate your diagrams? Mine always look so boring in comparison.
• joeldo 3y ago
  For vector style graphics (like in the article) - You can achieve this quite simply on the web with SVG DOM. You can add event listeners to the SVG's paths/groups and apply fill when clicked.
  • yuchi 3y ago
    Even better, you can just use a single listener and on click verify the element under the cursor with document.elementFromPoint
• gatkinso 3y ago
  I liked the slow version. more fun.
  • NeoTar 3y ago
    I came into the comments to say the same - the slow version is rather charming like the paint software of the eighties/nineties. But of course I imagine it would be frustrating after a few times.
  • feintruled 3y ago
    Yes, it seemed more appropriate for a kids painting app, like the paint is being 'poured' into the shape. It's probably only cool for the first couple of fills, mind you, after that it might start to get in the way. 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.
• Camillo 3y ago
  You could do instant flood-fill on a slow PC in the early 90s. There is no need to precompute this. The possible issues are: 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.
  • buescher 3y ago
    There are fast segment based fill algorithms from the seventies or very early eighties in the literature and reprinted in the first volume of Graphics Gems. They work very well and do not require the call stack or amount of computation of simpler methods.
  • stkdump 3y ago
    Note that you loose 1-2 orders of magnitude just by the screen resolution (in the early nineties we used 640x480, sometimes even 320x200 vs 4K nowadays). Another order of magnitude is lost by using a more high level programming language, which sure you could probably optimize down to factor 2-3. Plus sublinear scaling of stuff like memory latency since the 90s. All in all I agree we should be able to do better, but it is by no means trivial.
  • shaneos 3y ago
    If you are right that would be amazing! The demo code is open source, please send a PR with such a flood fill implemented. 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
    • irskep 3y ago
• eyelidlessness 3y ago
  Apart from algorithm commentary by folks who are certainly wiser than me on the topic: since you’re already using a worker, you would probably benefit from using OffscreenCanvas[0], which is transferrable to worker threads and otherwise should be optimized for heavier computations. 0: https://developer.mozilla.org/en-US/docs/Web/API/OffscreenCanvas https://developer.mozilla.org/en-US/docs/Web/API/OffscreenCa...
  • shaneos 3y ago
    Thanks for the suggestion. I did indeed achieve a significant speed up with OffscreenCanvas, see the commit below. It lets me avoid the slowest part of my original solution, the call to context.putImageData() https://github.com/shaneosullivan/example-canvas-fill/commit/4197243080ff4fb49b67854e68566c902ff29b0a https://github.com/shaneosullivan/example-canvas-fill/commit...
• robomartin 3y ago
  I've played with and implemented a range of area fill algorithms in the past. Optimized span-filling (dating back to the 1990's) works very well, is fast, buffer friendly and delivers great results. Subtleties surface when you have to consider filling around dithered edges and partially transparent elements. Fur stuff. https://en.wikipedia.org/wiki/Flood_fill https://en.wikipedia.org/wiki/Flood_fill
• TeffenEllis 3y ago
  This is very clever! I found out about the canvas composite modes far too late in an animated ASCII art project. 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://asciify.sister.software - Demo: https://asciify.sister.software/demo/3d/ https://asciify.sister.software/demo/3d/
  • jvdvegt 3y ago
    The demo page is blank for me? (Firefox on Ubuntu, on a AMD laptop).
• stkdump 3y ago
  In the past we had indexed color screen modes. You could draw all pixels to the screen once and give each pixel an index into a color palette. When you would start, they would all be mapped to white, but as you start with coloring, you would then just change the color of the palette entry (truly a O(1) operation) and your graphics card would then do the work at scan time. I guess the closest equivalent nowadays would be to do this inside the pixel shader.
  • danbruc 3y ago
    This is however not the same operation, changing the palette will affect all pixel of that color, flood fill affects only all the pixels in the connected component you clicked on.
    • stkdump 3y ago
      > changing the palette will affect all pixel of that color 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.
• andersrs 3y ago
  > The idea was to build something fun that never shows adverts to them or tricks them into sneaky purchases by “accident”. 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/ https://memorycardsgame.com/. Then browsing a svelte forum I found https://toddler-games.com 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.
  • gsliepen 3y ago
    I can also recommend https://tuxpaint.org/ https://tuxpaint.org/. I see they also have an app for Android nowadays, but no iOS it seems.
  • jmkni 3y ago
    Not sure I would take parenting advice from Steve Jobs!
  • tony_antny 3y ago
    I was looking for colouring app two days ago but couldn't find a decent one. https://toddler-games.com https://toddler-games.com seems to be something my niece's would love. Thanks.
  • shaneos 3y ago
    Thanks - that toddler-games.com is really nice. It’s so simply done that even a two year old could enjoy it for hours. My kids are 5 and 7 now so want something a bit more advanced, but I wish I’d found that a few years ago
  • taskforcegemini 3y ago
    you made the game for Steve Jobs kid?
• primitivesuave 3y ago
  This is a very neat implementation and explanation of a disjoint set algorithm: https://en.wikipedia.org/wiki/Disjoint-set_data_structure https://en.wikipedia.org/wiki/Disjoint-set_data_structure
  • deleted 3y ago
    [deleted]
• shaan7 3y ago
  Oh man this brings back memories. When I was young we did not have Internet at home, so I made a VB6 app for my sister so she could load outlines and color them. So much fun! For both of us :D EDIT: Later I also made a simple LOGO interpreter in VB6 for the same reasons. Turtle fun!
• dmje 3y ago
  [flagged]
• DaveSapien 3y ago
  This has convinced me to add prepossessed fill areas on my kids colouring book for iOS. (no IAP, subscription, no ads, etc, like the general sentiment here) Been thinking about this for a while, but things are fast enough on an iPad that it took a back seat, nice to be inspired to go that extra mile :)
• PretzelPirate 3y ago
  It seems hypocritical to make an app that won't show ads and talk about it's implementation on a site full of ads (I see 5 on the page). 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.
  • shaneos 3y ago
    Wordpress' free tier sucks alright. However, I have nothing against ads per se, just ads shown to children. Maybe I'll start giving Wordpress money after all these years of them hosting my blog..... So no, not hypocritical. Ads are fine, just keep them away from young kids.
  • shaneos 3y ago
    Sigh, ok I've given Wordpress money. No more ads for your delicate eyes. You're welcome for the all the free code, write up, diagrams and fun app for kids by the way. I hope they bring a bit more positivity into your life so you can spread it elsewhere on the internet.
• danbruc 3y ago
  I tried the usual route using getImageData() and am getting between 50 ms for a small region and 100 ms for the full 2048 x 2048 canvas on a 8th generation mobile i5 in Chrome. In Firefox it is 50 ms and 150 ms, all on Windows 10. So the overhead alone of getting the image data from the canvas and writing it back can eat up most of the entire 50 ms budget if not exceed it. Or maybe I did it not in the proper way, I am totally not a web developer. There is also certainly some room for improvement in my implementation of the core algorithm. But unless there are more tricks than specifying willReadFrequently, it seem hard to get below 50 ms.
  • shaneos 3y ago
    Yeah it's not easy. I'm going to look into using OffscreenCanvas to see if I can wring a bit more performance out of this
• rep_movsd 3y ago
  A better way to do it would be to maintain canvas Path2d objects to define the enclosed regions, which can be instantly filled with context.fill() No need for complex pixel manipulation stuff This also lets you do things like let the user move things around.