Drawing polygons#

As well as being able to draw lines on a raster display we also need to be able to draw polygons. Drawing polygons can be achieved using one of two approaches, we can either draw the outline of the polygon using line drawing algorithms and then fill in all of the pixels inside the polygon or just draw the polygon, including the pixels in the interior, all at once. A successful method should produce a filled polygon with no holes in the interior of the polygon, i.e., all pixels that are contained within a polygon should be illuminated using the desired colour. These notes discuss two algorithms that use each of these approaches: the flood fill algorithm and the scanline fill algorithm.

Flood fill algorithm#

The flood fill algorithm is used to fill a polygon that has been rendered on a raster array using the line drawing algorithms. Given the position of a starting pixel \((x_0,y_0)\) that is known to be in the interior of the polygon, the flood fill algorithm illuminates that pixel and moves to a neighbouring pixel either to the east, west, north or south direction. At each pixel, a check is performed to see whether the pixel requires illuminating. A pixel is only illuminated if its current colour is the same as a \(target\) colour. If the pixel is to be illuminated then its colour is set to that of the \(replacement\) colour and the process is restarted using an adjacent pixel.

To keep track of the pixels that need to be considered a LIFO (Last In First Out) queue is used. The queue (also known as a stack) is initialised so that it only contains the starting pixel \((x_0,y_0)\). At each iteration of the method the last pixel in the queue is removed and is checked to see if the current colour of the pixel is the same as the target colour. If it is then this the pixel is plotted using the replacement colour and the four neighbouring pixels to the right, left, bottom and top are added onto the end of the queue. This continues until the queue is empty.

Algorithm 10 (Flood fill algorithm)

Inputs A raster array \(R\), pixel co-ordinates of the starting pixel \((x_0, y_0)\) the target colour \(target\) and the replacement colour \(replacement\).

Output A raster array \(R\).

Initialise \(Q \gets (x_0, y_0)\) (\(Q\) is a list or array)
While \(Q\) is not empty do
- Remove the last pixel in \(Q\) and store the co-ordinates in \(x\) and \(y\)
- If \(R(x, y) = target\) then
  - \(R(x, y) \gets replacement\)
  - Append pixels \((x+1, y)\), \((x - 1, y)\), \((x, y+1)\) and \((x, y-1)\) to \(Q\)
Return \(R\)

Example 41

Starting with the pixel at \((4, 4)\), use the flood fill algorithm to fill in the polygon on the raster below where the target colour is white and the replacement colour is blue.

Use of the flood fill algorithm#

Since the flood fill algorithm uses adjacent pixels to the four compass directions to spread the fill colour across a polygon is cannot spread across tight corners. This can be desirable since if the width of the outline is a single pixel then the flood fill will not leak outside of the polygon. In practice the flood fill algorithm is too computationally expensive to be used for virtual worlds and is only really used in drawing applications to provide a filling tool.

../_images/flood_fill_tight_corner.png — Fig. 101 The flood fill algorithm is blocked by tight corners.#

The scanline algorithm#

The scanline algorithm is a method of rendering a polygon without drawing the edges beforehand unlike the flood fill algorithm that requires pixels to be plotted to form an outline. Instead of testing pixels one by one, the scanline filling algorithm loops through horizontal rows of pixels, known as a scanline starting at the top of the raster and finishing at the bottom. If the scanline intersects with an edge of the polygon the intersection points, which are known as span extrema, are calculated and sorted into ascending order and all pixels between pairs of intersection points are filled.

Definition 28 (Scanline)

A horizontal row of pixels.

Definition 29 (Span extrema)

A pixel where a scanline intersects with the edge of a polygons.

Calculating the span extrema#

../_images/span_extrema.svg — Fig. 102 Calculating span extrema co-ordinates.#

Consider Fig. 102 where the co-ordinates of the span extrema on the left edge of a polygon are \((x_i, y_i)\) and \((x_{i+1}, y_{i+1})\). If \((x_i, y_i)\) are known then the next value \(y_{i+1}\) is easily calculated using \(y_{i+1} = y_i + 1\). The values of the \(x\) span extrema co-ordinates are calculated using the slope intercept equation of a line.

\[ \begin{align*} y = m x + c, \end{align*} \]

where \(y\) and \(x\) are the co-ordinates of a point on the line, \(m = (y_{\min} - y_{\max}) / (x_{\min} - x_{\max})\) is the gradient of the line and \(c\) is where the line intercepts the \(y\)-axis. Rearranging this to make \(x\) the subject gives

(35)#\[x = \frac{1}{m} (y - c).\]

To derive an expression for calculating \(x_{i+1}\) we let \(x_{i+1} =x \) and rearrange equation (35) and substitute \(y_{i+1} = y_i + 1\)

\[\begin{split} \begin{align*} x_{i+1} &= \frac{1}{m} (y_{i+1} - c) \\ &= \frac{1}{m} (y_i + 1 - c) \\ &= \frac{1}{m} + \frac{1}{m}(y_i - c). \end{align*} \end{split}\]

Since \(x_i = \dfrac{1}{m} (y_i - c)\) then

\[ \begin{align*} x_{i+1} &= x_i + \frac{1}{m}. \end{align*} \]

So calculating the values of \(y_{i+1}\) and \(x_{i+1}\) is simply a matter of adding 1 to \(y_i\) and \(1/m\) to \(x_i\).

Edge tables#

We only want to perform the span extrema calculations on polygon edges that intersect a scanline, known as active edges and ignore the rest. To do this we use an Edge Table (ET) to store information for all edges of a polygon and an Active Edge Table (AET) that only contains information for the active edges. The information that is stored in the ET is the \(x\) co-ordinate of the current span extrema, \(1/m\), \(y_{\min}\) and \(y_{\max}\)

../_images/active_edges.svg — Fig. 103 As the scanline moves down the polygon different edges become active.#

To start with we initialise ET so that it contains all of edges of a polygon and the AET is empty. Then as we move down the scanlines some of the polygon edges will become active edges and some of the active edges will become non active (Fig. 103). Any edge in the ET that has \(y_{\min}=y\) has become active so are moved to the AET. The AET table contains \(x\), \(1/m\) and \(y_{\max}\) (we don’t need \(y_{\min}\) from now on).

../_images/scanline_fill.svg — Fig. 104 The pixels between pairs of span extrema are filled.#

The \(x\) values in the AET contain the \(x\) co-ordinate of the span extrema. The AET is sorted in ascending order by the \(x\) values and then all pixels between pairs of span extrema are filled (Fig. 104). Once a scanline has been filled, any edge in the AET that has \(y_{\max} =y\) will become non-active and is removed from the AET. When both the ET and AET are empty the polygon has been drawn and the algorithm terminates.

Algorithm 11 (The scanline algorithm)

Inputs: A raster array, the pixel co-ordinates of the polygon vertices and the colour of the polygon

Outputs: A raster array

ET \(\gets \emptyset\) and AET \(\gets \emptyset\)
For each edge of the polygon add \([x, 1/m, y_{\min}, y_{\max}]\) to ET
\(y \gets 0\)
While ET or AET are not empty
- Move edges in ET that have \(y_{\min} = y\) to AET
- Sort AET by \(x\) in ascending order
- Fill pixels between every pair of \(x\) co-ordinates (rounding the left co-ordinate up and the right co-ordinate down) with the colour of the polygon
- Remove edges in AET that have \(y_{\max} = y\)
- Add \(1/m\) to \(x\) to the edges in AET
- \(y \gets y + 1\)
return \(R\)

Note

The scanline algorithm presented here uses floating point numbers for \(1/m\) and the span extrema co-ordinates. In practice the scanline algorithm uses a method similar to Bresenham’s algorithm so that we are only dealing with integer numbers.

Example 42

Use the scanline algorithm to draw the polygon defined below

Computer Graphics Lecture Notes

Drawing polygons

Contents