Graphics Reference
In-Depth Information
Figure 2.5.
A fill algorithm example.
Figure 2.6.
Pixel shadows.
put (2,3) and (6,3) on the stack. The loop would start over and pop (6,3). This time,
since (6,3) has already been filled, we immediately jump back to the beginning and
pop (2,3), and so on.
The problem with Smith's basic algorithm is that we look at some pixels twice, as
we saw in the case of (2,3) in the previous example. This happens because we auto-
matically put coordinates from both the line above and the line below the current one
on the stack. When we then, say, deal with the line above, the algorithm will have us
look at the current line again because it will be the line below that one. For a fast
algorithm we need to prevent this duplicate effort. Algorithm 2.4.3 from [Fish90b]
involves more bookkeeping because it differentiates between the three different types
of possible shadows shown in Figure 2.6, but it will read each pixel only slightly more
than once on the average and also has good worst-case behavior. Fishkin points out
that it is optimal if the region has no holes.
An alternative improvement to Smith's seed fill algorithm is described by Heck-
bert in [Heck90b].
Finally, another distinction that is made between flood fill algorithms is whether
we are dealing with
hard
or
soft
area flooding. The algorithms we have described so
far were hard area flooding, which basically assumed that the region to be filled was
demarcated by a “solid” boundary, that is, a curve of pixels all of the same color. Such
a boundary would be a jagged curve. To get a smoother looking boundary one typi-
cally would blur or “shade” it by assigning a gradation of colors in a neighborhood
of it. (The causes of the “jaggies” and solutions to the aliasing problem are discussed
later in Section 2.6.) If boundaries are shaded, then we would like filling algorithms
to maintain this shading. Soft area flooding refers to algorithms that do this and leave
any “shading” intact. Smith's paper [Smit79] is a good reference for both hard and
soft area flooding. The
tint fill
algorithm he describes in that paper is a soft area flood-
ing algorithm.
There are other types of pixel-based fill algorithms. Pavlidis [Pavl82] describes a
parity check type algorithm. Rogers [Roge98] describes various algorithms for filling
regions bounded by polygons that he calls “edge fill” algorithms.
