The scan-line polygon fill algorithm is used to colour in any closed shape. The algorithm uses the concept of scan lines, being the horizontal lines that make up a digital display.
Two data structures are central to the algorithm: an ‘all edges table’ (
ET), and an ‘active edge table’ (
ET stores a list of the edges defining the polygon to colour in, whereas
AET holds the edges that intersect with the current scan line.
All edges start in
ET, and move to
AET as they are ‘hit’ by the scan line.
Initialising the Scan Line
Scan lines are typically drawn from the bottom to the top of the screen.
So, simply initialise the scan line to the lowest y-value ‘touched’ by the polygon (i.e., the minimum y-value of the first entry in the sorted
For each non-horizontal edge defining the outline of the polygon, store:
- the minimum y-value of the two endpoints
- the maximum y-value of the two endpoints
- the x-value that corresponds with the minimum y-value
mis the gradient of the edge
ET in ascending order, by minimum y-value.
If two edges have the same minimum y-value, sort them in ascending order by x-value.
We do this so that we can efficiently move entires from
Because the scan line starts at the bottom of the screen and moves up, we can trigger the movement of an edge from one table to another when the scan line y-value is equal to the minimum y-value for an edge.
If the edges are sorted by minimum y-value, this can be done a lot faster.
We ignore horizontal edges to ensure they get drawn.
If they were left in
ET, they would trigger a parity change at every step (see ‘Parity’, below), hence would break the drawing algorithm.
AET simply move all edges with the lowest minimum y-value from
ET is sorted, this should not be an expensive operation.
In order to know when to colour pixels, the algorithm uses the concept of ‘parity’.
parity is defined, and initialised to
At each step on the scan line (from left to right), the value of parity is checked. If parity is odd, the current pixel is coloured; if parity is even, the pixel is left alone.
As a scan line is drawn, collisions with a polygon edge trigger a reversal of parity (i.e., even to odd, odd to even). This means that with parity initialised to even, the first collision with the polygon (i.e., when the scan line ‘enters’ the polygon) will start drawing, by flipping parity to odd. The second collision (i.e., when the scan line ‘leaves’ the polygon) will stop drawing, by changing parity back to even.
After initialisation, the following steps describe the fill algorithm:
Colour all pixels between pairs in the
For example, if the
AETcontained four entries, with x-values
[1, 7, 8, 19], the pixels in the range
x = [1, 7)and
x = [8, 19)should be coloured. As the scan line is horizontal, its current y-value can be used.
Increase the scan line y-value by 1 (i.e., move the scan line up).
Remove any edges in the
AETwhere the maximum y-value is equal to the current scan line y-value.
Update the x-intercepts for each edge in the
For each edge in the
AET, the x-value represents the x-coordinate at which the scan line will intercept that edge. So, initially
xis set to the coordinate corresponding to the minimum value of
yfor that edge, as that is when the edge will first intercept the scan line.
However, as the scan line moves up we need to update the value of
We can figure this out by using the equation for the gradient of a line,
m, at the
kth point in that line:
m = (y(k + 1) - y(k)) / (x(k + 1) - x(k))
Because the scan line always moves up by
1each iteration, we know that:
y(k + 1) = y(k) + 1
By substituting this into the equation for
m, we can find the general formula for incrementing
m = (y(k + 1) - y(k)) / (x(k + 1) - x(k)) = (y(k) + 1 - y(k)) / (x(k + 1) - x(k)) = 1 / (x(k + 1) - x(k)) m * (x(k + 1) - x(k)) = 1 x(k + 1) - x(k) = 1 / m x(k + 1) = x(k) + (1 / m)
So, to increment
x, we add
1 / mto it’s current value. Conveniently, this value is stored in
Move any edges from
AETif the scan line y-value is equal to the edge’s minimum y-value.
AETby x-value to avoid complications caused by crossing lines.