Page 103 - DCAP313_LAB_ON_COMPUTER_GRAPHICS

Unit 6: Implementing Polygon Filling Algorithm

The edge list for such a polygon, for each of the scan-lines from 3 to 11 is: Notes

Table 6.2: Edge List

Scan-line Edge number
11 –
10 –
9 –
8 –
7 2, 10
6 –
5 –
4 –
3 3, 5, 7, 9

Note that in the Table 6.2 the horizontal lines are not added to the edge list. The active edges
for scan-line 3 would be 3, 5, 7, 9; these are sorted in order of their x values, in this case 9, 7, 5,
3. The polygon fill routine would proceed to fill the intersections between (3, 3) (E9) and (6, 3)
(E7) and (10, 3) (E5) to (15, 3) (E3). The next scan-line (4) is calculated in the same manner. In
this the values of x do not change (since the line is vertical; it is incremented by 0). The active
edge at scan-line 7 is 10 and 2 (correct order).
The sorting of the edges is not explicitly necessary: for each scan line position you could try to
intersect it with all polygon edges which are not that effective. The sorting allows us to easily
keep a list of active edges:

If the scan line moves over the endpoint of an edge with the smaller y-coordinate it is added
to the list; if the scan line moves over the endpoint of an edge with the bigger y-coordinate it
is deleted from the list.
6.1.1 Basic Scan-fill Algorithm

1. For each non-horizontal edge of the polygon boundary recognizes the upper and lower
endpoints, (x l , y l ) and (x u , y u ), such that y u > y l , and creates a record for each that contains
• Y u , the y-coordinate at the upper endpoint.
• x = x l , the current x-intersection.
• w = 1/m = (x u – x l )/ (y u – y l ), the reciprocal of the slope of the edge.

2. Set the AET (the active edge table) to be empty.
3. Apply a bucket sort algorithm to sort the edges using the y l as the primary key, and x l as
the secondary, and w as the tertiary. N.B., Each bucket contains a list. The set of buckets
is called the ET (edge table):
4. Set y equal to the smallest index in the ET that has a non empty bucket.

5. Repeat until the ET and the AET are empty:
• Move any edges from bucket y in the ET to the AET.

• Remove any edges from the AET that have a y u equal to y.
• Sort the AET according to x.

LOVELY PROFESSIONAL UNIVERSITY 97