Flood Fill Algorithms with Variations

 

This section presents algorithms and demos for high performance flood fill or seed fill applications. Included are methods for variant methods such as flood under, re-bordering and pixel swapping.

The code for the demos and applications themselves are not portable, because they consist of a hybrid mix of Borland C++ Builder, Intel '86 assembler language and non-standard Windows bitmaps. The methods, however, are applicable to any computer graphics environment.

Efficient Algorithms with New Features

 

Here is a paper which describes an efficient and versatile flood fill method which supports advanced fill options. The paper discloses a method which only visits each processed pixel once, and can therefore support the transfer of arbitrary pixels into the filled regions. Algorithms are presented in pseudo-code and a complete implementation of the lowest level scan and fill routines in Intel assembler language are demonstrated. The paragraphs below show some of the capabilities of the method.

Flood Under

 

This variation of a conventional flood fill routine, supports the ability to ignore a chosen color. When the fill routine begins, it terminates at a chosen border color or any color other than that of the starting pixrl .depending on the method selected. However, flood-under allows the user to choose another color which is ignored during the fill and is effectively skipped over. An example is shown below.

 

 

      Basic starting screen      

 

                

                   Standard Flood Fill                                       Flood Fill with Flood Under           

 

Given the starting screen shown above, and filling the black background with blue, how does your flood fill algorithm perform? Chances are, it produces a screen like the standard flood fill image above. This is the result of invoking a conventional surface fill algorithm such as the one in the Windows API. The third image above is the result of invoking a flood fill with flood under capability. Flood under is just one of the new features of a flood fill library I have created to manage extended special fill requirements. This particular feature is most useful when an image has been partially covered with text and it is necessary to fill the background including the closed regions within the text characters. The flood under feature allows the caller to specify one color to ignore during the fill. This color is neither filled nor treated as a boundary, so the algorithm will treat any other color (other than the original surface color or the flood under color) as a boundary. The effect is to 'elevate' the text or other graphics object to the foreground and fill underneath it.

 

Re-Border

 

      

   Starting Screen                                       Flood fill with re-border

The above images show the effects of invoking flood fill with the reborder option. This option allows the caller to specify a particular color to re-color any border pixel. In this case we have flood filled the black background surface with blue, and re-colored the border pixels with red. This can be useful for forming outlines of text or graphics.

Fill from Bitmap and Gradient Fill

Another available option for filling a surface is to copy pixels from a second bitmap pixel-for-pixel into the region to be filled. The image below fills the region enclosed by the elliptical frame with pixels from a bitmap of the image processing standard picture of "Lena". The flood-under option was also used so that the text appears normal. To create this image, white text was written over a blue background, then a yellow ellipse was drawn over it. Then the fill algorithm was invoked with the fill-from-bitmap and flood-under options for the interior of the region and called again with a gradient fill option for the external region. Gradient fills are available to fill with colors from a table indexed by the 'y' coordinate (as in this example) or the 'x' coordinate.

      

   Fill from Bitmap with Flood-Under            Same Image with Gradient Fill Added