Page 101 - DCAP313_LAB_ON_COMPUTER_GRAPHICS

Unit 6: Implementing Polygon Filling Algorithm

6.1 Scan-line Fill Algorithm Notes

The scan line fill algorithm is an inventive way of satisfying in irregular polygons. The algorithm
begins with a place of points. Each point is associated to the next, and the line between them is
considered to be an edge of the polygon. The points of each edge are attuned to make sure that
the point with the smaller y value appears first. Next, a data structure is created that contains
a list of edges that begin on each scan line of the image. The program progresses from the first
scan line upward. For each line, any pixels that contain an intersection between this scan line
and an edge of the polygon are filled in. Then, the algorithm progresses along the scan line,
turning on when it reaches a polygon pixel and turning off when it reaches another one, all the
way across the scan line.
There are two special cases that are solved by this algorithm. First, a problem may happen 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” colouring of the scan line 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 colouring will turn on and then immediately off, resulting in “backwards” colouring
for the rest of the scan line. 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.
For example see Figure 6.1

Figure 6.1: Horizontal Scanning of the Polygon

The sequence of edges sorted by their smallest y-coordinate (assume the y-axis goes from top
to bottom) would be 1234567. The edges intersected by the scan line (the so-called active edges)
are 3654. Calculating these four intersections and sorting them by their x-coordinates give two
line segments 3-6 and 5-4 which can easily be drawn. Afterwards the scan line would be shifted
down one pixel etc.
For each horizontal scan-line:
1. List all the points that intersect with the horizontal scan-line

2. Sort the intersection points in ascending order of the x coordinate
3. Fill in all the interior pixels between pairs of successive intersections

LOVELY PROFESSIONAL UNIVERSITY 95