Scanline 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 scanline algorithm uses the intersections between area boundaries
and scan lines to identify pixels that are inside the area.
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 V_{1, }V_{2,} V_{3,} V_{4,} V_{5,}
V_{6 }and V_{7 }that are connected by edges E_{1, }E_{2,}
E_{3,} E_{4,} E_{5,} E_{6 }and E_{7} We assume that each vertex V_{1} has already been scanconverted to integer
coordinates (x_{1} y_{1}).
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 E_{1, }E_{7,} E_{6} and E_{4} 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 E_{5} 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 E_{5}.
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 V_{1} and V_{7} 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 V_{5} and V_{6}, 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.V_{4}) 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 V_{4}). The solution to this problem is to record
only one intersection point at the vertex.
Edge

y_{min}

y_{max}

X coordinate of vertex
with y= y_{min}

1/m

E_{1}

y_{1}

Y_{2 } 1

x_{1}

1/m_{1}

E_{7}

y_{1}

y_{7}

x_{1}

1/m_{7}

E_{4}

y_{5}

y_{4 } 1

x_{5}

1/m_{4}

E_{6}

y_{6}

y_{7}

x_{6}

1/m_{6}

E_{2}

y_{2}

y_{3}

x_{2}

1/m_{2}

E_{3}

y_{4}

y_{3}

x_{4}

1/m_{3}

In order to support an efficient implementation of this
scan line algorithm we create a data structure called an edge list. Each
nonhorizontal edge occupies one row/record. Information stored in each row
includes the y coordinate of the edge's two endpoints, with y_{min} being
the smaller value and y_{max} the larger value (may be decreased by 1
for reasons to be discussed below), the x coordinate of the endpoint whose y
coordinate is y_{min}, and the inverse of the edge's slope m. the
rows are sorted according to y_{min}. Since edges E_{1} and E_{7} both
originate from the lower vertex V_{1} at (x_{1}, y_{2 }) they
appear on top of the edge list, with m_{1} and m_{7 }being
their slope value, respectively.
Edges in the edge list become active when the y
coordinate of the current scan line matches their y_{min} 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 E_{1} and E_{7}
active. They intersect the scan line at (x_{1}, y_{1}).
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 E_{7} intersects scan line y at point b, and
so the next intersection point scan line y + 1 can be calculated by ∆x = 1/m_{1} 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 y_{max} 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 y_{max} 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 (V_{2} in the figure). This explains why the initial y_{max}
value for edges E_{1} and
E_{4} 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

y_{min}

y_{max}

x

1/m

E_{2}

4

7

9

0

E_{8}

4

7

2

0

E_{4}

7

9

8

0

E_{6}

7

9

4

0

(b) An edge becomes active when the scan line
value y equals the edge's y_{min} value. The edge remains active until
the scan line value y goes beyond the edge's y_{max} value.
Therefore,
the active edges for y = 6, 7, 8, 9 and 10 appears as follows.
At y = 6, E_{2} and E_{8}.
At y =
7, y = y_{max} for both edges E_{2} and E_{8} so they
remain active. Also at y = 7 E_{4} and E_{6 }become active.
At y =
8, E_{2} and E_{8} are removed from the edge list. E_{4}
and E_{6 }remain active.
At y = 9, the active edges remain the same.
At y =
10, edges E_{2} and E_{4} are removed from the edge list and the edge
list becomes empty.
No comments:
Post a Comment