Computer graphics priority system with antialiasing

• US 4,918,626 A
• Filed: 12/09/1987
• Issued: 04/17/1990
• Est. Priority Date: 12/09/1987
• Status: Expired due to Term

• Current Assignee: Evans & Sutherland Computer Corp. (Elevate Entertainment, Inc.)
• Original Assignee: Evans & Sutherland Computer Corp. (Elevate Entertainment, Inc.)
• Inventors: Brown, Russell A., Watkins, Gary S., Eckart, Glen A.
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): Bayerl, Raymond J.
• Application Number:
  US07/130,811
• Time in Patent Office: 860 Days
• Field of Search: 340/729, 340/728, 340/747, 358/903, 364/522, 364/518, 364/521, 382/52, 382/33, 382/36, 382/41, 382/56
• US Class Current: 345/421
• CPC Class Codes: G06T 15/40 Hidden part removal
• CPC Class Codes: G06T 15/503 Blending, e.g. for anti-aliasing

Abstract

Image data is composed from primitives (polygons) to attain data for displays with the removal of hidden surfaces and smooth-appearing edges. Defined polygons are tested for priority in a determined field of vision by scan conversion to specify individual picture elements (pixels). Polygon contention for pixels is resolved by determining the edge of intersection between the planes of such polygons and testing the signs of certain values in accordance with predetermined criteria. Subpixel priority is treated for similar resolution to provide improved antialiased images.

Claims

1. A process for resolving priority at specific locations of designated coordinate values of x and y for a graphics display between a first primitive P₁ defined in conventional three-dimensional space in a plane a₁ x+b₁ y+c₁ z+d₁ =0 and a second primitive P₂ similarly defined in a plane a₂ x+b₂ y+c₂ z+d₂ =0, said planes potentially although not necessarily intersecting along a projected line of intersection in said display, comprising the steps of:

defining said projected line of intersection by determining the values of (c₂ a₁ -c₁ a₂), (c₂ b₁ -c₁ b₂) and (c₂ d₁ -c₁ d₂);

storing the determined values (c₂ a₁ -c₁ a₂), (c₂ b₁ -c₁ b₂) and (c₂ d₁ -c₁ d₂);

storing picture element data to define elemental areas of said graphics display;

resolving priority for said elemental areas in sequence as between said primitives for said display to determine precedence in favor of one of said primitives P₁ or P₂ under control of c₁, c₂, and one or more of (c₂ a₁ -c₁ a₂), (c₂ b₁ -c₁ b₂) and (c₂ d₁ -c₁ d₂); and

storing display data of said one primitive for said elemental areas to provide electrical signals for the graphics display.

2. A process according to claim 1 including the further step of resolving said line of intersection existing between said primitives as more horizontal or more vertical as by determining the relative magnitudes of (c₂ a₁ -c₁ a₂) and (c₂ b₁ -c₁ b₂), and further resolving said priority under control of whether said line is either more horizontal or more vertical.

3. A process according to claim 2 wherein priority is resolved in favor of said first primitive to one side of said more vertical line, and priority is resolved in favor of said second primitive to the other side of said more vertical line, under control of c₁, c₂ and (c₂ a₁ -c₁ a₂).

4. A process according to claim 2 wherein priority is resolved in favor of said first primitive to one side of said more vertical line, and priority is resolved in favor of said second primitive to the other side of said more vertical line, under control of the signs of c₁, c₂ and (c₂ a₁ -c₁ a₂).

5. A process according to claim 2 wherein priority is resolved in favor of said first primitive to one side of said more horizontal line, and priority is resolved in favor of said second primitive to the other side of said more horizontal line, under control of c₁, c₂ and (c₂ b₁ -c₁ b₂).

6. A process according to claim 2 wherein priority is resolved in favor of said first primitive to one side of said more horizontal line, and priority is resolved in favor of said second primitive to the other side of said more horizontal line, under control of the signs of c₁, c₂ and (c₂ b₁ -c₁ b₂).

7. A process according to claim 1 wherein said priority is further resolved by determining the absence of an intersecting line between said planes.

8. A process according to claim 7 wherein said priority is resolved in favor of one of said primitives under control of c₁, c₂ and (c₂ d₁ -c₁ d₂).

9. A process according to claim 7 wherein said priority is resolved in favor of one of said primitives under control of the signs of c₁, c₂ and (c₂ d₁ -c₁ d₂).

10. A process according to claim 7 wherein determination of said absence of an intersecting line between planes is controlled by the determined magnitudes of (c₂ a₁ -c₁ a₂) and (c₂ b₁ -c₁ b₂).

11. A process according to claim 1 wherein said designated x and y values indicate subpixels for said display and said process further includes a step of computing composites for pixels in accordance with priorities determined for said subpixels.

12. A hidden surface elimination system for resolving priority as between primitives for a computer graphics image display with respect to picture element areas, the primitives P₁, P₂ and so on being defined in planes, a₁ x+b₁ y+c₁ z+d₁ =0;

a₂ x+b₂ y+c₂ z+d₂ =0 and so on, the hidden surface elimination system comprising;

means for receiving primitive data to specify components for a computer graphics display in the form of said primitives P₁ and P₂ and so on;

structure for sequencing said picture element areas to be occupied by said primitives P₁ and P₂ as specified by the received primitive data to identify primitives contending for a picture element area;

structure for resolving priority between primitives P₁ and P₂ contending for a pixel area, by determining the values (c₂ a₁ -c₁ a₂), (c₂ b₁ -c₁ b₂) and (c₂ d₁ -c₁ d₂) and logically analyzing the signs of certain of the values to select one of said contending primitives P1 or P2 for the picture element area; and

cache memory means for receiving the determined values (c₂ a₁ -c₁ a₂), (c₂ b₁ -c₁ b₂) and (c₂ d₁ -c₁ d₂) and means for identifying said values for use on occurrence of another pixel with contention between the primitives P₁ and P₂.

13. A hidden surface elimination system for resolving priority as between primitives for a computer graphics image display with respect to picture element areas, the primitives P₁, P₂ and so on being defined in planes, a₁ x+b₁ y+c₁ z+d₁ =0;

a₂ x+b₂ y+c₂ z+d₂ =0 and so on, the hidden surface elimination system comprising;

means for receiving primitive data to specify components for a computer graphics display in the form of said primitives P₁ and P₂ and so on;

structure for sequencing said picture element areas to be occupied by said primitives P₁ and P₂ as specified by the received primitive data to identify primitives contending for a picture element area, said structure for sequencing comprising a raster converter for scan converting said primitives; and

memory means for receiving the determined values (c₂ a₁ -c₁ a₂), (c₂ b₁ -c₁ b₂) and (c₂ d₁ -c₁ d₂) and means for identifying said values for use on occurrence of another pixel with contention between the primitives P₁ and P₂.

14. A system according to claim 13 comprising a plurality of said structures for resolving priority and further including means for coupling said plurality of structures to process said received primitive data and further including means for accessing said memory means by each of said structures.

15. A system according to claim 13 wherein said memory means further includes a polygon memory for storing primitive data and a mask memory for storing picture element data.

16. A system according to claim 15 wherein said mask memory stores subpixel data.

17. A hidden surface elimination system for resolving priority as between primitives for a computer graphics image display with respect to picture element areas, the primitives P₁, P₂ and so on being defined in planes, a₁ x+b₁ y+c₁ z+d₁ =0;

a₂ x+b₂ y+c₂ z+d₂ =0 and so on, the hidden surface elimination system comprising;

means for receiving primitive data to specify components for a computer graphics display in the form of said primitives P₁ and P₂ and so on;

structure for sequencing said picture element areas to be occupied by said primitives P₁ and P₂ as specified by the received primitive data to identify primitives contending for a picture element area;

a polygon memory for storing data on said polygons;

a mask memory for storing data on said picture element areas;

structure for resolving priority between primitives P₁ and P₂ contending for a pixel area, by determining the values (c₂ a₁ -c₁ a₂), (c₂ b₁ -c₁ b₂) and (c₂ d₁ -c₁ d₂) and logically analyzing the signs of certain of the values to select one of said contending primitives P1 or P2 for the picture element area; and

means for storing signal indications of said one contending primitive in said mask memory.

18. A system according to claim 17 wherein said mask memory stores designations for polygons in said polygon memory to indicate data for said picture element areas.

19. A system according to claim 17 further including a frame buffer storage for said image display and means for storing data from said mask memory and said polygon memory in said frame buffer storage.

20. A system according to claim 19 wherein said means for storing further includes means for processing said data from said mask memory and said polygon memory for shading.