Research and Advances

Scan conversion algorithms for a cell organized raster display

Raster scan computer graphics with “real time” character generators have previously been limited to alphanumeric characters. A display has been described which extends the capabilities of this organization to include general graphics. Two fundamentally different scan conversion algorithms which have been developed to support this display are presented. One is most suitable to noninteractive applications and the other to interactive applications. The algorithms were implemented in Fortran on the CDC6400 computer. Results obtained from the implementations show that the noninteractive algorithms can significantly reduce display file storage requirements at little cost in execution time over that of a conventional raster display. The interactive algorithm can improve response time and reduce storage requirements.

Advertisement

Author Archives

Research and Advances

A cell organized raster display for line drawings

Raster scan computer graphics displays with “real time” character generators have previously been limited to alphanumeric characters. A display is described which extends the capabilities of this organization to include general graphics. The feasibility of such a display is shown by deriving the minimum number of patterns required in the read only memory of the character generator to synthesize an arbitrary line. The synthesis process does not compromise picture quality, since the resulting dot patterns are identical with those of a conventional raster display. Furthermore, the time constraints of a raster display are shown to be satisfied for a typical design for very complex line drawings.
Research and Advances

A scan conversion algorithm with reduced storage requirements

Most graphics systems using a raster scan output device (CRT or hardcopy) maintain a display file in the XY or random scan format. Scan converters, hardware or software, must be provided to translate the picture description from the XY format to the raster format. Published scan conversion algorithms which are fast will reserve a buffer area large enough to accommodate the entire screen. On the other hand, those which use a small buffer area are slow because they require multiple passes through the XY display file. The scan conversion algorithm described here uses a linked list data structure to process the lines of the drawing in strips corresponding to groups of scan lines. A relatively small primary memory buffer area is used to accumulate the binary image for a group of scan lines. When this portion of the drawing has been plotted, the buffer is reused for the next portion. Because of the list processing procedures used, only a single pass through the XY display file is required when generating the binary image and only a slight increase in execution time over the fully buffered core results. Results show that storage requirements can be reduced by more than 80 percent while causing less than a 10 percent increase in execution time.

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved