High Speed Method for Rendering Antialiased Vectors

The present invention relates generally to the field of computer graphics. More particularly, the present invention is related to scan conversion methods and corresponding apparatuses for rendering antialiased vectors in an interactive computer graphics system. Still more particularly, the present invention is related to a high speed scan conversion method that can be carried out by one processor or a plurality of parallel processors.

The field of computer graphics concerns the creation, storage, manipulation and display of pictures and models of objects by a digital processor. Interactive computer graphics is the subclass of computer graphics in which a user dynamically controls the picture's content, format, size or color on a display surface by means of an interaction device such as a keyboard, lever or joystick. See Fundamentals of Interactive Computer Graphics, by J. D. Foley and A. Van Dam, ISBN: 0-201-14468-9. The creation of synthetic images (i.e., images which exist as abstract collections of lines, points, curves, etc., in the computer's memory) is the usual domain of interactive computer graphics.

There are two primary classes of interactive computer graphics systems: random-scan and raster-scan systems. Images displayed by a random-scan system are encoded as commands to draw each output primitive (i.e., point, line or polygon) by plotting individual points or drawing connecting lines between specified starting and ending coordinates of line segments. Polygons are simply treated as a closed series of line segments. Encoding for a raster-scan system is much simpler: output primitives are broken up into their constituent points for display. The major difference between a simple point-plotting random-scan system and a raster-scan system is in the organization of the stored data used to drive the display. As explained below, the data is stored in a "frame buffer" (also called a "refresh buffer").

In the random-scan system, the component points of each successive output primitive are stored sequentially in memory and are plotted in that order, one point at a time. This is because the beam may be moved randomly on the screen. In the raster-scan system, the refresh memory is arranged as a 2-dimensional array of data. The value stored at a particular row and column encodes an intensity and/or color value of a corresponding display element on the screen. By convention, the location of each display element is specified by a unique (X,Y) coordinate.

Since each memory location defines a single point-sized element of an image, both the display screen location and its corresponding memory location are often called a "pixel," short for the image processing term "picture element." Hereinafter, to avoid confusion, we'll use the term "display pixel" to indicate picture elements of a display device, and "storage pixel" to indicate memory locations corresponding to the display pixels.

FIG. 1 is a simplified block diagram of a raster-scan graphic system 10. Such a system includes an image creation system 12, an image storage system 14 (such as a frame buffer), an image display system 16, a raster-scan display 18 and an interaction device 20. The image creation system 12 converts output primitives into the data stored in the frame buffer of the image storage system 14. The processing speed of the image creation system 12 establishes most of the characteristics of the raster-scan system 10. Moreover, the image creation system 12 is particularly malleable because it is typically implemented with a microprocessor. See Chapter 12 of Fundamentals of Interactive Computer Graphics, referenced above.

The overall speed with which all or part of the stored image data can be changed is dependent upon, among other things, how fast the image creation system executes instructions. It is the image creation system's execution of instructions which is often the slowest process in creating or changing an image. This is because the "scan conversion" algorithm (described below) typically requires many iterations. Usually, the faster the scan conversion algorithm, the faster the overall system response time to user commands. In addition, it is known that response time is critical to user satisfaction and, perhaps more importantly, to user productivity.

The process of converting a line, point, and area representation of an image to the array of pixel data in the image storage system 14 is called "scan conversion." Scan conversion algorithms are always needed in an interactive raster-scan graphics system, and are usually incorporated into the image creation system 12. The scan conversion algorithm used in a raster-scan graphics system will be invoked quite often, typically hundreds or even thousands of times, each time an image is created or modified. Hence, it must not only create visually pleasing images, but must also execute as rapidly as possible. Indeed speed versus image quality is the basic tradeoff in known scan conversion algorithms. Some scan conversion algorithms are fast and give jagged edges, while others are slower but give smoother edges. However, it can generally be said that faster is better for a given smoothness of image.

FIG. 2 depicts an exemplary line, y=mx+b, along with a vector 22 as it might be rendered (i.e., stored) in the frame buffer of the image storage system 14. Vector 22 is composed of a set of display pixels P.sub.0, P.sub.1, P.sub.2, . . . P.sub.N driven by a corresponding set of storage pixels in the image storage system 14. Vector 22 is rendered by stepping along the major axis, in this case the X-axis, and computing corresponding minor axis (Y-axis) ordinate values. These (X,Y) coordinates define the storage and display pixels composing the vector 22. The basic task in scan converting a line is to compute the integer coordinates of the display pixels lying nearest the line.

As can be seen from vector 22, the limited resolution of the frame buffer 14 and display device 18 causes the vector to become jagged, or "aliased." Techniques for generating antialiased (i.e., smooth) vectors are known in the art. See, for example, Chapter 11.2.3 of Fundamentals of Interactive Computer Graphics, referenced above, and references cited therein for details of known antialiasing techniques. These known antialiasing techniques are too slow for many applications however, although they may produce visually acceptable images.

FIGS. 3(a) and 3(c) depict two sets of vectors. The end point description of the set shown in FIG. 3(a) is a simple horizontal translation of the end point description of the set shown in FIG. 3(c). Both sets of vectors have a slope of 1/200. The vectors of FIG. 3(a) have been filtered, i.e., are antialiased, while the vectors of FIG. 3(c) are aliased.

The spatial aliasing shown by the unfiltered set of vectors in FIG. 3(c) is not the only aliasing problem in computer generated graphics. Another aliasing problem is shown in FIGS. 3(b) and 3(d). The vectors shown in FIG. 3(b) are the same as those in FIG. 3(a), and the vectors shown in FIG. 3(d) are the same as those shown in FIG. 3(c), with the exception that the vectors shown in FIGS. 3(b) and 3(d) have been translated vertically by one-half of a pixel. If these two sets of aliased and antialiased vectors are displayed as part of a real time series, then the antialiased vectors would have the correct apparent motion; that is, the antialiased vectors would appear to be slowly moving up. On the other hand, the aliased vectors would appear to be moving quickly in the horizontal direction. The arrow in FIG. 3(d) points to a step in the displayed pixels. This step is noticeably offset from the equivalent step in FIG. 3(c). It is the motion of these steps that dominate the apparent motion of the unfiltered vectors in the real time series. In other words, the image on the right would appear to moving at the wrong speed in the wrong direction. This artifact is called "aliasing-induced motion." A viewer sees a combination of all aliasing artifacts, including those due to both spatial aliasing and aliasing-induced motion. As pixel rendering speed increases and the goal of real-time generation of images is approached, aliasing-induced motion becomes greater and the total aliasing problem becomes more troublesome. See A. C. Barkans, "High Speed High Quality Antialiased Vector Generation," Computer Graphics, Vol. 24, Number 4, August 1990, which is incorporated herein by reference.

Users of interactive graphics systems now expect vector generation to be fast enough to support the real time display of user-controlled complex images. This has unfortunately aggravated the aliasing problem since aliasing-induced motion is added to the formerly dominant static spatial aliasing.

Accordingly, an object of the present invention is to provide an efficient and rapid method and apparatus for rendering antialiased vectors. A further object of the present invention is to provide a high speed method for rendering antialiased vectors that can be carried out by a number of processors running in parallel. The present invention achieves these goals.

According to the invention, a scan conversion method for rendering an antialiased vector in a multi-processor graphics system comprises the following steps.

First, signals are provided to the processors indicative of display areas for which the respective processors are responsible. Next, a first set of storage pixels to be rendered by the processors is determined. Next, each storage pixel of the first set is rendered simultaneously, each by a different processor. Finally, a second set of storage pixels to be rendered is determined, and each pixel of the second set of storage pixels is rendered substantially simultaneously by a different one of the processors. The determinations of the first and second sets of storage pixels are made in accordance with the signals. Each pixel in a given set of pixels corresponds either to different minor axis steps along a given major axis step (for Y-major vectors) or to different major axis steps along a given minor axis step (for X-major vectors), depending upon whether the major axis is the X or Y axis.

In a second embodiment, an apparatus is provided for carrying out the above method steps.

In a third embodiment, a multi-processor computer graphics system is provided. The system comprises an image creation system, a frame buffer comprising storage pixels for storing pixel data rendered by the image creation system, and a raster-scan display for displaying pixel data stored in the frame buffer. The image creation system comprises a plurality of parallel processors for rendering the vector; means for providing signals to each of the processors indicative of display areas the respective processors are responsible for; means for determining in accordance with the signals a first set of storage pixels to be rendered by the processors, and for rendering each pixel of the first set simultaneously by a different one of the processors; and means for determining in accordance with the signals a second set of storage pixels to be rendered by the processors, and for rendering each of the second set of pixels simultaneously by a different one of the processors.

Where the vector's major axis is along the X-axis, each of the pixels in the first set corresponds to a single major axis step. Where the vector's major axis is along the Y-axis, each of the pixels in the first set corresponds to a different major axis step.

FIG. 1 is a block diagram of a known basic raster-scan graphics system.

FIG. 2 is a simplified representation of an aliased vector.

FIGS. 3(a) and 3(c) depict a set of antialiased vectors and a corresponding set of aliased vectors, respectively. FIGS. 3(b) and 3(d), depict the same sets of antialiased and aliased vectors depicted in FIGS. 3(a) and 3(c), but shifted up one-half pixel.

FIG. 4(b) is a simplified representation of an antialiased vector rendered in accordance with the present invention.

FIG. 4(a) is a block diagram of a multi-processor raster-scan graphics system in accordance with the present invention.

FIG. 5 depicts alternative positions of a first rendered pixel for a major axis step, in accordance with the present invention.

FIGS. 6(a)-5(c) are a flowchart of a scan conversion method in accordance with the present invention.

The preferred embodiments will now be described with reference to the drawings, wherein like numerals designate like elements or steps.

FIG. 4(a) depicts a multi-processor graphics system in accordance with the present invention. The only difference between the block diagrams of FIGS. 1 and 4(a) is that the image creation system 12 of FIG. 4(a) includes a plurality of pixel processors 12A through 12D. In a preferred embodiment, processors 12A-12D are each a Color Texture Interpolator, part no. IFY5-0001, manufactured by Hewlett Packard Co., Palo Alto, Cali. As described below, the present invention provides an efficient algorithm for rendering antialiased vectors. Moreover, the algorithm is particularly adapted to be carried out by multiple processors operating in parallel.

FIG. 4(b) depicts an antialiased vector 24 corresponding to the line y=mx+b from the point (X.sub.0 =0, Y.sub.0 =0) to the point (X.sub.1 =20, Y.sub.1 =10). This is the same line represented in FIG. 2 by the aliased vector 22. The antialiased vector 24 is preferably composed of three pixels for each major axis step. Vector 24 has a major axis in the horizontal (X) direction and a minor axis in the vertical (Y) direction. Vector 24 is rendered at each major axis step, beginning at the first major axis step X.sub.0, by rendering groups of three pixels along the minor axis. The Y ordinate of the middle pixel in each group of three pixels corresponds as nearly as possible to the line y=mx+b. As with the aliased vector 22 discussed above, there will still be some error due to the limited number of storage pixels in the frame buffer and the limited number of display pixels.

According to the invention, the smoother appearance of antialiased vector 24 is achieved by tapering the intensity distribution of the display pixels along the vector minor axis (Y-axis). For example, one such scheme is to assign all pixels centered exactly on the line y=mx+b (e.g., P.sub.1, P.sub.30) a peak intensity, and assign its neighboring pixels along the minor axis an intensity less than the peak intensity. A set of pixels centered below (above) the line (e.g., P.sub.8, P.sub.9, P.sub.10) is assigned an intensity distribution weighted more heavily above (below) the line. There are many possible intensity distribution functions that would achieve a satisfactory result, however the Hamming function (a modification of the Sinc function (sinX/X)) is most preferred.

Antialiased vector 24 is preferably rendered by first rendering pixel P.sub.1, then P.sub.2, then P.sub.34, then P.sub.4 and so on, in the order shown. Note that, at each new major axis step, the rendering order along the minor axis changes direction. For example, at the first major axis step, P.sub.1 and P.sub.2 are rendered in the positive minor axis direction, while at the second major axis step P.sub.3 and P.sub.4 are rendered in the negative minor axis direction.

In order to take full advantage of modern VLSI parallel processing technology, a parallel processor algorithm for vector generation was developed. The algorithm efficiently matches a hardware implementation with an image space sub-division. The algorithm provided by the present invention (the Barkans algorithm) may be contrasted with the well known Bresenham algorithm (see, Bresenham, J. "Algorithm For Computer Control Of A Digital Plotter," IBM Systems Journal 4(1) July 1965) for single processor systems, which automatically step along the major axis and check whether the minor axis should be adjusted. Unlike the situation in single processor systems, the efficient use of multiple processors requires that while each pixel is being processed the position of the next pixel for each processor be determined by that processor. This decouples the processors so that they can proceed independently. Since this is a more complex algorithm, it requires more logic than the Bresenham algorithms. The additional logic circuitry required is relatively inexpensive, given modern VLSI technology.

Before presenting the details of the algorithm, the required state information will be described. The state information may be provided by an external source (e.g., a host processor) and/or the data sent to describe each individual vector. The embodiment described below supports one, two or four processors with an image space subdivision along scan lines; however the invention is not limited to systems with any particular number of processors or to image space subdivision along scan lines.

The signals S0-S3 tell a processor which of the scan lines, 0-3 (MOD 4), it "owns", i.e., is responsible for. Note that the scan lines identified by the signals S0-S3 may be either screen relative or window relative.

In addition to the S0-S3 signals, three configuration bits are used to produce a set of logical signals. These signals are called 4.sub.-- PP, 2.sub.-- PP and STEP.sub.-- CONTROL. 4.sub.-- PP is asserted if the current processor owns one of every four scan lines in a four processor configuration. 2.sub.-- PP is asserted if the processor is part of a two processor configuration. STEP.sub.-- CONTROL is asserted if the current processor is part of a one or two processor configuration.

The signal Y.sub.-- MAJOR is asserted if the major axis of the vector being rendered is the Y-axis, and not asserted if X is the major axis.

The SERP signal causes the vector to be rendered in serpentine mode. Serpentine mode is a way to specify the output order of the pixels. (This serpentine mode is distinguished from the serpentine rendering of antialiased vectors, discussed above, whereby a number of pixels are sequentially rendered along the minor axis for each major axis step.) If the pixels along one scan line are output with incrementing x values, then the pixels for the adjunct scan line are output by decrementing the x values. This ordering is done to improve locality (i.e., reduce the number of addresses required to be sent to the frame buffer) and thus increase throughput into the frame buffer. The SERP signal is initially set to the value of the sign bit of the vector's slope, and is thereafter toggled at each major axis step.

The MAJ.sub.-- DEC signal is asserted if the major axis should be decremented for each major axis step.

If the AA.sub.-- MODE signal is asserted, an antialiased vector is rendered. If AA.sub.-- MODE is not asserted, an aliased vector will be rendered.

The MIN.sub.-- 1 and MIN.sub.-- 0 signals represent the least significant bits of the minor axis position. These are used by a processor to determine the location of the pixels it is responsible for.

Two signals, MAJ.sub.-- 1 and MAJ.sub.-- 0, are the least significant bits of the major axis position. These are used by a processor to determine the location of the pixels it is responsible for.

FIG. 5 shows the positions where the pixels for a major axis step may be located. The grid represents pixel locations on a CRT display. Note that the image space is subdivided along scan lines such that in a four processor system each processor is responsible for every fourth scan line. The figure assumes that the current major and minor axis values point to the pixel location shown as "1". For an aliased vector only, pixel 1 is rendered at the current major axis step. A Y-major antialiased vector requires that the processor responsible for scan line N render the pixels designated 3, 1 and 5. An X-major antialiased vector requires the pixels designated 2, 1 and 4 be rendered. In a four processor system a different processor renders each of three pixels required for the major axis step of the X-major antialiased vector (this assumes that the antialiased vector comprises three pixels for each major axis step, which is most preferred).

The selection of which pixel to render first is based on the following criteria:

The pixel at location 1 would be the first pixel rendered if:

1. The mode is aliased and the processor owns scan line N; or

2. if the mode is antialiased, the vector is X-major, it is a two or four processor system, and the processor owns scan line N.

The pixel at location 2 would be the first pixel rendered if the mode is antialiased, the vector is X-major, and the processor owns scan line (N+1). The SERP signal must also be asserted unless the processor is part of a four processor system, in which case the SERP signal may be ignored.

Pixels at location 3 or 5 would be rendered first if the mode is antialiased, the vector is Y-major and the processor owns scan line N. The choice of which pixel, 3 or 5, to render first depends on the state of the SERP signal.

The last possible case is that no pixel is rendered for the current major axis step. This would occur if:

1. A pixel on scan line N that is part of an aliased X-major vector is evaluated by a processor that does not own scan line N;

2. a Y-major vector is being rendered and the current major axis location is not on a scan line owned by the processor; or

3. an antialiased X-major vector is being rendered by a system with four processors and the processor of interest owns scan line (N+2). Note that in a four processor system the processor that owns scan line (N+2) does not own another scan line until line (N-2) or (N+6).

Thus, it can be seen that at each major axis step a determination must be made whether the minor axis value of the first pixel rendered should be incremented, decremented, or held. From FIG. 5 it can be seen that positions 2 and 5 are increments along the minor axis, and positions 3 and 4 are decrements along the minor axis. To stay at position 1 the minor axis is held.

Using the given state information, a set of Boolean expressions for the signals "Increment", "Decrement" and "Hold" can be derived. For example, the Boolean expression for Increment may be written as follows: ##EQU1## The equations for "Decrement" and "Hold" can be derived in a similar fashion. See A. C. Barkans, "High Speed High Quality Antialiased Vector Generation," referenced above.

After determining the position of the first pixel to render, a determination must be made whether there are other pixels to render along the minor axis. If the vector is Y-major and Increment or Decrement are true, then there are more pixels to render along the minor axis. Referring to FIG. 5, this condition implies that a pixel at position 3 or 5 was rendered first. In that case, the other two pixels must be rendered along the scan line. The other case where there are more pixels along the minor axis is when an X-major vector is rendered and the processor is part of a one or two processor system and the first pixel required an increment or decrement.

A Boolean expression may be written for Minor.sub.-- Step as follows:

Pseudo code describing the preferred embodiment of the algorithm is shown below. Note that this embodiment will work for one-, two- and four-processor systems. In addition, note that the symbols "*" and "+" represent the logical operations "AND" and "OR", respectively; and that steps enclosed within brackets "{ }" are performed within a single clock cycle. The ability of a given processor to perform a number of steps within a single clock cycle is important to the overall speed with which the algorithm can be carried out. The circuitry for achieving this parallelism within a processor will be apparent to those skilled in the art. See, A. C. Barkans, "High Speed High Quality Antialiased Vector Generation," referenced above; W. Newman and R. Sproull, Principles of Interactive Computer Graphics, p. 24, 2nd ed. McGraw-Hill, New York, 1979.

There are several points to note about this algorithm:

First, if aliased vectors are being rendered, then the signals Increment, Decrement and Minor.sub.-- Step cannot be asserted. In the aliased case the "while" loop becomes very much like the inner loop of a DDA algorithm, with one noticeable exception: in a multi-processor configuration the Hold signal will only be asserted when the processor owns the scan line.

In addition, in a four processor configuration with Y-major antialiased vectors, the major axis will be stepped ahead while rendering across the minor axis. The result is that in three clock cycles three minor axis pixels will be rendered and the major axis stepped ahead to the next scan line the respective processor is responsible for.

Finally, in a four processor configuration with X-major antialiased vectors, the Increment, Decrement and Hold signals will make the processor render the correct minor axis pixel on the first clock. The Minor.sub.-- Step signal will not be asserted. The combined processing of the four processors will result in one major axis step rendered in every clock cycle. Aliased vectors also require one clock cycle to step a major axis step. See A. C. Barkans, "High Speed High Quality Antialiased Vector Generation," referenced above, for additional points regarding the above algorithm.

Referring now to FIGS. 6(a)-6(c), a flowchart of the above scan conversion algorithm is depicted. The preferred embodiment of the algorithm includes the step of first determining the state variables discussed above and represented by the signals listed in block 28.

Next, a check is made of whether "major.sub.-- count" is greater than or equal to zero, block 30. If less than zero, the algorithm is ended, block 62. If major.sub.-- count is greater than or equal to zero, the next pixel value is moved into a register called the "current" register, block 32.

Next, a check is made of whether Increment, Decrement, or Hold are true, block 34. If any one of them is true, the first pixel is written to the frame buffer, block 36. If none of them are true, or after rendering the first pixel, the "shadow register" is adjusted to the next major axis location, block 38. Note that the "shadow register" and "current register" are coupled together in series in a pipelined implementation of the invention. These registers allow the respective processors to "look ahead," and compute a next pixel location while current pixel is being rendered.

Next, major.sub.-- count is decremented by 1, block 40. Next, minor.sub.-- step is checked to determine whether it is true, block 42. If not true, the algorithm loops back to block 30. If true, a check is made of whether Y.sub.-- major *2.sub.-- PP is true, block 44. If not true, the second pixel along the minor axis is written, block 46.

Next Y.sub.-- major*(4.sub.-- PP+2.sub.-- PP) is tested, block 48. If true, the shadow register is set to the next major axis location, block 50, and major.sub.-- count is decremented by 1, block 52.

Next, the third pixel value is written to the frame buffer, block 54. Next, Y.sub.-- major*4.sub.-- PP is tested, block 56. If Y.sub.-- major*4.sub.-- PP is not true, the algorithm loops back to block 30. If Y.sub.-- major*4.sub.-- PP is true, the shadow register is adjusted to the next major axis location, block 58. Finally, major.sub.-- count is decremented by 1, block 60, and the algorithm loops back to block 30.

Note that although the flowchart and corresponding description reflect the parallelism between processors, they may fail to bring out that many of the steps may also be performed in parallel by the individual processors. The degree of parallelism within a processor is dependent upon the particular circuitry employed to carry out the algorithm, which circuitry is subject to an infinite variety of variations and modifications.

As a final point, it is noted that many other variations and modifications of the method and apparatus described above will be apparent to those skilled in the art. For example, the specific number of pixels for each major axis step, and the particular antialiasing filter employed may vary from the preferred embodiments described above without departing from the scope of the invention. Accordingly, the invention is intended to be limited only by the following claims.