Polygon Scan Conversion: Background

This section will give a brief history of graphics w.r.t. raster-scan displays, and provide motivation for the study of scan conversion algorithms in general, and specifically polygon scan conversions.

Why Scan Conversion?

Interactive graphics displays require display devices whose images can be changed quickly. In order to extract the maximum possible performance from the display device, the algorithms used for displaying and computing images need to be tailored for the type of display devices used.

In the sixties and early seventies, the most common and inexpensive [relatively speaking] display devices were the Vector Displays. In a vector display system, the processor generated point- and line-plotting commands with endpoint coordinates. These coordinates were sent to a vector generator that converted the digital values to analog voltages for the beam-deflection circuitry. The display circuitry would deflect the beam from endpoint to endpoint as required by the display commands sent to it.

In the early seventies, Raster Displays were developed. These displays stored the graphics primitives in terms of their component pixels. The pixels "images" were stored in a raster, which consisted of a set of horizontal raster lines, each of which was a row of pixles corresponding to a row on the display screen. The entire raster was scanned rowwise, onto the screen eveytime the screen was refreshed.

In order to calculate the raster image for each screen refresh, different techniques were needed. Each primitive needed to be processed to produce a set of pixels that corresponded to the primitive. Since screen refreshes occur very often (usually at a rate that is greater than 60 Hz), the processing of primitives needed to be done at a correspondingly fast rate. For this, algorithms that could perform up to the reuqired specification were needed. Also, these algorithms needed to be able to take advantage of the pixellated nature of each primitive. Scan conversion algorithms were developed to fill this need.

Why Polygon Scan Conversion?

Mathematics and graphics define a lot of different primitives -- lines, circles, ellipses, polygons, rectangles, etc are all 2-D primitives. However, most real world objects are irregular and not easily classified as regular objects such as ellipses or rectangles. Polygons, on the other hand, are a generic object that can encompass a large number of different objects. Other objects, such as circles and curves, can be approximated by using polygons. These attributes of polygon primitives cause them to play an important part in computer graphics. As a result, the Polygon Scan conversion algorithm is of fundamental importance.

From Graphica -- see details 26.11.1996