System and method for drawing antialiased polygons

• US 5,287,438 A
• Filed: 08/13/1992
• Issued: 02/15/1994
• Est. Priority Date: 11/17/1989
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Kelleher, Brian M.
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US07/929,845
• Time in Patent Office: 551 Days
• Field of Search: 340/728, 340/729, 340/747, 340/750, 358/903, 382/33, 382/36, 382/52, 382/56, 395/129, 395/128, 395/131, 395/132, 395/140, 395/142, 395/143
• US Class Current: 345/613
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture
• CPC Class Codes: G06T 15/503 Blending, e.g. for anti-aliasing

Abstract

A system (30) draws antialiased polygons. A CPU (32) is connected to a floating point processor (FPU) (34) by bus (36). The CPU (32) is connected by a 32-bit system bus (38) to a random access memory (RAM) (40), a cache (42) and an interface (44) in graphics subsystem (45). The interface (44) is connected by bus (46) to graphics processor (48). The graphics processor (48) is connected by 120-bit graphics bus (50) to frame buffer (52). The frame buffer (52) is connected to a video digital to analog converter (DAC) (54) by bus (56). The DAC (54) is connected to video display (58) by line (60). The graphics processor (48) use a technique known as super-sampling to combat the effects of aliasing. In aliased mode, the graphics processor (48) use 16 array sites to sample 16 pixels (72). When drawing a polygon or line in antialiased mode, the graphics processor (48) uses the 16 sites to sample at 16 locations (120) within a single pixel (72). The antialiasing is done by determining what proportion of the locations (120) within each pixel (72) are within the polygon and setting a color of each pixel (72) on the basis of the proportion.

Claims

1. A system for drawing antialiased polygons, which comprises a host data processor, a memory connected to said host data processor by a bus, a graphics processor connected to said bus, a display including a plurality of pixels for displaying the polygons, and a frame buffer connected between said graphics processor and said display, said graphics processor including a program for calculating values of an image array, said image array being selectively reconfigurable by said program to comprise either a plurality of the pixels or a plurality of subpixels within one of the pixels, lines of the polygons being determinable with said program by dividing a plane of the display surface into geometric half spaces with the lines and categorizing the half spaces by which side of the lines on which the half spaces are located, said graphics processor comprising a plurality of array registers and a plurality of comparators, each of said plurality of array registers being connected to one of said plurality of comparators, said registers and comparators for storing and comparing said values calculated by said program to determine in which said half space said pixels or subpixels in said image array reside.

2. The system for drawing antialiased polygons of claim 1 in which said image array is scannable by said program to draw the polygons by moving from a first location at a first line of the polygons in a first direction until encountering a second line of the polygon, in a second direction along the the first line, then in the first direction until encountering the second line, repeating until encountering a third line of the polygons.

3. The system for drawing antialiased polygons of claim 1 in which the pixels of the display are determinable with said program as inside the polygons by logically combining the categorization of the side of the lines on which the half spaces are located.

4. The system for drawing antialiased polygons of claim 3 in which the lines of the polygons are determinable with said program by evaluating a linear equation equivalent to:

space="preserve" listing-type="equation">y=dy/dx x+y1-dy/dx x1,

where x and y are coordinates on an x-axis and a y-axis, respectively, x1 and y1 are incremental values from the coordinates x and y, respectively and dx/dy is the derivative of x with respect to y, respectively representing a rate of change in values of x as values of y change, said derivative dx/dy representing a constant for said linear equation.

5. The system for drawing antialiased polygons of claim 4 in which the linear equation is evaluatable with said program by determining the relationship:

space="preserve" listing-type="equation">dx (offsety)-dy (offsetx),

where, y offsetx, offsety are a pixel or subpixel'"'"'s offset from an origin of said image array and dx (offsety) and dy (offsetx) are the derivatives of x (offsety) and y (offsetx).

6. The system for drawing antialiased polygons of claim 1 in which the polygons are antialiasable with said program by determining what proportion of the subpixels within each pixel are within the polygons and setting a color of each pixel on the basis of the proportion.

9. The system for drawing antialiased polygons of claim 6 in which the polygons having a common edge are antialiasable with said program along the common edge by treating the pixels along the common edge in each polygon having the common edge as partially covered by the other polygon and blending the colors of the pixels along the common edge on the basis of extent of the partial coverage.

10. The system for drawing antialiased polygons of claim 9 in which the polygons are triangles and the colors of the pixels along the common edge are blended by using a relationship equivalent to:

space="preserve" listing-type="equation">i.sub.new =i.sub.fb +MIN(1-α

.sub.fb, α

.sub.tri) i.sub.tri

space="preserve" listing-type="equation">α

.sub.new =α

.sub.fb +MIN(1-α

.sub.fb, α

.sub.tri)

where

α

_fb =current α

value in the frame buffer

i_fb =current intensity value in the frame buffer

α

_tri =α

value from new triangle (based on number of subpixels inside triangle)

i_tri =intensity value from new triangle

α

_new =α

value to be put into the frame buffer

i_new =intensity value to be put into the frame buffer.

7. A system for drawing antialiased polygons, which comprises a host data processor, a memory connected to said host data processor by a bus, a graphics processor connected to said bus, a display including a plurality of pixels for displaying the polygons, and a frame buffer connected between said graphics processor and said display, said graphics processor including a program for calculating values of an image array, said image array being selectively reconfigurable by said program to comprise either a plurality of the pixels or a plurality of subpixels within one of the pixels, lines of the polygons being determinable with said program by dividing a plane of the display surface into geometric half spaces with the lines and categorizing the half spaces by which side of the lines on which the half spaces are located by logically combining the categorization of the side of the lines on which the half spaces are located, the lines of the polygons being determinable with said program by evaluating a linear equation equivalent to:

space="preserve" listing-type="equation">y=dy/dx x+y1-dy/dx x1,

where x and y are coordinates on an x-axis and a y-axis, respectively, x1 and y1 are incremental values from the coordinates x and y, respectively and dx/dy is the derivative of x with respect to y, respectively representing a rate of change in values of x as values of y change, said derivative dx/dy representing a constant for said linear equation, said linear equation being evaluatable with said program by determining the relationship;

space="preserve" listing-type="equation">dx (offsety)-dy (offsetx),

where offsetx, offsety are a pixel or subpixel'"'"'s offset from an origin of said image array and dx (offsety) and dy (offsetx) are the derivatives of x (offsety) and y (offsetx), said graphics processor comprising a plurality of array registers and a plurality of comparators, each of said plurality of array registers being connected to one of said plurality of comparators, said registers and comparators for storing and comparing said values calculated by said program to determine in which said half space said pixels or subpixels in said image array reside.

8. The system for drawing antialiased polygons of claim 7 in which said plurality of array registers are arranged in sets, with one set for each line of the polygons, each register of each set producing an output from one of said comparators, the outputs being combined to determine whether the pixels are inside the polygons.

11. In a system for drawing antialiased polygons having a graphics processor including a program for calculating values of an image array, the improvement comprising said image array being selectively reconfigurable for sampling by said program to comprise either a plurality of the pixels or a plurality of subpixels within one of the pixels, lines of the polygons being determinable with said program by dividing a plane of the display surface into geometric half spaces with the lines and categorizing the half spaces by which side of the lines on which the half spaces are located, said graphics processor comprising a plurality of array registers and a plurality of comparators, each of said plurality of array registers being connected to one of said plurality of comparators, said registers and comparators for storing and comparing said values calculated by said program to determine in which said half space said pixels or subpixels in said image array reside.

12. The system for drawing antialiased polygons of claim 11 in which the polygons are antialiasable with said program by determining what proportion of the subpixels within each pixel are within the polygons and setting a color of each pixel on the basis of the proportion.

13. The system for drawing antialiased polygons of claim 12 in which the polygons having a common edge are antialiasable with said program along the common edge by treating the pixels along the common edge in each polygon having the common edge as partially covered by the other polygon and blending the colors of the pixels along the common edge on the basis of extent of the partial coverage.

14. The system for drawing antialiased polygons of claim 13 in which the polygons are triangles and the colors of the pixels along the common edge are blended by using a relationship equivalent to:

space="preserve" listing-type="equation">i.sub.new =i.sub.fb +MIN(1-α

.sub.fb, α

.sub.tri) i.sub.tri

space="preserve" listing-type="equation">α

.sub.new =α

.sub.fb +MIN(1-α

.sub.fb, α

.sub.tri)

where

α

_fb =current α

value in the frame buffer

i_fb =current intensity value in the frame buffer

α

_tri =α

value from new triangle (based on number of subpixels inside triangle)

i_tri =intensity value from new triangle

α

_new =α

value to be put into the frame buffer

i_new =intensity value to be put into the frame buffer.

15. In a system for drawing antialiased polygons having a graphics processor including a program for calculating values of an image array, the improvement comprising said image array being selectively reconfigurable by said program to comprise either a plurality of the pixels or a plurality of subpixels within one of the pixels, said graphics processor comprising a plurality of array registers and a plurality of comparators, each of said plurality of array registers being connected to one of said plurality of comparators, said registers and comparators for storing and comparing said values calculated by said program to determine whether said pixels or subpixels in said image array are inside the polygons.

16. The system for drawing antialiased polygons of claim 15 in which said plurality of array registers are arranged in sets, with one set for each line of the polygons, each register of each set producing an output from one of said comparators, the outputs being combined to determine whether the pixels are inside the polygons.

17. A method for drawing antialiased polygons, comprising the steps of providing a graphics processor including a program for calculating values of an image array, said graphics processor being provided as a plurality of array registers and a plurality of comparators, each of said plurality of array registers being connected to one of said plurality of comparators, said registers and comparators for storing and comparing said values calculated by said program, selectively configuring the image array with the program to comprise either a plurality of pixels or a plurality of subpixels within one of the pixels, calculating values of the image array as configured, antialiasing the polygons, and determining lines of the polygons with said program by dividing a plane of a display surface into geometric half spaces with the lines, categorizing the half spaces by which side of the lines on which the half spaces are located, and updating the pixels or subpixels in the image array with the program in parallel.

18. The method for drawing antialiased polygons of claim 17 further comprising scanning the image array with the program to draw the polygons by moving from a first location at a first line of the polygons in a first direction until encountering a second line of the polygons, in a second direction along the the first line, then in the first direction until encountering the second line, and repeating until encountering a third line of the polygons.

19. The method for drawing antialiased polygons of claim 17 further comprising the step of determining with the program whether the pixels of the display are inside the polygons by logically combining the categorization of the side of the lines on which the half spaces are located.

20. The method for drawing antialiased polygons of claim 19 in which the lines of the polygon are determined with the program by evaluating a linear equation equivalent to:

space="preserve" listing-type="equation">y=dy/dx x+y 1-dy/dx x1,

where x and y are coordinates on an x-axis and a y-axis, respectively, x1 and y1 are incremental values from the coordinates x and y, respectively and dx/dy is the derivative of x with respect to y, respectively representing a rate of change in values of x as values of y change, said derivative dx/dy representing a constant for said linear equation.

21. The method for drawing antialiased polygons of claim 20 in which the linear equation is evaluated with the program by determining the relationship:

space="preserve" listing-type="equation">dx (offset)-dy (offsetx),

where offsetx, offsety are a pixel or subpixel'"'"'s offset from an origin of the image array and dx (offsety) and dy (offsetx) are the derivatives of x (offsety) and y (offsetx).

22. The method for drawing antialiased polygons of claim 17 in which the polygons are antialiased with the program by determining what proportion of the subpixels within each pixel are within the polygons and setting a color of each pixel on the basis of the proportion.

23. The method for drawing antialiased polygons of claim 22 in which the polygons having a common edge are antialiased with the program along the common edge by treating the pixels along the common edge in each polygon having the common edge as partially covered by the other polygon and blending the colors of the pixels along the common edge on the basis of extent of the partial coverage.

24. The method for drawing antialiased polygons of claim 23 in which the polygons are triangles and the colors of the pixels along the common edge are blended by using a relationship equivalent to:

space="preserve" listing-type="equation">i.sub.new =i.sub.fb +MIN(1-α

.sub.fb, α

.sub.tri) i.sub.tri

space="preserve" listing-type="equation">α

.sub.new =α

.sub.fb +MIN(1-α

.sub.fb, α

.sub.tri)

where

α

_fb =current α

value in the frame buffer

i_fb =current intensity value in the frame buffer

α

_tri =α

value from new triangle (based on number of subpixels inside triangle)

i_tri =intensity value from new triangle

α

_new =α

value to be put into the frame buffer

i_new =intensity value to be put into the frame buffer.