The scanline fill algorithm is an ingenious way of filling in irregular
polygons. The algorithm begins with a set of points. Each point is
conected to the next, and the line between them is considered to be an
edge of the polygon. The points of each edge are adjusted to ensure that
the point wih the smaller y value appears first. Next, a data structure
is created that contains a list of edges that begin on each scanline of
the image. The program progresses from the first scanline upward. For
each line, any pixels that contain an intersection between this scanline
and an edge of the polygon are filled in. Then, the algorithm progresses
along the scanline, turning on when it reaches a polygon pixel and
turning off when it reaches another one, all the way across the scanline.
There are two special cases that are solved by this algorithm.
First, a problem may arise if the polygon contains edges that are
partially or completely out of the image. The algorithm solves this
problem by moving pixel values that are outside the image to the
boundaries of the image. This method is preferable to eliminating the
pixel completely, because its deletion could result in a "backwards"
coloring of the scanline i.e. pixels that should be on are off and vice
versa.
The second case has to do with the concavity of the polygon. If the
polygon has a concave portion, the algorithm will work correctly. The
pixel on which the two edges meet will be marked twice, so that it is
turned off and then on. If, however, the polygon is convex at the
intersection of two edges, the coloring will turn on and then
immediately off, resulting in "backwards" coloring for the rest of the
scanline. The problem is solved by using the vertical location of the
next point in the polygon to determine the concavity of the current
portion. Overall, the algorithm is very robust. It turns out that
the only difficulty comes with polygons that have large amounts of edges,
like circles and ellipses. Filling in such a polygon would be very
costly. Luckily, there is a better way to fill circles and ellipses.
Below is an image of a polygon filled in with scanfill.
Circles and ellipses are considerably easier to fill than other
polygons. These figures are also filled as they are drawn. A pair of
boundary pixels sits on each scanline. Simply fill in the pixels
between each pair. Since both of these shapes are typically drawn in
one quadrant and then reflected around the center point, the space
between the pair can be drawn as soon as the two pixels are filled in.
Below is an example of an image drawn with the circle adn elipse fills.
A funcion called PolyLine was added ot the graphics environment to
simplify the creation of polygons. This function takes in a set of
points and draws lines betwen consecutive pairs. This function does not
assume that he figureis a closed polygon. If the user wants to create
a closed polygon, they must reenter the first point at the end of the
list. Below is an image of some lines and polygons created with
PolyLine.
The first required image is a scene containing a box on top of a
table. This image builds from teh one constructed in the last lab.
It incorporates the scanline fill function so that all of the
surfaces that were previously open are now filled. The bitmap fill
extension is demonstrated in this image, as the fill patterns for the
floor and wall.
The second required image is an oddly shaped polygon. This polygon
exhibits a variety of possible situations in which the fill program
may have difficulties.
