9
Maroti
10d

Couldn't find any satisfactory explanation online, so here is a question. Discussions idea etc are welcome.

How is the colour fill tool implemented in paint or other software?

I remember it running superfast on old 98 machines. Got me curious to think how they achieved it.

(correct me if I am wrong, recursion won't be a good idea for large images.)

Comments
  • 6
    It's a basic flood fill, and it is recursive in 4 directions (specifically, in paint, it uses a stack)

    It's fast because it's a simple algorithm.

    https://en.wikipedia.org/wiki/...
  • 0
    @oudalally thanks!
    will need to write and test out flood fill on larger images then, cause I always thought recursion on some 1000x1000 pixels would take some noticeable time at least.
  • 2
    @Maroti Recursion in itself isn't actually slow, but it's very easy to get wrong.

    When you're just checking a pixel value, it's pretty quick as essentially you're just moving through a matrix of pixels to see if the next one you're targeting is the same colour as your starting colour.

    I've used recursion on a convolution kernel before now for edge detecting, and it was really quite surprisingly fast.

    The thing to keep in mind is that as with RegEx, the vast majority of occasions when people use recursion, it's just not necessary.

    Recursive algorithms are a very precise tool to wield, and when used properly are quite incredible, but when used badly, they are a nightmare to debug and can become difficult to control effectively.
  • 1
    @Maroti Think of it this way.

    You click on a pixel, and that pixel is your marker colour which will be filled. You store its original colour, and then change it to the new colour.

    From that pixel, you look for every pixel surrounding it, pick one, and recursively run the algorithm again. It looks for all the pixels around it, but the one you first clicked is already the new target colour, so it ignores it.

    This keeps on going, until you find a pixel which is not the marker colour. From that point, the recursion returns until you end up back to your starting pixel.

    The next pixel surrounding it is chosen, and it all goes on from there.

    The time limiting factor is how big the area to fill is, and how you handle the fill operation itself. If you fill lines for example, that speeds things up.

    Recursion is just the mechanism the process is applied by.
  • 0
    @oudalally yes, I get the process totally, but wouldn't the overhead on larger images be great too when running on single thread? So if my operation is a simple one I can get away with a larger recursion depth. Now the question is, is that enough for large images?
  • 0
    @Maroti Not really, it will have a big overhead but that's largely irrelevant with modern CPUs.

    If you write the algorithm in C, even on a single thread it's really SERIOUSLY fast.

    Even in C#, it's still quick.
  • 0
    @Maroti @oudalally
    Rendering line by line would still probably be faster though, if a bit more annoying to implement.
    Unless I've got it totally wrong, you basically go across the image in a line and fill in the pixels that are in the interior of your shape.
    The problem with the recursive flood fill is that it's very cache unfriendly assuming that you've stored your image as a straightforward matrix. You have to access pixels in adjacent columns or rows, and that's terrible if you have a decent sized image that's stored row or column wise. Here Z-ordering (Morton coding) can help you by decreasing the locality penalty somewhat.
  • 3
    @RememberMe It would depend a lot on where in the image you clicked the point to fill from, and hope far in each direction the boundary is.

    If you have a circle and place the start point dead centre, there will be an equal spread in each direction so the cache hit would be lessened.

    If instead of a single point spreading, a line is drawn in each direction (up/down, or left/right) from that point, and then adjacent points are treated the same way, that would improve performance which is essentially how the MSPaint version works (run it on a 16 mhz 386 in Win3.0 and you'll see it in action), but there's still ar recursive element.

    In each recursion, the line is drawn vertically until a different colour pixel is found, then extended in the opposite direction (again vertically) to the boundary.

    This function is then called on adjacent points via recursion effectively creating a stack of line drawing operations.
  • 0
    Something to keep in mind is that in the MSPaint version, really large images never came up.

    Avoiding recursion is generally the safest option, and with large images, will likely be the only real way to implement flood fill without overflowing the stack, however in terms of performance, it will be slightly slower as all possible paths for filling will need to be evaluated before they are filled.
  • 0
    @oudalally oh whoops I was thinking of a different flood fill, one that immediately recurses on all non-filled neighbors.
  • 1
    @RememberMe Its a weird one to balance out, as an entirely recursive option would be the fastest if all neighbours in 8 directions are examined simultaneously in 8 threads, but it's really wasteful.

    Using lines in a none recursive loop and testing a match above or below (or left and right) could work well.

    If you start from a point, draw a line say horizontally until you read a different colour in either direction, then check if above or below that line has a matching colour - each time you draw a pixel on the line, check if the line above has a suitable colour, and if so, stop checking on subsequent pixels.

    I you know another line is going to be drawn, draw from the pixel you matched.

    Eventually, no lines will have candidate colours above or below, and the fill is completed.

    It wouldn't be recursive as you store the point of the next pixel to examine outside the loop, and when it's got a null value, there's nothing left to fill.
Your Job Suck?
Get a Better Job
Add Comment