US5343558A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for scan converting shaded triangular polygons
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1991-02-19
•
Granted: 1994-08-30
•
Expires: 2011-02-19
Abstract
Abstract A method for scan converting a triangular polygon where information representative of parameter values at each vertex is provided. The method includes the step of selecting an edge of the triangular polygon which is designated as a major edge and calculating parameter values for a first pixel center adjacent to the major edge, and then moving to a next pixel center adjacent to the major edge and calculating parameter values for that next pixel center adjacent to the major edge. The method continues to find pixel centers adjacent to the major edge until all parameter values for pixel centers adjacent to the major edge have been calculated. Then, for each line parallel to an orthogonal axis of the display device which is intersected by the triangular polygon, the method interpolates parameter values for pixel centers within the triangle which have not been calculated by interpolating from the calculated parameter values for one pixel center for each line. Typically, a line is column or a scan line.
Inventors
- 👤 Kurt Akeley
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 23:22
CPC Classifications
G; G06; G06T; G06T15/00; G06T15/50; G06T15/80
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
273 words
In a computer controlled display system with a processor and a scanned display device having an array of pixels, a computer implemented method for scan converting an arbitrarily positioned triangular polygon for display, wherein each pixel within said triangular polygon is set to a shade corresponding to parameter values stored in memory, said method comprising: reading information representative of parameter values at each vertex of said triangular polygon; selecting an edge of said triangular polygon to provide a selected edge; calculating parameter values for a first pixel center adjacent to said selected edge, wherein said first pixel center may be on either side of said selected edge; moving along said selected edge to a next pixel center adjacent to said selected edge; calculating parameter values for said next pixel center adjacent to said selected edge; repeating said steps of moving and of calculating parameter values for said next pixel center until all parameter values for pixel centers adjacent to said selected edge have been calculated; for each line in a set of lines parallel to an orthogonal axis of said display device, interpolating parameter values for pixel centers on said line within said triangular polygon which have not been calculated, wherein said interpolating is performed according to parameter values determined in said calculating steps which correspond to pixel centers adjacent to said selected edge; storing said parameter values in said memory; reading said parameter values from said memory; generating an electrical signal to actuate said pixels of said triangular polygon on the display device at shades indicated by said parameter values stored in said memory; displaying said triangular polygon on said display device.
Claim 2
Dependent Claim
273 words
In a computer controlled display system with a processor and a scanned display device having an array of pixels, a computer implemented method for scan converting an arbitrarily positioned triangular polygon for display, wherein each pixel within said triangular polygon is set to a shade corresponding to parameter values stored in memory, said method comprising: reading information representative of parameter values at each vertex of said triangular polygon; selecting an edge of said triangular polygon to provide a selected edge; calculating parameter values for a first pixel center adjacent to said selected edge, wherein said first pixel center may be on either side of said selected edge; moving along said selected edge to a next pixel center adjacent to said selected edge; calculating parameter values for said next pixel center adjacent to said selected edge; repeating said steps of moving and of calculating parameter values for said next pixel center until all parameter values for pixel centers adjacent to said selected edge have been calculated; for each line in a set of lines parallel to an orthogonal axis of said display device, interpolating parameter values for pixel centers on said line within said triangular polygon which have not been calculated, wherein said interpolating is performed according to parameter values determined in said calculating steps which correspond to pixel centers adjacent to said selected edge; storing said parameter values in said memory; reading said parameter values from said memory; generating an electrical signal to actuate said pixels of said triangular polygon on the display device at shades indicated by said parameter values stored in said memory; displaying said triangular polygon on said display device.
Claim 3
Dependent Claim
18 words
A method as in claim 1 wherein each of said lines is a column of said display device.
Claim 4
Dependent Claim
29 words
A method as in claim 2 wherein three of said parameter values represent the distance from a pixel center to each of the three edges of said triangular polygon.
Claim 5
Dependent Claim
32 words
A method as in claim 3 further comprising the step of determining a coverage of each pixel of said polygon according to a function of said three parameter values which represent distance.
Claim 6
Dependent Claim
30 words
A method as in claim 2 wherein said step of interpolating parameter values is performed after all parameter values for pixel centers adjacent to said selected edge have been calculated.
Claim 7
Dependent Claim
54 words
A method as in claim 2 wherein said step of interpolating parameter values is performed for a particular column after the parameter values for a pixel center adjacent to said selected edge on said particular column are determined and before the parameter values for all pixel centers adjacent to said selected edge are determined.
Claim 8
Dependent Claim
35 words
A method as in claim 2 wherein said step of selecting an edge to provide a selected edge comprises determining the pair of connected vertices which have the largest difference in their values of X.
Claim 9
Dependent Claim
67 words
A method as in claim 7 further comprising the step of determining whether said triangle is an up triangle or a down triangle, an up triangle having a vertex which is not part of said selected edge and which is above said selected edge, and wherein a down triangle has a vertex which is not part of said selected edge and which is below said selected edge.
Claim 10
Dependent Claim
29 words
A method as in claim 8 wherein said step of determining whether said triangle is an up or down triangle comprises calculating the signed area of said triangular polygon.
Claim 11
Dependent Claim
63 words
A method as in claim 9 wherein said signed area is provided by: (X1-X0)(Y2-Y0)-(X2-X0)(Y1-Y0), where X0,Y0 are the coordinates of one vertex of said selected edge and X1, Y1 are the coordinates of the other vertex of said selected edge, where X0 is less than X1, and X2, Y2 are the coordinates of the vertex which is not part of the selected edge.
Claim 12
Dependent Claim
19 words
A method as in claim 1 wherein each of said lines is a scan line of said display device.
Claim 13
Dependent Claim
29 words
A method as in claim 11 wherein three of said parameter values represent the distance from a pixel center to each of the three edges of said triangular polygon.
Claim 14
Dependent Claim
32 words
A method as in claim 12 further comprising the step of determining a coverage of each pixel of said polygon according to a function of said three parameter values which represent distance.
Claim 15
Dependent Claim
41 words
A method as in claim 11 wherein said step of interpolating parameter values is performed for a particular scan line immediately after the parameter values for a pixel center adjacent to said selected edge on said particular scan line are determined.
Claim 16
Dependent Claim
35 words
A method as in claim 11 wherein said step of selecting an edge to provide a selected edge comprises determining the pair of connected vertices which have the largest difference in their values of Y.
Claim 17
Dependent Claim
74 words
A method as in claim 15 further comprising the step of determining whether said triangle is a left triangle or a right triangle, wherein a left triangle has a vertex which is not part of said selected edge and which is to the left of said selected edge, and wherein a right triangle has a vertex which is not part of said selected edge and which is to the right of said selected edge.
Claim 18
Dependent Claim
29 words
A method as in claim 16 wherein said step of determining whether said triangle is a left or right triangle comprises calculating the signed area of said triangular polygon.
Claim 19
Dependent Claim
64 words
A method as in claim 17 wherein said signed area is provided by: (Y1-Y0)(X2-X0)-(Y2-Y0)(X1-X0), where X0, Y0 are the coordinates of one vertex of said selected edge and X1, Y1 are the coordinates of the other vertex of said selected edge, where Y1 is greater than Y0, and X2, Y2 are the coordinates of the vertex which is not part of the selected edge.
References Cited (Backward Citations)
US4819192A
Cited
US4974177A
Cited
US4805116A
Cited
US4862391A
Cited
US4873515A
Cited
US5163127A
Cited
US5036316A
Cited
US5060172A
Cited
US5123085A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-08-29 | 1998-02-28 | 1998-08-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-08-29 | 2002-02-28 | 2002-08-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-08-29 | 2006-02-28 | 2006-08-30 | $7700.00 | Window Closed / Lapsed |