Efficient polygon-filling algorithms for raster displays

Reviewer: Joseph J. O'Rourke

Polygon-filling algorithms are ubiquitous in computer graphics. They come in two main varieties: flood algorithms, which grow to all connected pixels from a seed, and parity-based algorithms, which invert interior pixels an odd number of times and exterior pixels an even number. Dunlavey presents two algorithms of the second variety. The first is Ackland and Weste's region-oriented procedure [1], which assumes that the pixels lie between the grid lines. The second is an original vector-oriented algorithm, which assumes that the pixels lie on the grid lines. Both algorithms are described in a uniform notation and explained very clearly. Speed-ups are suggested that limit the length of the scan line inversion. Finally, a careful proof of correctness is provided for the vector-oriented algorithm.