Pere Mares, Antonio B. Martinez, Joan Aranda
Departament of Automatic Control and Computer Engineering
Universitat Politecnica de Catalunya (UPC)
Pau Gargallo, 5. 08028. Barcelona. Spain.
E-mail: [pere.mares,antonio.b.martinez,joan.aranda]@upc.es
Depicting straight-line segments on raster devices is one of the main tasks in the generation of drawings by computer. To cite some examples, we find straight-line segments in block diagrams, bar graphs, drafts for civil and mechanical engineering, architectural plans and logic diagrams. In addition, curves can often be approximated using a series of very small line segments.
In graphic interactive applications, the problem of line drawing is how to obtain those pixels that provide the best approximation to the line in a shorter time.
In an attempt to provide an improvement in line drawing speed, we propose to accelerate the process of obtaining the pixels to be drawn and to shorten the display memory write time. In order to achieve these goals we aim to:
a) Find a parallel line-drawing algorithm allowing hardware implementation.
b) Design, test and simulate an ASIC co-processor capable of calculating and memorizing in parallel the pixels that approximate the straight-line segments.
A parallel algorithm is proposed which does not use the classical incremental techniques that obtain the present pixel coordinates from the previous ones. In our case, the computation to determine if a certain pixel belongs to a segment consists of a single comparison at every pixel between previous common computed values for each row and column of the screen. The maximum efficiency is obtained when placing one processor by pixel in which case the pixels that approximate the straight segment are obtained simultaneously.
The simplicity of the obtained parallel algorithm allows a direct implementation of a parallel architecture consisting in a matrix (MXN) of very simple pixel processors and N+M column and row calculation units. This coprocessor architecture allows writing simultaneously in just one clock cycle all the pixels that approximate a given straight segment. In this way the writing speed is only limited by propagation time of the technology used in the implementation. This co-processor also provides read/write random accesses and raster outputs in order to display the data serially in a graphic device.
As a sample, a VLSI 256x256 eight-bit pixel processor array has been implemented using 0.35 micrometers standard cells with three metal layers. It could be easily extended to 24bit true color by combining three ASICs. An exhaustive test and simulation results upon this design have demonstrated that a rate of 50M segments per second can be drawn, independently of their length and orientation.