More info

Sunday, 2 March 2014

Computer Graphics Notes - Lab 14 SCAN LINE POLYGON FILLING ALGORITHM

Scan-line algorithm is used for filling in an area when only area boundary is specified. The basic idea of this algorithm is for each scan line that intersects area, determine interior points and set raster values. A scan-line algorithm uses the intersections between area boundaries and scan lines to identify pixels that are inside the area.

 Scan line processed one-at-a-time from first line to last line. Pixel positions along the scan line that are within the polygon definition are set to the intensity or color values specified in the application program. Taking each scan line in turn, a scan conversion algorithm locates the intersection points of the scan line with each edge of the area to be filled. Proceeding from left to right, intersections are paired, and the intervening pixels are set to the specified fill intensity or color. In the figure shown above the four intersection points with the polygon boundaries define two stretches of interior pixels.

In simpler terms, the algorithms can be explained as follows:
     Processes the raster one row, or scan line, at a time.
     Must begin each scan line at a point outside of the figure.
     As it marches along each scan line it alternates state between inside and outside the figure.
     When inside, it replaces the pixel value with the current fill color.
We represent a polygonal region in terms of a sequence of vertices V1, V2, V3, V4, V5, V6 and V7 that are connected by edges E1, E2, E3, E4, E5, E6 and E7 We assume that each vertex V1 has already been scan-converted to integer coordinates (x1- y1).

The algorithm begins with the first scan line the polygon occupies and proceeds line by line towards the last scan line. For each scan line it finds all intersection points between the current scan line and the edges. For example, scan line intersects edges E1, E7, E6 and E4 at points a, b, c and d respectively. The intersection points are sorted according to their x coordinates and grouped into pairs such as (a, b) and (c, d). A line is drawn from the first point to the second point in each pair.

Horizontal edges are ignored since the pixels that belong to them are automatically filled during scan conversion. For example, edge E5 is drawn when the corresponding scan line is processed. The two intersection points between the scan line and edges Ee and £4 are connected by a line that equals exactly E5.

Now we take a more careful look at cases when a scan line intersects a vertex. If the vertex is a local minimum or maximum such as V1 and V7 no special treatment is necessary. The two edges that join at the vertex will each yield an intersection point with the scan line. These two intersection points can be treated just like any other intersection points to produce pairs of points for the filling operation. As for vertices V5 and V6, they are simply local minimums, each with one joining edge that produces a single intersection point. On the other hand, if a scan line intersects a vertex (e.g.V4) that is joined by two monotonically increasing or decreasing edges, getting two intersection points at that vertex location would lead to incorrect results(e.g., a total of three intersection points on the scan line that intersects V4). The solution to this problem is to record only one intersection point at the vertex.



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

In order to support an efficient implementation of this scan line algorithm we create a data structure called an edge list. Each non-horizontal edge occupies one row/record. Information stored in each row includes the y coordinate of the edge's two endpoints, with ymin being the smaller value and ymax the larger value (may be decreased by 1 for reasons to be discussed below), the x coordinate of the endpoint whose y coordinate is ymin, and the inverse of the edge's slope m. the rows are sorted according to ymin. Since edges E1 and E7 both originate from the lower vertex V1 at (x1, y2 ) they appear on top of the edge list, with m1 and m7 being their slope value, respectively.
Edges in the edge list become active when the y coordinate of the current scan line matches their ymin value. Only active edges are involved in the calculation of intersection points. The first intersection point between an active edge and a scan line is always the lower endpoint of the edge, whose coordinates are already stored in the edge's record. For example, when the algorithm begins at the first scan line, edges become E1 and E7 active. They intersect the scan line at (x1, y1).

Additional intersection points between an edge and successive scan lines can be calculated incrementally. If the edge intersects the current scan line at (x, y), it intersects the next scan line at (x + 1/m, y + 1). For example, edge E7 intersects scan line y at point b, and so the next intersection point scan line y + 1 can be calculated by x = 1/m1 since y = 1. This new x value can simply be kept in the x field of the edge's record.

An edge is deactivated or may even removed from the edge list once the scan line whose y coordinate matches its ymax value has been processed, since all subsequent scan lines stay clear from it. The need that was mentioned early to give special treatment to a vertex where two monotonically increasing or decreasing edges meet is elegantly addressed by subtracting one from the ymax value of the lower edge. This means that lower edge is deactivated one line before the scan line that intersects the vertex. Thus only the upper edge produces an intersection point with the scan line (V2 in the figure). This explains why the initial ymax value for edges E1 and E4 has been decreased by one.

EXAMPLE
The coordinates of the vertices of a polygon are shown in the figure below, (a) Write the initial edge list for the polygon, (b) State which edges will be active on scan lines y = 6, 7, 8, 9 and 10.



SOLUTION

(a)    Column x contains the x coordinate of the corresponding edge's lower endpoint. Horizontal edges are not included.
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

(b)    An edge becomes active when the scan line value y equals the edge's ymin value. The 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, 9 and 10 appears as follows.
At y = 6, E2 and E8.
At y = 7, y = ymax for both edges E2 and E8 so they remain active. Also at y = 7 E4 and E6 become active.
At y = 8, E2 and E8 are removed from the edge list. E4 and E6 remain active.
At y = 9, the active edges remain the same.
At y = 10, edges E2 and E4 are removed from the edge list and the edge list becomes empty.


No comments:

Post a Comment