Polygon renderer which determines the coordinates of polygon edges to sub-pixel resolution in the X,Y and Z coordinates directions

• US 5,278,949 A
• Filed: 03/12/1991
• Issued: 01/11/1994
• Est. Priority Date: 03/12/1991
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Company (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Thayer, Larry J.
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): JANKUS, ALMIS R
• Application Number:
  US07/669,150
• Time in Patent Office: 1,036 Days
• Field of Search: 395/119-122, 395/125-127, 395/132, 395/133, 395/137, 395/138, 395/162-166
• US Class Current: 345/426
• CPC Class Codes: G06T 15/87 Gouraud shading

Abstract

A polygon rendering circuit for a computer color graphics system comprising an edge stepper which steps along edges of an input polygon to determine the span of the polygon along each scan line intersected by the polygon. The coordinate values of the edges on each scan line are determined to sub-pixel resolution such that only those pixels whose centers lie within the true polygon edges (within the span width) must be drawn. Processing efficiency is improved and bandwidth is minimized by passing only those edges of the polygon which are new to that polygon and by computing the Z values in the same manner as, and in parallel with, the X values. Improved results are also possible in accordance with the technique of the invention, for since adjacent polygons compute the same edge by stepping, there can be no gaps between polygons due to round-off errors.

Claims

1. A polygon rendering circuit for rendering a plurality of polygons representing an image to a raster display device, each polygon having respective edges intersecting at least one scan line of said raster display device, comprising:

means for providing coordinates (x,y,z) of respective vertices of said polygon, said vertices representing endpoints of edges of said polygon, and for providing slopes M_x and M_z with respect to a y coordinate of lines connecting the respective vertices of said polygon to form said edges;

a polygon edge stepper for determining coordinates (x,y,z) of an intersection of each of said edges with each scan line of said polygon, said polygon edge stepper starting at a first scan line of said polygon, and (1) determining coordinates (x,y,z) of points along respective edges of said polygon which are in an adjacent scan line by incrementing a coordinate (y) perpendicular to said scan line to a y coordinate of said adjacent scan line, (2) determining a coordinate (x) parallel to said scan line and a coordinate (z) perpendicular to x and y axes for each edge of said polygon intersecting said scan line by adding the slope M_x for the corresponding edge to an x coordinate for that edge on the previous scan line and adding the slope M_z for the corresponding edge to a z coordinate for that edge on the previous scan line, (3) repeating determinations (1) and (2) for each scan line intersecting said respective edges until the coordinates (x,y,z) of said edges for a scan line at an end of at least one edge have been determined, and (4) repeating determinations (1) through (3) for subsequent edges of said polygon, starting from a scan line after the scan line at the end of said at least one edge, until the coordinates (x,y,z) of all said intersections along each edge of said polygon have been determined;

interpolating means for determining which display pixels of said raster display device are on an inside portion of said polygon with respect to the determined coordinates (x,y,z) of all edges of said polygon and appropriately shading for display only those display pixels which are on said inside portion of said polygon; and

a buffer for temporarily storing said shaded display pixels and then sending said shaded display pixels to said raster display device for display.

2. A circuit as in claim 1, wherein said polygon edge stepper comprises a double buffer, responsive to said providing means, for storing the coordinates (x,y,z) of said intersections, said slopes M_x and M_z and a y count value setting forth the number of scan lines in said polygon.

3. A circuit as in claim 2, wherein said polygon edge stepper further comprises a controller responsive to said y count value and a command from said providing means for controlling transfer of data between respective registers of said double buffer and for controlling output of data to said interpolating means.

4. A circuit as in claim 3, wherein said polygon edge stepper further comprises an adder for adding the slope M_x of each edge to the x coordinate for the point of that edge on the previous scan line and an adder for adding the slope M_z of each edge to the z coordinate for the point of that edge on the previous scan line.

5. A circuit as in claim 1, wherein said polygon edge stepper determines the z coordinate and x coordinate of said intersections in parallel.

6. A circuit as in claim 1, wherein said coordinates (x,y,z) of said intersections are determined to sub-pixel resolution.

7. A computer graphics system having a polygon rendering circuit for rendering a plurality of polygons representing an image to a raster display device, each polygon having respective edges intersecting at least one scan line of said raster display device of said computer graphics system, comprising:

means for providing coordinates (x,y,z) of respective vertices of said polygon, said vertices representing endpoints of edges of said polygon, and for providing slopes M_x and M_z with respect to a y coordinate of lines connecting the respective vertices of said polygon to form said edges;

a polygon edge stepper for determining coordinates (x,y,z) of an intersection of each of said edges with each scan line of said polygon, said polygon edge stepper starting at a first scan line of said polygon, and (1) determining coordinates (x,y,z) of points along respective edges of said polygon which are in an adjacent scan line by incrementing a coordinate (y) perpendicular to said scan line to a y coordinate of said adjacent scan line, (2) determining a coordinate (x) parallel to said scan line and a coordinate (z) perpendicular to x and y axes for each edge of said polygon intersecting said scan line by adding the slope M_x for the corresponding edge to an x coordinate for that edge on the previous scan line and adding the slope M_z for the corresponding edge to a z coordinate for that edge on the previous scan line, (3) repeating determinations (1) and (2) for each scan line intersecting said respective edges until the coordinates (x,y,z) of said edges for a scan line at an end of at least one edge have been determined, and (4) repeating determinations (1) through (3) for subsequent edges of said polygon, starting from a scan line after the scan line at the end of said at least one edge, until the coordinates (x,y,z) of all said intersections along each edge of said polygon have been determined;

interpolating means for determining which display pixels of said raster display device are on an inside portion of said polygon with respect to the determined coordinates (x,y,z) of all edges of said polygon and appropriately shading for display only those display pixels which are on said inside portion of said polygon; and

a buffer for temporarily storing said shaded display pixels and then sending said shaded display pixels to said raster display device for display.

8. A method of rendering a plurality of polygons representing an image to a raster display device, each polygon having respectively edges intersecting at least one scan line of said raster display device, comprising the steps of:

(a) providing coordinates (x,y,z) of respective vertices of said polygon, said vertices representing endpoints of edges of said polygon, and providing slopes M_x and M_z with respect to a y coordinate of lines connecting the respective vertices of said polygon to form said edges;

(b) starting at a first scan line of said polygon, determining coordinates (x,y,z) of points along respective edges of said polygon which are in an adjacent scan line by incrementing a coordinate (y) perpendicular to said scan line to a y coordinate of said adjacent scan line and determining a coordinate (x) parallel to said scan line and a coordinate (z) perpendicular to x and y axes for each edge of said polygon intersecting said scan line by adding the slope M_x for the corresponding edge to an x coordinate for that edge on the previous scan line and adding the slope M_z for the corresponding edge to a z coordinate for that edge on the previous scan line;

(c) repeating step (b) for each scan line intersecting said respective edges until the coordinates (x,y,z) of said edges for a scan line at an end of at least one edge have been determined;

(d) if all vertices of said polygon have not been provided, providing the coordinates (x,y,z) of a first vertex of a new edge sharing a second vertex with said end of said at least one edge and the slopes M_x and M_z of a line connecting the first and second vertices of said new edge;

(e) starting from a scan line after the scan line at the end of said at least one edge, repeating steps (b) through (d) for subsequent edges of said polygon until the coordinates (x,y,z) of all intersections with the scan line along each edge of said polygon have been determined;

(f) determining which display pixels of said raster display device are on an inside portion of said polygon with respect to the determined coordinates (x,y,z) of all edges of said polygon; and

(g) shading for display only those display pixels which are on said inside portion of said polygon; and

(b) sending said shaded display pixels to said raster display device for display.

9. A method as in claim 8, wherein a y count value setting forth the number of scan lines in said polygon is further provided in said providing step and said step (e) is completed when the edge coordinates for the number of scan lines specified by said y count values have been determined.

10. A method as in claim 8, wherein said coordinates (x,y,z) of said intersections are determined in steps (b) through (e) to sub-pixel resolution.