Patent US5278949A successfully refreshed from Google Patents.
US5278949A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Polygon renderer which determines the coordinates of polygon edges to sub-pixel resolution in the X,Y and Z coordinates directions
Assignee: HP Inc
•
Filing: 1991-03-12
•
Granted: 1994-01-11
•
Expires: 2011-03-12
Abstract
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.
Inventors
- 👤 Larry J. Thayer
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 13:56
CPC Classifications
G; G06; G06T; G06T15/00; G06T15/50; G06T15/80; G06T15/87
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
391 words
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.
Claim 2
Dependent Claim
391 words
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.
Claim 3
Dependent Claim
50 words
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.
Claim 4
Dependent Claim
50 words
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.
Claim 5
Dependent Claim
66 words
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.
Claim 6
Dependent Claim
23 words
A circuit as in claim 1, wherein said polygon edge stepper determines the z coordinate and x coordinate of said intersections in parallel.
Claim 7
Dependent Claim
18 words
A circuit as in claim 1, wherein said coordinates (x,y,z) of said intersections are determined to sub-pixel resolution.
Claim 8
Dependent Claim
401 words
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.
Claim 9
Dependent Claim
401 words
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.
Claim 10
Independent Claim
407 words
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.
Claim 11
Independent Claim
407 words
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.
Claim 12
Dependent Claim
53 words
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.
Claim 13
Dependent Claim
23 words
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.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-01-10 | 1997-07-12 | 1998-01-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-01-10 | 2001-07-12 | 2002-01-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-01-10 | 2005-07-12 | 2006-01-11 | $7700.00 | Window Closed / Lapsed |