4 ms·

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://gith

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.
- shaneos 3y ago
  https://excalidraw.com https://excalidraw.com !! Such an amazing app, free and open source
penteract 3y ago
Assuming you currently recompute the whole thing on every edit, it might be fairly straightforward to speed it up by reusing the results of the previous run. Areas which do not overlap the edited area shouldn't need to be recalculated. Bounding boxes would be a quick way to test overlap.
- penteract 3y ago
  Having checked the website https://kidzfun.art https://kidzfun.art, it looks like you compute the masks once, and don't recalculate anything upon edits. 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.
devit 3y ago
The fill algorithm is far from being properly optimized: 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.
- shaneos 3y ago
  Thanks for the great write up - pull requests are welcome.

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.

shaneos 3y ago
https://excalidraw.com https://excalidraw.com !! Such an amazing app, free and open source

penteract 3y ago

Assuming you currently recompute the whole thing on every edit, it might be fairly straightforward to speed it up by reusing the results of the previous run. Areas which do not overlap the edited area shouldn't need to be recalculated. Bounding boxes would be a quick way to test overlap.

penteract 3y ago
Having checked the website https://kidzfun.art https://kidzfun.art, it looks like you compute the masks once, and don't recalculate anything upon edits. 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.

devit 3y ago

The fill algorithm is far from being properly optimized: 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.

shaneos 3y ago
Thanks for the great write up - pull requests are welcome.