Area-Filling Algorithms

To this point we have discussed how to scan covert lines and curves. Suppose that we want to do more than just draw outline figures. We could fill the interior of objects with lines using our line drawing algorithm, or we could draw concentric circles or ellipses with increasingly smaller radii until it appeared to be solid. But this approach is wasteful.

The next class of scan conversion algorithms that we will discuss are the area-filling algorithms. These algorithms operate on a raster while completely unaware of any other primatives previously drawn.

The first algorithm, called the parity-fill algorithm, is very simple.

Processes the raster one row, or scan line, at a time.
Must begin each scan line at a point outside of the figure.
As it marches along each scan line it changes alternates state from between inside and outside the figure.
When inside it replaces the pixel value with the current fill color

The parity fill algorithm has some notable disadvantages.

It treats each figure in isolation
It only works properly for ideal primatives
Lines parallel to scanning direction must be handled as special cases
Does not work properly for self-intersecting figures.

Despite all its problems the parity fill algorithm is very popular is some applications, such as fonting and simple polygon drawing. Some reasons are

It is fast and well suited for hardware implementation
Most packages don't allow self-intersecting figures
Parallel lines don't occur very frequently, and if they are simply ignored parity-fill gives a reasonable result.
Parity fill is closely related to the boundary-equation method of rasterizing polygons to be discussed later.

A second important class of area-filling algorithms start at a point know to be inside a figure and start filling in the figure outward from the point. Using these algorithms a graphics artist may sketch the outline of a figure and then select a color or patten from a menu with which to fill it. The actual filling process begins when a point inside of the figure is slected. These routines are like the paint-can function seen in common interactive paint packages.

The first such method that we will discuss is called the boundary-fill algorithm. The boundary-fill method requires the coordinate of a starting point, a fill color, and a background color as arguments.

    public void boundaryFill(int x, int y, int fill, int boundary)
    {
        if ((x < 0) || (x >= raster.width)) return;
        if ((y < 0) || (y >= raster.height)) return;
        int current = raster.getPixel(x, y);
        if ((current != boundary) & (current != fill)) {
            raster.setPixel(fill, x, y);
            boundaryFill(x+1, y, fill, boundary);
            boundaryFill(x, y+1, fill, boundary);
            boundaryFill(x-1, y, fill, boundary);
            boundaryFill(x, y-1, fill, boundary);
        }
    }

Note: that this is a recusive routine. Each invocation of boundaryFill( ) may call itself four more times.

The logic of this routine is very simple. If we are not either on a boundary or already filled we first fill our point, and then tell our neighbors to fill themselves.

But, our intuition can be misleading. Let's watch the alogorithm in progress.

Left-button click inside one of the regions to start the fill process. I might suggest a starting with a small region. Click the right button to reset the image to its original state

What has happened here? Why is the drawing happening in the order shown? (Hint: consider the algorithm as a tree, with the current pixel as a node and neighoring pixels as ancestors).

Here's the algorithm at full speed.

Left-button click inside one of the regions to start the fill process. Click the right button to reset the image to its original state

By the way, sometimes the boundary fill algorithm doesn't work. Can you think of such a case?

Sometimes we'd like a area fill algorithm that replaces all connected pixels of a selected color with a fill color. The flood-fill algorithm does exactly that.

    public void floodFill(int x, int y, int fill, int old)
    {
        if ((x < 0) || (x >= raster.width)) return;
        if ((y < 0) || (y >= raster.height)) return;
        if (raster.getPixel(x, y) == old) {
            raster.setPixel(fill, x, y);
            floodFill(x+1, y, fill, old);
            floodFill(x, y+1, fill, old);
            floodFill(x-1, y, fill, old);
            floodFill(x, y-1, fill, old);
        }
    }

Here's the algorithm in action

Left-button click inside one of the regions to start the fill process. Click the right button to reset the image to its original state

It's a little awkward to kick off a flood fill algorithm, because it requires that the old color must be read before it is invoked. The follow implementation overcomes this limitation, and it is also somewhat faster, albeit longer.

    public void fillFast(int x, int y, int fill)
    {
        if ((x < 0) || (x >= raster.width)) return;
        if ((y < 0) || (y >= raster.height)) return;
        int old = raster.getPixel(x, y);
        if (old == fill) return;
        raster.setPixel(fill, x, y);
        fillEast(x+1, y, fill, old);
        fillSouth(x, y+1, fill, old);
        fillWest(x-1, y, fill, old);
        fillNorth(x, y-1, fill, old);
    }

    private void fillEast(int x, int y, int fill, int old)
    {
        if (x >= raster.width) return;
        if (raster.getPixel(x, y) == old) {
            raster.setPixel(fill, x, y);
            fillEast(x+1, y, fill, old);
            fillSouth(x, y+1, fill, old);
            fillNorth(x, y-1, fill, old);
        }
    }

    private void fillSouth(int x, int y, int fill, int old)
    {
        if (y >= raster.height) return;
        if (raster.getPixel(x, y) == old) {
            raster.setPixel(fill, x, y);
            fillEast(x+1, y, fill, old);
            fillSouth(x, y+1, fill, old);
            fillWest(x-1, y, fill, old);
        }
    }

    private void fillWest(int x, int y, int fill, int old)
    {
        if (x < 0) return;
        if (raster.getPixel(x, y) == old) {
            raster.setPixel(fill, x, y);
            fillSouth(x, y+1, fill, old);
            fillWest(x-1, y, fill, old);
            fillNorth(x, y-1, fill, old);
        }
    }

    private void fillNorth(int x, int y, int fill, int old)
    {
        if (y < 0) return;
        if (raster.getPixel(x, y) == old) {
            raster.setPixel(fill, x, y);
            fillEast(x+1, y, fill, old);
            fillWest(x-1, y, fill, old);
            fillNorth(x, y-1, fill, old);
        }
    }

And here is the working algorithm.

Left-button click inside one of the regions to start the fill process. Click the right button to reset the image to its original state

A final consideration when writing a area-fill algorithm is the size and connectivity of the neighborhood, around a given pixel.

The eight-connected neighborhood is able to get into knooks and crannies that an algorithm based on a four-connected neighborhood cannot.

Here's the code for an eight-connected flood fill.

    public void floodFill8(int x, int y, int fill, int old)
    {
        if ((x < 0) || (x >= raster.width)) return;
        if ((y < 0) || (y >= raster.height)) return;
        if (raster.getPixel(x, y) == old) {
            raster.setPixel(fill, x, y);
            floodFill8(x+1, y, fill, old);
            floodFill8(x, y+1, fill, old);
            floodFill8(x-1, y, fill, old);
            floodFill8(x, y-1, fill, old);
            floodFill8(x+1, y+1, fill, old);
            floodFill8(x-1, y+1, fill, old);
            floodFill8(x-1, y-1, fill, old);
            floodFill8(x+1, y-1, fill, old);
        }
    }

Sometimes the eight-connected algorithm gives you exactly what you want. In the following example try a 8-way connected flood-fill of the antelope.

Left-button click inside one of the regions to start the fill process. Click the right button to reset the image to its original state

At other times the eight-connected algorithm really messes up. Try clicking on various parts of the circle below. Because of this, the four-neighborhood algorithm is used far more often.

Left-button click inside one of the regions to start the fill process. Click the right button to reset the image to its original state

This page last updated Wednesday, September 25, 1996