GIT-GVU-93-22

Run-Based Multi-Point Line Drawing

Eun Jae Lee
Larry F. Hodges

Line drawing on discrete graphics devices such as raster video displays, plotters, and image printers is one of the fundamental operations in computer graphics. Real-time interactive applications or high speed image output (such as on a Postscript laser printer) may require line drawing speeds in the millions of pixels per second. Such demands, which are ever increasing, push the efficiency of line generation.

For nearly thirty years Bresenham's algorithm has been the standard which subsequent efforts in line drawing have sought to surpass. This work can be broadly classified into three groups: parallel algorithms which divide line generation over multiple processing units; multi-point algorithms which output a fixed number of pixels in each iteration with fewer decision tests per pixel; and structural methods, including run-length algorithms, which identify periodic patterns in raster lines to reduce the number of decision tests or even to eliminate them.

This paper describes a hybrid method which uses structural properties of raster lines, such as runs, to improve the efficiency of multi-point line generation. A quadruple-step algorithm is developed which requires fewer decision tests than other multi-point algorithms, while retaining the multi-point's advantage in pixel output efficiency, particularly when implemented in hardware. A hardware state-machine circuit is described which efficiently implements the algorithm and outputs a four pixel segment every machine cycle.

Line drawing, computer graphics, real-time interaction, Bresenham's algorithm, parallel algorithm, multi-point algorithm, run-length algorithm

PDF

Postscript