Raster Algorithms - Computer Graphics and Geometric Modeling - page 28

procedure BFA ( integer x, y)
if Inside (x,y) then
begin
Set (x,y);
BFA (x,y - 1); BFA (x,y + 1);
BFA (x - 1,y); BFA (x + 1,y);
end;

Algorithm 2.4.1. The basic fill algorithm.

ferent from the color inside the region, where the boundary of a set S means here the
set of points of S c that are adjacent to S.
In the algorithms of this section, the Boolean-valued function Inside (x,y) deter-
mines whether or not the pixel at (x,y) has the property one wants. The procedure
Set (x,y) sets the value of the pixel at (x,y) to its desired value. For example, to get a
flood fill algorithm let Inside (x,y) be true if the value of the pixel at (x,y) agrees with
the value of the pixels in the region and let Set (x,y) set the pixel value to its new
value (the same as Draw (x,y,c¢)). Using the functions Inside and Set will make our
algorithms more general and applicable to a variety of fill algorithms. There is one
constraint on the Inside function however: Inside (x,y) must return false after an
operation Set (x,y).
Assume 4-adjacency is chosen and that our regions are 4-connected. The BFA pro-
cedure in Algorithm 2.4.1 shows that the basic idea behind a fill algorithm is very
simple. Notice that 4-connected is important and that the algorithm will not work if
the region is not 4-connected.
Although the BFA algorithm is simple, the recursion is expensive. One of the earli-
est nonrecursive algorithms is due to Smith ([Smit79]). It is not very efficient because
pixels are visited twice, but many of the better algorithms are based on it. It will be
worthwhile to describe Smith's algorithm, Algorithm 2.4.2, first before we present the
one due to [Fish90b]. In this algorithm and the next, the constants XMIN, XMAX,
YMIN, and YMAX define the minimum and maximum values for the x- and y-
coordinates of pixels in the viewport. The procedures Push and Pop push and pop a pair
(x,y) onto and from a stack, respectively. The function StackNotEmpty tests whether
this stack is empty or not. The procedures Inside and Set are as described above.
For example, suppose that in Figure 2.5 our starting point is (7,3). After the first
FillRight command the two-pixel segment from (7,3) to (8,3) would have been filled.
The FillLeft command would fill (6,3). The ScanHi command would place the pixel
coordinates (6,4) and (8,4) on the stack in that order. The ScanLo command would
add (6,2). The segments of the region that (6,4), (8,4), and (6,2) belong to are usually
called “shadows.” The point of the ScanHi and ScanLo procedures is to find these
shadows that still need to be filled. We now return to the beginning of the main while
loop, pop (6,2), and make that our new starting point. The next FillRight and
FillLeft would fill the segment from (2,2) to (8,2). The ScanHi and ScanLo would