US5684941A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Interpolation rendering of polygons into a pixel grid
Assignee: Nvidia Corp
•
Filing: 1996-08-28
•
Granted: 1997-11-04
•
Expires: 2016-08-28
Abstract
Abstract Interpolation method and apparatus for rendering polygons into a pixel grid. A software driver receives vertices of each polygon and identifies a main slope traversing the vertical extent of the polygon, where the other sides are opposite slopes. The software driver determines initial and incremental width values for width interpolation, rather than edge walking the opposite slopes. The interpolator logic includes a width counter for loading the width value, so that each orthogonal scan line is complete when the width counter reaches terminal count rather than comparing each pixel with the opposite slope. An interpolation procedure thus allows randomly-oriented triangles and other polygons having a main slope, up to two opposite slopes and up to three orthogonal sides to be drawn in a single command. Tessellation of general coplanar polygons is also simplified, where the software driver preferably divides the polygon into randomly-oriented triangles rather than further dividing the polygon into orthogonally-oriented triangles as was done in prior art. Thus, the interpolation method simplifies the logic and provides faster interpolation for polygons.
Inventors
- 👤 Thomas Anthony Dye
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 12:13
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3877; G06F9/3879; G06T; G06T15/00; G06T15/50; G06T15/80; G06T3/00; G06T3/40; G06T3/4007; G06T3/403
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
297 words
A system for interpolating a polygon into a pixel grid having reference and orthogonal dimensions and corresponding reference and orthogonal coordinates, wherein the polygon has a plurality of vertices and is interpolated with a plurality of orthogonal rows of pixels in the pixel grid, the system comprising: tessellation means receiving the vertices of the polygon for dividing the polygon into a plurality of simple polygons, each one of said simple polygons having a subset of the same vertices of the polygon, a main slope traversing the reference extent of each simple polygon in the reference dimension, up to two opposite slopes and up to three orthogonally oriented sides, wherein for each one of said plurality of simple polygons, said tessellation means calculates an initial reference value, an initial orthogonal value, an incremental orthogonal value, an initial width value and an incremental width value; a reference interpolator receiving said initial reference value; an orthogonal interpolator receiving said initial and incremental orthogonal values; a width interpolator receiving said initial and incremental width values for providing a width count representing a number of pixels for each of the orthogonal rows of pixels; a counter receiving said width count for each of the orthogonal rows of pixels, said counter decrementing said width count to zero and providing a terminal count line done signal indicating that the current orthogonal row is complete; and addressing means coupled to said reference, orthogonal and width interpolators and said counter for addressing each pixel of the polygon, wherein for each of said plurality of simple polygons, said addressing means asserts control signals to advance said interpolators to a next orthogonal row of pixels when said terminal count signal is asserted until all of the orthogonal rows are interpolated for each of said plurality of simple polygons.
Claim 2
Independent Claim
297 words
A system for interpolating a polygon into a pixel grid having reference and orthogonal dimensions and corresponding reference and orthogonal coordinates, wherein the polygon has a plurality of vertices and is interpolated with a plurality of orthogonal rows of pixels in the pixel grid, the system comprising: tessellation means receiving the vertices of the polygon for dividing the polygon into a plurality of simple polygons, each one of said simple polygons having a subset of the same vertices of the polygon, a main slope traversing the reference extent of each simple polygon in the reference dimension, up to two opposite slopes and up to three orthogonally oriented sides, wherein for each one of said plurality of simple polygons, said tessellation means calculates an initial reference value, an initial orthogonal value, an incremental orthogonal value, an initial width value and an incremental width value; a reference interpolator receiving said initial reference value; an orthogonal interpolator receiving said initial and incremental orthogonal values; a width interpolator receiving said initial and incremental width values for providing a width count representing a number of pixels for each of the orthogonal rows of pixels; a counter receiving said width count for each of the orthogonal rows of pixels, said counter decrementing said width count to zero and providing a terminal count line done signal indicating that the current orthogonal row is complete; and addressing means coupled to said reference, orthogonal and width interpolators and said counter for addressing each pixel of the polygon, wherein for each of said plurality of simple polygons, said addressing means asserts control signals to advance said interpolators to a next orthogonal row of pixels when said terminal count signal is asserted until all of the orthogonal rows are interpolated for each of said plurality of simple polygons.
Claim 3
Dependent Claim
19 words
The system of claim 1, wherein at least one of said plurality of simple polygons is a randomly-oriented triangle.
Claim 4
Dependent Claim
18 words
The system of claim 1, wherein at least one of said simple polygons has more than three sides.
Claim 5
Dependent Claim
17 words
The system of claim 1, wherein said tessellation means comprises a processor executing a software driver program.
Claim 6
Independent Claim
361 words
An apparatus for interpolating a polygon into a pixel grid, the pixel grid having reference and orthogonal dimensions and corresponding coordinates and wherein the polygon is interpolated with a plurality of orthogonal rows of pixels relative to the main side of the polygon, the apparatus comprising: calculating means for determining a simple polygon including a main side extending the entire length of the simple polygon in the reference dimension, up to two opposite sides and up to three orthogonally oriented sides, and for determining an initial reference value, an initial orthogonal value, an incremental orthogonal value, an initial width value and an incremental width value for the simple polygon; a reference interpolator receiving said initial reference value for providing a reference coordinate for each of the orthogonal row of pixels; an orthogonal interpolator receiving said initial orthogonal value and said incremental orthogonal value for providing an orthogonal coordinate for an initial pixel along the main side of each of the orthogonal row of pixels; a width interpolator receiving said initial width value and said incremental width value for providing a width count representing a number of pixels for each of the orthogonal rows of pixels; and an address controller coupled to said reference interpolator, said orthogonal interpolator and said width interpolator and receiving a count value indicative of a number of orthogonal rows of pixels comprising the simple polygon for asserting address and control signals to control interpolation, said address controller comprising: a width counter receiving said width count for each of the orthogonal rows of pixels and decrementing said width count to zero and then providing a terminal count line done signal indicating completion of a current row pixels; and addressing means coupled to said width counter and receiving said reference and orthogonal coordinates and said count value for asserting an address for each pixel of the simple polygon, said addressing means incrementing or decrementing said orthogonal coordinate until receiving said terminal count signal and then asserting control signals to said reference, orthogonal and width interpolators to advance to the next row of pixels until the total number of rows of pixels are completed as indicated by said count value.
Claim 7
Independent Claim
361 words
An apparatus for interpolating a polygon into a pixel grid, the pixel grid having reference and orthogonal dimensions and corresponding coordinates and wherein the polygon is interpolated with a plurality of orthogonal rows of pixels relative to the main side of the polygon, the apparatus comprising: calculating means for determining a simple polygon including a main side extending the entire length of the simple polygon in the reference dimension, up to two opposite sides and up to three orthogonally oriented sides, and for determining an initial reference value, an initial orthogonal value, an incremental orthogonal value, an initial width value and an incremental width value for the simple polygon; a reference interpolator receiving said initial reference value for providing a reference coordinate for each of the orthogonal row of pixels; an orthogonal interpolator receiving said initial orthogonal value and said incremental orthogonal value for providing an orthogonal coordinate for an initial pixel along the main side of each of the orthogonal row of pixels; a width interpolator receiving said initial width value and said incremental width value for providing a width count representing a number of pixels for each of the orthogonal rows of pixels; and an address controller coupled to said reference interpolator, said orthogonal interpolator and said width interpolator and receiving a count value indicative of a number of orthogonal rows of pixels comprising the simple polygon for asserting address and control signals to control interpolation, said address controller comprising: a width counter receiving said width count for each of the orthogonal rows of pixels and decrementing said width count to zero and then providing a terminal count line done signal indicating completion of a current row pixels; and addressing means coupled to said width counter and receiving said reference and orthogonal coordinates and said count value for asserting an address for each pixel of the simple polygon, said addressing means incrementing or decrementing said orthogonal coordinate until receiving said terminal count signal and then asserting control signals to said reference, orthogonal and width interpolators to advance to the next row of pixels until the total number of rows of pixels are completed as indicated by said count value.
Claim 8
Dependent Claim
118 words
The apparatus of claim 5, wherein the simple polygon includes a first and a second side opposite the main side forming a first and a second half of the simple polygon, further comprising: said calculating means further determining a second incremental width value; said width interpolator further comprising memory for receiving a second incremental width value, wherein said initial width value and said incremental value correspond to the first half and said second incremental value corresponds to the second half of the simple polygon; and wherein said addressing means asserts a half signal indicating the first half of the simple polygon is complete and said width interpolator thereafter uses said second incremental value to complete the simple polygon.
Claim 9
Dependent Claim
58 words
The apparatus of claim 6, further comprising: said calculating means further determining a second width value corresponding to the second half of the simple polygon; and said memory further receiving said second width value; wherein said addressing means further uses said second width value and said second incremental value to complete the second half of the simple polygon.
Claim 10
Dependent Claim
111 words
The apparatus of claim 6, wherein: said count value includes a first and a second count value corresponding to the first and second halves of the simple polygon, respectively, wherein said first count value represents the number of orthogonal rows of pixels in the first half and wherein said second count value represents the number of orthogonal rows of pixels in the second half of the simple polygon; and said addressing means uses said first count value to complete the first half and said second count value to complete the second half of the simple polygon and further asserts said half signal upon completing the first half of the simple polygon.
Claim 11
Dependent Claim
123 words
The apparatus of claim 8, wherein said width interpolator further comprises: said memory including a first register for receiving said incremental width value, a second register for receiving said second incremental width value and a third register for receiving said initial orthogonal width value; a select circuit having inputs coupled to said first and second registers and having an output, said select circuit receiving said half signal for selecting between said first and second registers and providing the contents of the selected register to said output; and an adder circuit coupled to said select circuit and said third register for adding the contents of said third register to the output of said select circuit and providing the sum back into said third register.
Claim 12
Dependent Claim
17 words
The apparatus of claim 5, wherein said calculating means comprises a processor executing a software driver program.
Claim 13
Dependent Claim
74 words
The apparatus of claim 5, wherein said reference interpolator comprises: a first register for receiving an incremental reference value; a second register for receiving said initial reference value; and an adder circuit coupled to said first and second registers for adding the contents of said first and second registers and providing the sum back into said second register, wherein said second register provides said reference coordinate for each of the orthogonal row of pixels.
Claim 14
Dependent Claim
58 words
The apparatus of claim 5, wherein said orthogonal interpolator comprises: a first register for receiving said incremental orthogonal value; a second register for receiving said initial orthogonal value; and an adder circuit coupled to said first and second registers for adding the contents of said first and second registers and providing the sum back into said second register.
Claim 15
Dependent Claim
74 words
The apparatus of claim 5, wherein said width interpolator comprises: a first register for receiving said incremental width value; a second register for receiving said initial width value; and an adder circuit coupled to said first and second registers for adding the contents of said first and second registers and providing the sum back into said second register, wherein said second register provides said width values for each of the orthogonal row of pixels.
Claim 16
Independent Claim
179 words
A method for interpolating a polygon into a pixel grid having reference and orthogonal dimensions and corresponding reference and orthogonal coordinates, wherein the polygon is interpolated with orthogonal rows of pixels, comprising the steps of: determining a simple polygon including a main slope extending the entire length of the polygon in the reference dimension, up to two opposite sides and up to three orthogonally oriented sides; calculating an initial reference value, an initial orthogonal value, an incremental orthogonal value, and initial width value and an incremental width value for the polygon; for each orthogonal row, interpolating reference coordinates for initial pixels along the main slope of the polygon traversing the length of the polygon in the reference dimension; for each orthogonal row, interpolating orthogonal coordinates for the initial pixels of the polygon; for each orthogonal row, interpolating the initial and incremental width values to provide a width count; and for each pixel in each orthogonal row, decrementing the width count until reaching terminal count and then providing a terminal count signal indicating that the current orthogonal row is complete.
Claim 17
Independent Claim
179 words
A method for interpolating a polygon into a pixel grid having reference and orthogonal dimensions and corresponding reference and orthogonal coordinates, wherein the polygon is interpolated with orthogonal rows of pixels, comprising the steps of: determining a simple polygon including a main slope extending the entire length of the polygon in the reference dimension, up to two opposite sides and up to three orthogonally oriented sides; calculating an initial reference value, an initial orthogonal value, an incremental orthogonal value, and initial width value and an incremental width value for the polygon; for each orthogonal row, interpolating reference coordinates for initial pixels along the main slope of the polygon traversing the length of the polygon in the reference dimension; for each orthogonal row, interpolating orthogonal coordinates for the initial pixels of the polygon; for each orthogonal row, interpolating the initial and incremental width values to provide a width count; and for each pixel in each orthogonal row, decrementing the width count until reaching terminal count and then providing a terminal count signal indicating that the current orthogonal row is complete.
Claim 18
Dependent Claim
29 words
The method of claim 14, wherein said step of interpolating reference coordinates comprises the step of incrementing or decrementing the initial reference value by one for each orthogonal row.
Claim 19
Dependent Claim
36 words
The method of claim 14, wherein said step of interpolating orthogonal coordinates comprises the step of: adding the incremental orthogonal value to the initial orthogonal value thereby providing an accumulated orthogonal coordinate for each orthogonal row.
Claim 20
Dependent Claim
37 words
The method of claim 14, wherein said step of interpolating a width value comprises the step of: adding the incremental width value to the initial width value thereby providing an accumulated width count for each orthogonal row.
Claim 21
Dependent Claim
124 words
The method of claim 14, wherein the polygon includes a midpoint forming two half portions of the polygon, further comprising the steps of: calculating a first incremental width value corresponding to the first half portion of the polygon and a second incremental width value corresponding to the second half portion of the polygon; and wherein said step of interpolating a width value comprises the steps of: for each orthogonal row of the first half portion of the polygon, adding the first incremental width value to a width count initially being the initial width value thereby providing an accumulated width count; and for each orthogonal row of the second half portion of the polygon, adding the second incremental width value to the accumulated width count.
Claim 22
Dependent Claim
155 words
The method of claim 14, wherein the polygon includes a midpoint forming two half portions of the polygon, further comprising the steps of: calculating a first initial width value and a first incremental width value corresponding to the first half portion of the polygon and a second initial width value a second incremental width value corresponding to the second half portion of the polygon; and wherein said step of interpolating a width value comprises the steps of: for each orthogonal row of the first half portion of the polygon, adding the first incremental width value to a width count initially being the initial width value thereby providing an accumulated width count; after the first half of the polygon is completed, loading the second initial width value into the accumulated width count; and for each orthogonal row oft he second half portion of the polygon, adding the second incremental width value to the accumulated width value.
Claim 23
Independent Claim
176 words
A method of interpolating a polygon having more than three sides into a pixel grid having reference and orthogonal dimensions and corresponding reference and orthogonal coordinates, wherein the polygon is interpolated with orthogonal rows of pixels, comprising the steps of: dividing the polygon into a plurality of simple polygons, each having a main slope extending the entire length of the simple polygon in the reference dimension, up to two opposite slopes and up to three orthogonally-oriented sides; for each simple polygon, determining an orthogonal component of the main slope; for each orthogonal row of each simple polygon, interpolating reference coordinates for initial pixels along the main slope; for each orthogonal row of each simple polygon, interpolating orthogonal coordinates for the initial pixels along the main slope; for each orthogonal row of each simple polygon, interpolating a width value; and for each pixel in each orthogonal row of each simple polygon, decrementing said width value until reaching terminal count and providing a terminal count signal indicating that the current orthogonal row of the simple polygon is complete.
Claim 24
Independent Claim
176 words
A method of interpolating a polygon having more than three sides into a pixel grid having reference and orthogonal dimensions and corresponding reference and orthogonal coordinates, wherein the polygon is interpolated with orthogonal rows of pixels, comprising the steps of: dividing the polygon into a plurality of simple polygons, each having a main slope extending the entire length of the simple polygon in the reference dimension, up to two opposite slopes and up to three orthogonally-oriented sides; for each simple polygon, determining an orthogonal component of the main slope; for each orthogonal row of each simple polygon, interpolating reference coordinates for initial pixels along the main slope; for each orthogonal row of each simple polygon, interpolating orthogonal coordinates for the initial pixels along the main slope; for each orthogonal row of each simple polygon, interpolating a width value; and for each pixel in each orthogonal row of each simple polygon, decrementing said width value until reaching terminal count and providing a terminal count signal indicating that the current orthogonal row of the simple polygon is complete.
Claim 25
Dependent Claim
38 words
The method of claim 20, wherein said step of dividing the polygon comprises the steps of: receiving vertices of the polygon; and determining a plurality of vectors between an initial vertex and the remaining vertices of the polygon.
Claim 26
Dependent Claim
12 words
The method of claim 20, wherein the simple polygons are randomly-oriented triangles.
References Cited (Backward Citations)
US5450534A
Cited
US5438656A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-11-03 | 2001-05-05 | 2001-11-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-11-03 | 2005-05-05 | 2005-11-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-11-03 | 2009-05-05 | 2009-11-04 | $7700.00 | Window Closed / Lapsed |