Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Technique for Vector Graphics Scan Conversion

IP.com Disclosure Number: IPCOM000086232D
Original Publication Date: 1976-Aug-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 3 page(s) / 48K

Publishing Venue

IBM

Related People

Niehoff, WH: AUTHOR

Abstract

Herein described is an improved technique for processing a list of graphic vectors to yield a discrete binary map of picture elements for a raster-oriented output device. Such devices include raster displays and printers.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Technique for Vector Graphics Scan Conversion

Herein described is an improved technique for processing a list of graphic vectors to yield a discrete binary map of picture elements for a raster-oriented output device. Such devices include raster displays and printers.

The principal technical problem is that the picture element density is so high that the buffering required to support the normal "bit per element" approach to scan conversion becomes prohibitively expensive. For example, one present printer technology would require on the order of five million bits if the conventional approach were chosen.

It has been previously described how the large buffer requirement could be overcome by processing -- that is, the vector representation of the picture was scissored on horizontal and vertical boundaries forming "subwindows", each of which, because of its smaller size, could be handled on a bit per element basis with an arbitrarily smaller buffer.

The principal feature herein described is the removal of the need for explicit clipping on vertical boundaries. As will be shown, this is accomplished by a work suspension process. A second feature is that horizontal boundary clipping is now a process done on integer rather than half-raster unit boundaries. Finally. the components of the processes embodying the technique have been formulated so as to permit implementation in programming, microcode or hardware, depending on the process performance required.

Referring to the flow chart, the first process (1), Initialization, clears the output buffer as well as a horizontal spill queue and a vertical save area.

Process (2) causes the vectors. which are represented in a list called BASE in the form (x, y, delta x, delta y), to be oriented in the positive y-direction. This is a prerequisite to process (3). This orientation is accomplished by checking if the delta y for each vector is positive. If not, y is replaced by y+delta y, delta y by - delta y, and delta x by -delta x. simple arithmet operations.

Process (3) scissors out of BASE those vector segments in a horizontal band defined by the current location of a horizontal boundary. The set of vectors in this band is called the WAKE. The process is implemented using simple comparisons and arithmetic on the vector representation. Three possible situations are possible: a) A vector is totally outside the wake band. In this case, the vector is not incorporated in the WAKE. b) A vector is totally inside the wake band. In this case, the vector is moved to the WAKE representation and removed from the BASE. c) A vector is both inside and outside the wake band
(i.e., is intersected by the wake boundary). In this case, the intersection point is computed by conventional techniques iteratively dividing the v...