Raster display smooth line generation

We claim:

1. In a raster type image-generating system, a high speed arrangement for generating for display a smooth line of consistent thickness regardless of slope, in which said line is defined by a starting end point position and a concluding end point position specified to a fractional pixel precision comprising:

(a) first means for deriving information representing the slope of said line to n bits of said fractional pixel precision;

(b) means, responsive to said end point positions and to said first deriving means, for identifying a plurality of pixel positions relevantly proximate to said end point positions, and for identifying a plurality of one-dimensional arrays, each of said arrays being at least three contiguous pixel positions defining a cross-section point of the interior portion of said line between said end point positions;

(c) second means, responsive to said end point positions and said deriving means, for deriving information representative of the distance of each of said pixel positions of said arrays from said line;

(d) first means, responsive to said starting end point position, to said second deriving means and to said identifying means, for determining a value representative of a level of intensity between a selected minimum and maximum to be associated with each of said pixel positions relevant to said starting end point position, said value being a function of the location of said pixel position relative to said starting end point position;

(e) second means, responsive to said first and second deriving means and said identifying means, for determining a value representative of a level of intensity between said selected minimum and maximum to be associated with each of said pixel positions of each of said arrays, said value being a function of the slope of said line and the distance between said pixel position and said line; and

(f) third means, responsive to said concluding end point position, to said second deriving means and to said identifying means, for determining a value representative of a level of intensity between said selected minimum and maximum to be associated with each of said pixel positions relevant to said concluding end point position, said value being a function of the location of said pixel position relative to said concluding end point position.

2. A system as recited in claim 1 further comprising means for enabling said first, second and third determining means to effectively operate in a selected one of a plurality of coordinate system octants regardless of the octant orientation of said line.

3. A system as recited in claim 1 further comprising means for sequentially effecting operation of said first, second and third determining means.

4. A system as recited in claim 1 wherein said arrays are parallel to each other, and said second determining means effects a zig-zag sequential pattern of coverage of said arrays.

5. In a raster type image-generating system, a high speed arrangement for generating for display a smooth line of consistent thickness regardless of slope, comprising:

(a) means for resolving in a single operative cycle first axis positional information to a selected number of bits of fractional pixel precision for each integral step in position along a portion of a second axis associated with said line; and

(b) first means operatively connected to said resolving means and responsive to a combined input signal comprising the slope of said line, rendered to n.sub.1 bits of fractional pixel precision, and the separation of said line, to n.sub.2 bits of fractional pixel precision, from a relevant pixel position for providing a value which is representative of an intensity to which said pixel position is to be set in displaying said line.

6. A system as recited in claim 5, wherein said first means comprises means for providing said value for each one of an array of at least three contiguous pixel positions for each integral second axis step.

7. A system as recited in claim 6 wherein said values are provided during a single operative clock cycle of said providing means.

8. A system as recited in claim 5 or 6 further comprising polychromatic proportional weighting means, responsive to an existing value representative of an intensity associated with said pixel position, to a desired color of said line, and to said value for said pixel position provided by said first means for said line, for generating a new value representative of intensity and color for said pixel position.

9. A system as recited in claim 5 or 6 further comprising proportional weighting means, responsive to an existing value representative of an intensity associated with said pixel position, to a value representative of an intended intensity of said line, and to said value for said pixel position provided by said first means, for generating a new value representative of intensity for said pixel position.

10. An improved digital differential analyzer for determining in a raster type line generating display system first axis (Y) positional information to a selected number (n) of bits of fractional pixel precision for each integral step in position along a predetermined portion of a second axis (X), wherein the improvement comprises:

(a) slope register means for receiving information representing the slope of a line segment to be displayed;

(b) first register means for receiving initially a resultant of the function (Slope.multidot.DX)-(2.sup.n .multidot.DY), where

Slope=the slope of said line segment,

N=said selected number of bits of fractional pixel precision, and

DX and DY=differences between an ending and a starting first and second axis position, respectively;

(c) second register means for receiving said resultant plus DX;

(d) multiplexer means connected to said first and second register means for selectively receiving the contents of said first and second register means;

(e) first adder means, a first input of which is coupled to said multiplexer means;

(f) second adder means, a first input of which is coupled to said slope register means;

(g) accumulator means connected to the output of said first adder means, said accumulator means having an output connected to said multiplexer means, to a second input of said first adder means and to a carry input of said second adder means;

(h) first axis position register means for receiving intially a starting-position first axis information, said first axis position register means being connected to the output of said second adder means and having its output connected to a third input of said second adder means, said second adder means output comprising an integer portion and fractional portion representative of said first axis positional information for a given second axis position; and

(i) means for simultaneously actuating said first and second adder means and for synchronously clocking said accumulator means and said first axis position register means once for said given second axis position associated with said line;

Whereby said first axis positional information for said given second axis position is calculated during a single clock cycle for any value of said selected number n.

11. An improved analyzer as recited in claim 10 wherein said first and second adder means constitute portions of a single adder means.

12. In a raster type line generating polychromic display system, an improved arrangement for the proportional weighting of pixel position values as a function of intensity, a desired color and a proportionality constant to provide new pixel position values, wherein the improvement comprises first, second and third ROM means, each respectively associated with one of a set of primary colors and containing a table of addressable predetermined values, for providing a digital output signal representative of said respective primary color's portion of said new pixel position value in response to a combined digital input signal comprised of parts which are respectively representative of an existing pixel value, said desired color and .alpha., where .alpha. is a value representative of a fractional coverage of a pixel by a line to be displayed and constitutes said proportionality constant.

13. In a high speed raster type system for accurately generating a smooth line for display, the improvement in combination comprising:

(a) first means for resolving end points defining said line to fractional pixel precision;

(b) second means, responsive to said first means, for identifying positionally relevant pixel positions related to each of said end points enabling a true representation of said end points; and

(c) third means, responsive to said second means, for deriving in a predetermined sequence values representative of a level of intensity between a selected minimum and maximum to be associated with each of said positionally relevant pixel positions for each of said end points.

Description Submit all comments and votes

BACKGROUND AND SUMMARY OF THE INVENTION

This invention relates to the generation of smooth lines or edges of images in raster-scan type displays, and more particularly to line generating apparatus for displaying smooth lines with intensity and color modulated picture elements (pixels). As used herein, the word "line" shall generally be deemed to include and cover edges of characters or other images.

To reconstruct a line in raster format, digital differential analyzer (DDA) may be used. For each incremental step of the DDA, say on the X axis, Y-position information will be generated for every pixel in the line. This is true, of course, for lines closer to the X axis (less than 45 degrees from horizontal). For lines closer to vertical (Y axis), the DDA will generate X-position information for steps along the Y axis. Accordingly, in the former case the so-called large axis would be the X axis and in the latter case the large axis would be the Y axis, and in each case the so-called small axis would be the axis perpendicular thereto. Thus, the DDA steps along the large axis, generating small axis position information.

Due to the fixed location of the raster pixels, the equivalent line usually has a staircase structure or is jagged. If the DDA is allowed to operate at a higher resolution than the raster screen resolution, the distance between the true or theoretical line and the individual pixel position (a function of the small axis distance) can be resolved and utilized in terms of modulating pixel intensity to create the appearance of a smooth line.

This technique has been successfully implemented in so-called purely software arrangements involving complex and very precise algorithms, and in hardware arrangements as may be represented, for example, by the disclosure in Japanese Patent Application No. 2626/79, filed on Jan. 12, 1979 to Daini Seikosha (Disclosure No. 95986/80, July 21, 1980; inventor Masayuki Matsumoto). A basic objection of the purely software arrangements is the relative slowness with which the lines are recreated accurately in display (i.e. graphics drawing speed), which is a principal result of the sequential nature of internal operation of such an arrangement.

Known hardware systems, while generally being able to substantially improve upon the speed of operation, nevertheless significantly suffer in terms of the actual displayed image by virtue of inadequate intensity (and color) modulation regarding the full compliment of pixels relevantly associated by position to the true or theoretical line intended to be recreated. Moreover, such systems tend to produce images in which readily apparent changes in line thickness occur as a function of the slope of the line. That is, lines other than vertical (Y axis) or horizontal (X axis) will varyingly (with slope) appear thinner, with lines having a 45 degree slope orientation appearing thinnest of all.

Additionally, these systems do not resolve the line end points to fractional pixel precision, and the lines must begin and end centered on a pixel position. Thus, although an advance may be provided with respect to line smoothing per se, none is provided with regard to precise line positioning. This effect is particularly undesirable in the case of approximately smooth curves comprised of many short vectors or line segments.

Even if such systems did resolve the end points to fractional pixel accuracy, there would still be needed special end point treatment to eliminate or prevent the appearance of angular slicing of the ends of the lines. This angular slicing effect stems from terminating the lines horizontally or vertically even when the lines are oriented other than vertically or horizontally.

In the arrangement depicted in the above-mentioned patent application, as example, intensity information may be said to be generated for two pixels on the small axis (e.g. Y axis) for each step along the large axis (X axis), i.e. the pixel on the line (or closest to it) and the adjacent pixel next closest to the line, with the total (fully-on) intensity of a single pixel being apportioned between them. Such line coverage is insufficiently selective to provide a highly accurate representation of the true line, particularly in view of those situations where all relevant pixels in the small axis for a given large axis increment would include not only the pixel on the line itself but the adjacent pixels on each side of the line. Moreover, this previously disclosed system does not solve the problem of varying line thickness with slope. It is thus deemed incapable of suggesting an efficient and high speed approach for full and consistent line coverage, i.e. providing small axis position information with regard to each pixel of a 3 (or more)-pixel array encompassing the line for a step along the large axis, and slope independence.

Reconstruction of a near-perfect anti-aliased or smooth image requires knowledge of every line crossing a given pixel before determining its intensity (or indeed its color in polychromatic systems), and utilization of this information to achieve an appropriate balance between the intensity values and/or colors associated to respective lines. A system attempting to carry this out would, however, be unacceptably slow.

Previous systems have either ignored the so-called old pixel value (e.g. the value already stored in the frame buffer system for a first line to be drawn), or used it in a so-called maximum value operation, with alpha (in its simplest form the fractional coverage of a pixel by the line to be drawn) times the line intensity. In the latter case, which is monochrome only, the effect is to write the new pixel value only if it is larger than the old value. In either case, the average errors are greater than say for proportional weighting when compared to the above-mentioned ideal case.

The above drawbacks are overcome according to the present invention, wherein a high speed system is provided for generating smooth lines to n bits (typically up to 6) of fractional pixel accuracy, both as to the line mid-section and its end points, and which provides special end points treatment which assures a true representation of the line, properly positioned, in display. The small axis distance information and slope information are utilized to assign alpha values (e.g. gray scale or intensity values in a monochrome system) to a set of pixels (at least 3) in an array providing a highly representative cross-section of the theoretical line for the incremental portions (large axis) of a DDA with consistency of line thickness regardless of line slope. Successive arrays of relevant pixels are sequentially treated efficiently in a zig-zag coverage of the line in conjunction with the special end points treatment. The small axis positional information for each array of pixels is generated within a single clock cycle. The alpha values generated are utilized, when appropriate, to provide proportional weighting between old pixel values and the desired line color, with alpha being the proportionality constant.

In a system according to the invention, sequencing of the pixels is such as to require only X and Y increment/decrement commands along with alpha values to be supplied to the frame buffer system. Since smoothing is accomplished during the building of the raster image, no after-filtering is required. Moreover, an operative mode of selective erase can be readily effected.

BRIEF DESCRIPTION OF THE DRAWINGS

The above-mentioned and other features and advantages of the present invention will become better understood with reference to the following detailed description taken in conjunction with the accompanying drawings, in which:

FIG. 1 illustrates in block form a typical global architecture of a raster scan display system;

FIG. 2 illustrates in a block diagram the global architecture of line smoothing improvements to a raster scan system such as is depicted in FIG. 1, in accordance with the invention;

FIG. 2A is a graphic illustration of line smoothing in accordance with the invention by varying the intensity of each pixel of each 3-pixel array encompassing the center portion of the line to be drawn;

FIG. 2B is a blow up of one such array taken at B--B of FIG. 2A and illustrating the geometric relationship between the line to be drawn and the fixed pixel positions;

FIG. 3A illustrates in block diagram form, interfacing between the micro-coded engine portion of the system depicted in FIG. 1 on the one hand and the central processing unit (CPU), line smoothing hardware, and frame buffer thereof on the other hand;

FIG. 3B is a block diagram of a micro-coded engine useful in the system of FIG. 2;

FIG. 4 is a block diagram illustrating a digital differential analyzer arrangement of the raster scan system of FIG. 2, in accordance with the invention;

FIG. 5 illustrates in block form an anti-aliasing value generator arrangement for the system of FIG. 2, in accordance with the invention;

FIG. 6 is a graphical representation of a pixel intensity gray scale employable in the system of FIGS. 2 and 5;

FIG. 7 is a schematic block diagram illustrating in greater detail the system of FIG. 5;

FIGS. 7A-7C illustrate the operation of the octant register 164 and adder/substracter 165 of FIG. 7;

FIG. 8 is a block diagram illustrating a proportional weighting function operable in the system of FIG. 2; and

FIGS. 9A-9E are graphic illustrations of various generations being performed by the line smoothing arrangement of the present invention in recreating a line in raster format, wherein for ease of illustration, pixels are shown centered in the grid squares, rather than at the vertices as in FIGS. 2A and 2B.

DESCRIPTION OF THE PREFERRED EMBODIMENT(S)

In the raster scan display system illustrated in FIG. 1, for example a color-video system with optional hard-copy capability (the system in practice may take the form of a raster computer terminal or a stand-alone computer graphics system), a display processor 100 is interconnected to and controlled by a central processor unit (CPU) and its interfacing 60,65. In particular, CPU block 60 may be thought of as including one or more data sources connected to a CPU (e.g. an 8086 commercially available from Intel Corporation) via a host interface, with the CPU in turn being operatively connected to the display processor via a display list memory and a memory (or CPU) interface.

The display processor is operatively linked by lines 105 to a frame buffer unit 200 of conventional construction. The frame buffer stage in turn is coupled to a monitor, e.g. a video display, by video and sync lines 215 and may also be coupled by lines 203 to a hard copy unit such as a printer 110. The latter would also be controllably connected to the display processor 100 via line 115.

Frame Buffer Specifications

The frame buffer 200 of FIG. 2, along with counters 205 and 210, may have the following capabilities. The counters can be individually loaded with any value from the microcoded engine. Further, they can be incremented and decremented under control of say a 3-bit step command carried by connection 178. The Y counter 205 will increment on the step commands 1, 2 and 3, decrement on commands 5, 6 and 7, and hold (do neither) on commands 0 and 4. The X counter 210 will increment on step commands 7, 0 and 1, decrement on commands 3, 4, and 5, and hold on commands 2 and 6. These step commands are graphically illustrated in FIG. 7B. The values in counters 205 and 210 at any one instant address storage for a single pixel of say 8 bits. This pixel data can be read over line 195, or written to a new value from line 194. By changing the values in the counters, every pixel on the screen can be addressed.

Transparent to the accesses over lines 194 and 195, the frame buffer memory may be read out 60 times a second in raster scan order, with this data being sent to the display over the 215. The frame buffer addressing for this display output is generated by a separate counter, which also generates horizontal and vertical sync signals for the display monitor. This counter is not shown, as it is a standard part of raster scan frame buffer systems. Transparency between the two frame buffer access mechanisms may be obtained in this system by alternating memory cycles between this screen refresh task and the accesses over lines 194 and 195 using counters 205 and 210. The other common method is to allow access over lines 194 and 195 only during horizontal and vertical retrace times. The latter option decreases performance, but otherwise has no effect on a system with this invention.

FIGS. 3A and 3B illustrate an implementation of a micro-coded engine utilizable in the raster system of FIG. 2. For ease of understanding, the following table of abbreviations is provided.

______________________________________ Abbreviation Explanation ______________________________________ Reg. Register .mu. pipe pipeline register 73 or its output PP Wait Picture (Display) Processor Wait MUX Multiplexer NZVC Negative; Zero; Overflow; and Carry HRA Holding Register A HRB Holding Register B .mu. ROM Micro ROM, referring to where the micro code is stored. ALUOUT BUS The output bus of arithmetic logic unit 74. ______________________________________

It will be appreciated that the coding of the micro-coded engine to perform the various functions depicted herein is well within the skills of the average practioner in this art, and such an exercise thus is not detailed herein. For a more complete understanding of micro-coded engines and implementing same, see, for example, the following publication: Build a Microcomputer, Chapter II, Microprogrammed Design, Advanced Micro Devices, 1978, AM-Pub 073-2.

The micro-coded engine of FIGS. 2 and 3B is comprised of micro-sequencer stage 71 (e.g. a 2910 of Advanced Micro Devices, Inc.), connected to both pipeline bus 150 and primary bus 140 on the one hand, and to an instruction ROM 77 (eg 4K.times.48) on the other hand, with the latter being coupled to pipeline register 73. Included also are an arithmetic logic unit (ALU) 74, eg six 2901's commercially available from Advanced Micro Devices, Inc. input connected to both the primary and pipeline buses, an auxiliary RAM 78 (e.g. 4K.times.24) with address block 78a, input coupled to the pipeline bus 150 and connected to the primary bus 140, an immediate data buffer 79 similarly connected to the pipeline and primary buses, and holding registers 75. The holding registers 75a and b communicate with the primary bus and in addition are in communication with the ALU 74 via ALU output bus 170. Although not specifically illustrated, the registers 75, as is the case with regard to most of the other blocks in FIG. 3B, receive control signals in conventional manner from control decoding block 77.

With reference again to FIG. 2, there is illustrated in block diagram form the display system line smoothing capability 80 interconnected with the system's micro-coded engine 70 on the one hand (to comprise the display processor 100) and the frame buffer 200 on the other hand. As shown, move and draw commands from the CPU memory interface are coupled to the micro-coded engine 70. Initial X-position information is sent to the X counter portion 210 of the frame buffer stage 200 over line 111, and initial Y-position information is sent to Y-position counter 205 over line 112. As stated before, the frame buffer stage 200 outputs to the display over lines 215.

The microcoded engine orchestrates the smooth line drawing task, along with performing miscellaneous other duties such as erasing the screen. It reads MOVE, DRAW, and SET LINE COLOR commands from a display list stored in the CPU's memory. On a SET LINE COLOR command, for example, it loads the new line color value into register 181 of the proportional weighting block 180, shown in FIGS. 2 and 8. On a MOVE command, the microcoded engine loads the new coordinates (starting position of the next line) into the X and Y counters 205 and 210 of the Frame Buffer 200. On a DRAW command, it performs setup operations including calculation of delta X (DX), delta Y (DY), slope, and octant values, and loading of registers inside the line smoothing block 80. These operations are defined in greater detail later.

The line smoothing section 80 is comprised of a digital differential analyzer stage 130, connected to micro-coded engine 70 via line 113, an anti-aliasing value generator 160 connected to analyzer stage 130 via line 154 and to the micro-coded engine 70 via line 114, and a proportional weighting stage 180. Generator 160 outputs alpha (.alpha.) value information on line 177 to the proportional weighting stage 180 and step control information on lines 178 to the X and Y counters 205,210 of the frame buffer (lines 178b and 178a respectively). Proportional weighting stage 180 is connected to the micro-coded engine by line 117 and has its output coupled to the frame buffer 200 via line 194.

In the operative scheme depicted in FIG. 2, in order to reconstruct a line in raster format, a digital differential analyzer (DDA) is utilized, in this case DDA unit 130. For each incremental step of the DDA along the large axis, small axis position information is generated for every pixel in the line. Because of the fixed location of the raster pixels, the equivalant line would have a jagged or stairstep structure in most orientations in the absence of a suitable and effective line smoothing or anti-aliasing capability. With the DDA 130 operating at a higher resolution than the raster screen resolution, the distance between the theoretical line and the individual pixel positions of relevant pixels can be resolved. This so-called small axis distance information associated to each relevant pixel, together with information in binary form representing the slope of the line to be recreated, can be utilized in generator 160 to generate a "gray scale" value to be assigned to each relevant pixel. The value generator is provided with the capability of assigning gray scale values to sets of pixels, each set comprising a single dimension array, when the array gives representative cross-section of the theoretical line for the incremental position of the DDA 130 regardless of the orientation of the line to be recreated relative to the horizontal (X) and vertical (Y) axes. The arrays of pixels thus comprising the center portion of the given line make the line appear to pass between screen pixels, with the result that the stair-step appearance is minimized.

In this way smoothing is accomplished perhaps 1000 times faster than in a pure software arrangement and during the building of the raster image itself, thus requiring no after-filtering. The use of the slope information in the generation of the gray scale values, on a pixel-by-pixel basis, enables effective minimization of changing line thickness appearances with different line orientations.

The unique arrangement of DDA 130 enables the calculation of small axis positions to n bits of fraction, for integral steps along the large axis, while using only a single clock cycle per step. As such it can be thought of as an advance over say Bresenham's DDA Algorithm (found in "Principles of Interactive Computer Graphics", by William Newman and Robert Sproull, Second Edition, pp. 25-27, McGraw-Hill, 1979) on a fractional pixel grid, which requires 2.sup.n cycles to move one pixel in X.

The pixel-by-pixel values generated by unit 160 for the fractional coverage of each pixel by the line being drawn, i.e. the alpha values, may be used to calculate new values for the display pixels via proportional weighting unit 180. The function of unit 180 is particularly effective in handling situations where lines cross and are sequentially drawn, and some intelligent balancing of intensities, and color for color systems, is desirable at the point of intersection. Where such a balancing function is considered dispensible, the alpha values from generator 160 can be input directly to the frame buffer stage.

The technique of proportional weighting in accordance with the present invention, involves utilization of the alpha value generated, the old or present pixel value as found in the frame buffer stage and the desired color for the line being drawn, at say the point of intersection with another line. For monochrome systems, this latter aspect is not considered. This technique is in contrast to present known systems and algorithms wherein the old pixel value is simply ignored, or is used in a maximum value operation with the alpha value times the line intensity. This maximum value operation is known only for a monochrome arrangement, wherein the effect is to write the new pixel only if it is larger than the old value. In the known prior arrangements, the average errors are greater than proportional weighting, as viewed against the ideal case.

Referring to FIG. 4, there is illustrated a hardware implementation of a digital differential analyzer in accordance with the invention for reconstructing a line in raster format. For ease of description, the generation of a line in the first octant (0 to 45 degrees) will be discussed here (where the X axis represents 0 degrees and the Y axis 90 degrees). The octants other than the first are obtainable through 90-degree rotations and reflections, as is demonstrated herein. Basically, with reference to FIGS. 2A and 2B, on lines of 45 degrees or less (i.e., first octant) from the horizontal (X axis), a set of three pixels in a vertical (small axis) array will be issued for every X (large axis) position of the processor along the center portion of the line. The gray scale (see FIG. 6) to be assigned to each individual pixel within each array is a function of the small axis distance from the actual line.

With reference to FIG. 2B, the true distance from pixel S is the small axis distance (in this case of a first octant line orientation, the Y-axis distance between the particular pixel position and the line to be drawn) times the cosine of the angle the line makes with the large (X)axis. Thus, with a first octant line orientation the small angle between the line and the horizontal is used, and the arrays of pixels will be vertical. If the line to be drawn was to have a second octant orientation, the angle to be used would be the small angle between the line and the vertical axis, and the array of pixels for each DDA increment will be horizontal.

The arrangement of FIG. 4 is designated for rapid smooth line ge