How does the fill operation work in paint applications?

Question

All paint programs, independent of how simple or complex they are, come with a fill tool. This basically replaces the color of a closed region with another color. I know that there are different APIs to do this, but I am interested in the algorithm. What would be an efficient algorithm to implement this tool?

A couple of things I can think of quickly are:

1. Convert image into a binary map, where pixels in the color to be replaced are 1 and all other colors are 0.
2. Find a closed region around the point you want to change such that all the pixels inside are 1 and all the neighbouring pixels are 0.

Sample Image

Answer 1

Many implementations are done as a recursive conquer and divide algorithm. If you do a quick google for "flood fill algorithm" you will find plenty of resources including the excellent wikipedia page on the topic.

Answer 2

If you want a time efficient algorithm that doesn't care very about memory efficiency, you can do it by:

1) keeping a boolean memory of which cells you have already visited: Vis[]

2) keeping a list of points you have already visited but have not yet marked the neighbours for: Busy[]

3) start both of those as empty

4) add your start point to Busy

5)

while you have a point P in Busy:
{
    for each neighbour N of the point P for which Vis[N] is still false
    {
       if appropriate (not crossing the boundary of the fill region)
       {
           set Vis[N] to true
           update the colour of N in the bitmap
           add N to the end of Busy[]
       }
       remove P from Busy[]
    }
}

Answer 3

The Flood Fill algorithm is what's most commonly used. The following is a naive version of it straight out of my old university textbook, "Computer Graphics with OpenGL" by Hearn Baker, 3rd ed:

void floodFill4 (int x, int y, int fillColor, int interiorColor)
{
  int color;

  /* Set current color to fillColor, then perform the following operations */
  getPixel(x, y, color);
  if (color == interiorColor) 
  {
    setPixel(x,y);  // Set color of pixel to fillColor.
    floodFill4(x + 1, y, fillColor, interiorColor);
    floodFill4(x - 1, y, fillColor, interiorColor);
    floodFill4(x, y + 1, fillColor, interiorColor);
    floodFill4(x, y - 1, fillColor, interiorColor);
  }
}

For large images, however, the above will probably give you a stack-overflow error due to recursing for every pixel. Often, this algorithm is modified so that it uses iteration when filling a row of pixels, then recursively fills the rows above and below. As @kasperjj stated, wikipedia has a good article about this.

Answer 4

These kinds of algorithms are discussed in detail in Computer Graphics: Principles and Practice. I highly recommend this book if you're interested in understanding how to rasterize lines, fill polygons, writing 3d code without the benefit of using DirectX or OpenGL APIs. Of course, for real world applications, you'll probably want to use existing libraries, but if you're curious about how these libraries work, this is an awesome read.

Answer 5

Also read about connected component labelling. This is an efficent way to find connected pixels whilst only visiting every pixel twice.

Wikipedia article.

The advantage to this is that the pixel values don't have to necessarily be the same or the function that describes pixels as connected could be something other than raw value - gradient perhaps.

Answer 6

General idea is described as Flood Fill Algorithm and there are various modifications to it. A common one is scanline fill. See the related question How Scanline based 2d rendering engines works?