What is the Scan line algorithm for polygon filling
In computer graphics, a scan line algorithm is a process of filling regions of a polygon that are geometrically defined by the coordinates of vertices of this polygon graph. This algorithm is specially used for the region filling just like the boundary-fill and flood-fill algorithms. The specialty of this algorithm is that it scans lines at a time rather than scans a pixel. This property makes it faster than others.
Scan line polygon fill algorithm
step 1: Locate all intersection points of the scan line with polygon edges in the given graph.
step 2: Pair the intersection points in a series. ex. : {(7,20), (8,20}
step 3: Move up or down the scan line concerning the x-axis or y-axis and put pairs in the series. ex. : {(7,19), (8,20}, {(5,20), (4,20}, {(3,22), (2,24}
step 4: All pairs of rows in the series need to be sorted according to y_min or y_max (choose anyone).
step 5: Now, start the area filling from the sorted pairs.
Scan line algorithm polygon fill example
From the algorithm, we know that each scan line finds all intersection points between the current scan line and the edges. For the example of the scan line polygon filling algorithm, A polygonal region following a sequence of vertices V1, V2, V3, ...., V7's are connected with the following edges E1, E2, E3, ....., E7 that are drawn in the below figure. Each vertex V1 to V7 with coordinates (Xi, Yi) has been scan-converted in the integer value. So, all scanning processes in the polygon will be considered as the integer value.
- scan line y intersects edges E1, E7, E6, and E4 at points a, b, c, and d, sequentially.
- The intersection points are sorted by coordinates and arranged in pairs such as (a,b) (c,d). In each pair, a line is drawn from the first to the second point.
- The rows are sorted according to the y minimum.
- Since edges E1 and E7 both originate from the lowest vertex V1 at (x1, y1), they arrive on top of the edge list, with m1 and m7 being their slope value respectively.
Edge | ymin | ymax | X coordinate of vertex with y = ymin | 1/m |
E1 | Y1 | Y2 – 1 | X1 | 1/m1 |
E7 | Y1 | Y7 | X1 | 1/m7 |
E4 | Y5 | Y4 – 1 | X5 | 1/m4 |
E6 | Y6 | Y7 | X6 | 1/m6 |
E2 | Y2 | Y3 | X2 | 1/m2 |
E3 | Y4 | Y3 | X4 | 1/m3 |
NoteBook:
- The edge list normally is: E1->E7->E6->E4 . But, it was sorted concerning the Y minimum. That is why it is: E1->E7->E4->E6
- Y2 and Y4 have increased and decreased options. And, that is why the Y2 and Y4 have minus 1 values.
Scan line polygon fill algorithm example
Problems
The coordinates of the vertices of a polygon are shown in the below figure.
Solve the two statements from the following figure with the help of the scan line polygon fill algorithm.
1. Write the initial edge list in a table for the polygon shown in the figure.
2. Discuss which edges will be active on scan lines when the values of y are 6, 7, 8, and 9.
Solutions:
Solution for statement 1:
The axis x contains the x coordinate from the corresponding edge’s lower endpoint and y contains the corresponding minimum and maximum values of the vertices' lower and upper endpoint. It should be mentioned that, according to the scan line algorithm, the horizontal edges can not be included as they are horizontal and easy to scan. So, all horizontal edges are not included in the below table.
Edge | ymin | ymax | x | 1/m |
E2 | 4 | 7 | 9 | 0 |
E8 | 4 | 7 | 2 | 0 |
E4 | 7 | 9 | 8 | 0 |
E6 | 7 | 9 | 4 | 0 |
You are confused with the value of (1/m). The m represents the slope of each x and y coordinate value. We know that, slope (m) = y/x. So, the inverse slope (1/m) is x/y.
To understand the slope value, we are calculating the inverse slope of edge E2(1/m2)
1/m2 = 1/((y3-y2)/(x3-x2))
= (x3-x2) / (y3-y2)
= (9-9)/(7-4)
=0/3
=0
Solution for statement 2:
An edge in a polygonal graph becomes active when the scan line values equal the corresponding edge's ymin value. Again, an edge remains active until the scan line value y goes beyond the edge’s ymax value. Therefore, the active edges for y = 6, 7, 8, and 9 status as following the below.
When y = 6, the edges E2 and E8 will active
When y = 7, then y=ymax, E2, and E8 will remain active.
When y = 7, the edges E4 and E6 will be active.
When y=8, the edges E4 and E6 remain active, and E2 and E8 will be removed from the active list.
When y=9, the edges E4 and E6 will remain active.
0 মন্তব্যসমূহ