Line drawing is our first adventure into the area of scan
conversion. The need for scan conversion, or rasterization, techniques is a
direct result of scanning nature of raster displays (thus the names).
Vector displays are particularly well suited for the display of lines. All that
is needed on a vector display to generate a line is to supply the appropriate
control voltages to the x and y deflection circuitry, and the electron beam
would traverse the line illuminating the desired segment. The only inaccuracies
in the lines drawn a vector display resulted from various non-linearities, such
as quantization and amplifier saturation, and the various noise sources in the
display circuitry.
When raster displays came along the process of drawing lines became more difficult.
Luckily, raster display pioneers could benefit from previous work done in the
area of digital plotter algorithms. A pen-plotter is a hardcopy device used
primarily to display engineering line drawings. Digital plotters, like raster
displays, are discretely addressable devices, where position of the pen on a
plotter is controlled by special motors called stepper motors that are connected
to mechanical linkages that translates the motor's rotation into a linear translation.
Stepper motors can precisely turn a fraction of a rotation (for example 2 degrees)
when the proper controlling voltages are applied. A typical flat-bed plotter
uses two of these motors, one for the x-axis and a second for the y-axis, to
control the position of a pen over a sheet of paper. A solenoid is used to raise
and lower the actual pen when drawing and positioning.
The bottom line is that most of the popular line-drawing algorithms used to
on computer screens (and laser and ink-jet printers for that matter) were originally
developed for use on pen-plotters. Furthermore, most of this work is attributed
by a single man, Jack Bresenham, who was an IBM employee. He is currently a
professor at Winthrop University.
In this lecture we will gradually evolve from the basics of algebra to the famous
Bresenham line-drawing algorithms (along the same lines as a famous paper by
Bob Sproull), and then we will discuss some developments that have happened
since then.