US5841443A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for triangle subdivision in computer graphics texture mapping to eliminate artifacts in high perspective polygons
Assignee: S3 Graphics Co Ltd
•
Filing: 1997-02-20
•
Granted: 1998-11-24
•
Expires: 2017-02-20
Abstract
Abstract The system and method of the present invention performs an iterative operation that subdivides selected polygons (e.g., triangles) having high perspective ratios into a plurality of smaller polygons to limit artifact creation during the rendering/texture map processes. The present invention is particularly well suited for interpolation driven rendering/texture map processes. Processing logic of the present invention analyzes each polygon stored in display list memory of a graphics accelerator or graphics subsystem and determines a perspective ratio between adjacent vertices of the polygon. If the perspective ratio is greater than a pre-selected limit, the edge bounded by the vertices is subdivided at the mid-point and new polygons are created. The process is iterative until all polygons have perspective ratios that are less than the pre-selected limit, at which time the object data can be displayed by the hardware. Perspective values (w) and three dimensional coordinates (x, y, z) for each created mid-point are calculated by averaging the perspective values at the vertices bounding the edge. Texture coordinates at the mid-point of a divided edge (umid, vmid) are calculated and then interpolated across the resulting polygon to determine the texels values of the image at each pixel within the boundary of the polygon. The present invention eliminates artifact creation when used with interpolation driven rendering/texture map processes that might otherwise not properly process polygons with large perspective.
Inventors
- 👤 Mark Alan Einkauf
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 17:55
CPC Classifications
G; G06; G06T; G06T17/00; G06T17/20
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
200 words
In a computer controlled graphics display system wherein objects are represented by data structures defining: the orientation and location of a plurality of polygons; and texture data defining surface characteristics of said object, said data structures at least partially stored in computer memory prior to rendering on a display screen, a method for subdividing polygons having a high degree of perspective, said method comprising the steps of: (a) selecting, from said computer memory, a selected polygon from said plurality of polygons that at least partially define a depiction of said object, said selected polygon comprising at least three vertices wherein each vertex has a perspective term, W, associated therewith that defines a display perspective of said associated vertex with respect to a given viewing angle; (b) determining perspective ratios for each pair of adjacent vertices of said at least three vertices of said selected polygon; (c) subdividing said selected polygon to generate a plurality of new polygons provided any of said perspective ratios exceeds a preselected perspective threshold amount; and (d) rendering and displaying said selected polygon on a display screen of said computer controlled graphics display system provided none of said perspective ratios exceeds said preselected perspective threshold amount.
Claim 2
Dependent Claim
200 words
In a computer controlled graphics display system wherein objects are represented by data structures defining: the orientation and location of a plurality of polygons; and texture data defining surface characteristics of said object, said data structures at least partially stored in computer memory prior to rendering on a display screen, a method for subdividing polygons having a high degree of perspective, said method comprising the steps of: (a) selecting, from said computer memory, a selected polygon from said plurality of polygons that at least partially define a depiction of said object, said selected polygon comprising at least three vertices wherein each vertex has a perspective term, W, associated therewith that defines a display perspective of said associated vertex with respect to a given viewing angle; (b) determining perspective ratios for each pair of adjacent vertices of said at least three vertices of said selected polygon; (c) subdividing said selected polygon to generate a plurality of new polygons provided any of said perspective ratios exceeds a preselected perspective threshold amount; and (d) rendering and displaying said selected polygon on a display screen of said computer controlled graphics display system provided none of said perspective ratios exceeds said preselected perspective threshold amount.
Claim 3
Dependent Claim
27 words
A method as described in claim 1 further comprising the step of: (e) repeating said steps of (a)-(c) for each new polygon generated by said step (c).
Claim 4
Dependent Claim
92 words
A method as described in claim 1 wherein said step (c) comprises the steps of: (c1 ) dividing said selected polygon into four new polygons provided three edges of said selected polygon have perspective ratios exceeding said preselected threshold amount; (c2) dividing said selected polygon into three new polygons provided only two edges of said selected polygon have perspective ratios exceeding said preselected threshold amount; and (c3) dividing said selected polygon into two new polygons provided only one edge of said selected polygon has a perspective ratio exceeding said preselected threshold amount.
Claim 5
Dependent Claim
94 words
A method as described in claim 3 wherein said step (c1) comprises the step of inserting three mid-points between adjacent vertex pairs of said selected polygon to constitute new vertices for said four new polygons, wherein said step (c2) comprises the step of inserting two midpoints between adjacent vertex pairs of said selected polygon to constitute new vertices for said three new polygons, and wherein said step (c3) comprises the step of inserting one mid-point between an adjacent vertex pair of said selected polygon to constitute a new vertex for said two new polygons.
Claim 6
Dependent Claim
50 words
A method as described in claim 4 further comprising the step of determining data for each inserted midpoint resultant from said steps (c1), (c2), and (c3), said data comprising: three dimensional coordinate values (x, y, z); texture map coordinate values (u, v); color (R, G, B); and perspective terms (W).
Claim 7
Dependent Claim
149 words
A method as described in claim 5 wherein said step of determining data for each inserted midpoint comprises the steps of: (1) calculating a perspective term, Wmid, for a midpoint of a given adjacent pair of vertices, A and B, in accordance with: Wmid=(WA+WB)/2 where WA and WB denote perspective terms for said vertices A and B, respectively; (2) calculating intermediate variables, a and a', in accordance with: a=uA*WA a'=vA*WA where uA and vA respectively denote the u-axis and v-axis texture coordinates for said vertex A; (3) calculating intermediate variables, b and b', in accordance with: b=uB*WB b'=vB*WB where uB and vB respectively denote the u-axis and v-axis texture coordinates for said vertex B; (4) calculating intermediate variables, c and c', in accordance with: c=(a+b)/2 c'=(a'+b')/2; and (5) calculating umid and vmid in accordance with: umid=c/Wmid vmid =c'/Wmid where umid and vmid are the texture coordinates for said midpoint.
Claim 8
Dependent Claim
90 words
A method as described in claim 1 wherein for a given pair of adjacent vertices, A and B, said step (b) comprises the steps of: (b1) dividing a perspective term associated with vertex A with a perspective term associated with adjacent vertex B to obtain a first perspective ratio associated with said given pair of adjacent vertices; and (b2) dividing said perspective term associated with vertex B with said perspective term associated with adjacent vertex A to obtain a second perspective ratio associated with said given pair of adjacent vertices.
Claim 9
Dependent Claim
19 words
A method as described in claim 1 wherein said preselected threshold is between the range of 1.25 to 1.5.
Claim 10
Dependent Claim
22 words
A method as described in claim 1 further comprising the step of receiving said preselected threshold amount from a user defined adjustment.
Claim 11
Dependent Claim
223 words
In a computer controlled graphics display system having a processor coupled to bus, and a graphics subsystem coupled to said bus, and wherein objects are represented by a plurality of polygons and texture data defining surface characteristics of object, a computer readable memory unit coupled to said bus and storing instructions therein that when executed causing said system to implement a method for subdividing polygons having a high degree of perspective, said method comprising the steps of: (a) selecting, from said computer memory, a selected polygon from said plurality of polygons that at least partially define a depiction of said object, said selected polygon comprising at least three vertices wherein each vertex has a perspective term, W, associated therewith that defines a display perspective of said associated vertex with respect to a given viewing angle; (b) determining perspective ratios for each pair of adjacent vertices of said at least three vertices of said selected polygon; (c) subdividing said selected polygon to generate a plurality of new polygons provided any of said perspective ratios exceeds a preselected perspective threshold amount; and (d) rendering and displaying said selected polygon on a display screen of said computer controlled graphics display system provided none of said perspective ratios exceeds said preselected perspective threshold amount (e) repeating said steps (a)-(d) for each polygon of said plurality of polygons.
Claim 12
Dependent Claim
223 words
In a computer controlled graphics display system having a processor coupled to bus, and a graphics subsystem coupled to said bus, and wherein objects are represented by a plurality of polygons and texture data defining surface characteristics of object, a computer readable memory unit coupled to said bus and storing instructions therein that when executed causing said system to implement a method for subdividing polygons having a high degree of perspective, said method comprising the steps of: (a) selecting, from said computer memory, a selected polygon from said plurality of polygons that at least partially define a depiction of said object, said selected polygon comprising at least three vertices wherein each vertex has a perspective term, W, associated therewith that defines a display perspective of said associated vertex with respect to a given viewing angle; (b) determining perspective ratios for each pair of adjacent vertices of said at least three vertices of said selected polygon; (c) subdividing said selected polygon to generate a plurality of new polygons provided any of said perspective ratios exceeds a preselected perspective threshold amount; and (d) rendering and displaying said selected polygon on a display screen of said computer controlled graphics display system provided none of said perspective ratios exceeds said preselected perspective threshold amount (e) repeating said steps (a)-(d) for each polygon of said plurality of polygons.
Claim 13
Dependent Claim
33 words
A computer readable memory unit as described in claim 10 wherein said method further comprises the step of: (f) repeating said steps of (a)-(c) for each new polygon generated by said step (c).
Claim 14
Dependent Claim
94 words
A computer readable memory unit as described in claim 10 wherein said step (c) comprises the steps of: (c1) dividing said selected polygon into four new polygons provided three edges of said selected polygon have perspective ratios exceeding said preselected threshold amount; (c2) dividing said selected polygon into three new polygons provided only two edges of said selected polygon have perspective ratios exceeding said preselected threshold amount; and (c3) dividing said selected polygon into two new polygons provided only one edge of said selected polygon has a perspective ratio exceeding said preselected threshold amount.
Claim 15
Dependent Claim
95 words
A computer readable memory unit of claim 12 wherein said step (c1) comprises the step of inserting three mid-points between adjacent vertex pairs of said selected polygon to constitute new vertices for said four new polygons, wherein said step (c2) comprises the step of inserting two mid-points between adjacent vertex pairs of said selected polygon to constitute new vertices for said three new polygons, and wherein said step (c3) comprises the step of inserting one mid-point between one adjacent vertex pair of said selected polygon to constitute a new vertex for said two new polygons.
Claim 16
Dependent Claim
58 words
A computer readable memory unit as described in claim 13 wherein said method further comprises the step of determining data for each inserted midpoint as a result of said steps (c1), (c2), and (c3), said data comprising: three dimensional coordinate values (x, y, z); texture map coordinate values (u, v); color (R, G, B); and perspective terms (W).
Claim 17
Dependent Claim
153 words
A computer readable memory unit as described in claim 14 wherein said step of determining data for each inserted midpoint comprises the steps of: (1) calculating a perspective term, Wmid, for a midpoint of a given adjacent pair of vertices, A and B, in accordance with: Wmid=(WA+WB)/2 where WA and WB denote perspective terms for said vertices A and B, respectively; (2) calculating intermediate variables, a and a', in accordance with: a=uA*WA a'=vA*WA where uA and vA respectively denote the u-axis and v-axis texture coordinates for said vertex A; (3) calculating intermediate variables, b and b', in accordance with: b=uB*WB b'=vB*WB where uB and vB respectively denote the u-axis and v-axis texture coordinates for said vertex B; (4) calculating intermediate variables, c and c', in accordance with: c=(a+b)/2 c'=(a'+b')/2 ; and (5) calculating umid and vmid in accordance with: umid=c/Wmid vmid =c'/Wmid where umid and vmid are the texture coordinates for said midpoint.
Claim 18
Dependent Claim
93 words
A computer readable memory unit as described in claim 10 wherein for a given pair of adjacent vertices, A and B, said step (b) comprises the steps of: (b1) dividing a perspective term associated with vertex A with a perspective term associated with adjacent vertex B to obtain a first perspective ratio associated with said given pair of adjacent vertices; and (b2) dividing said perspective term associated with vertex B with said perspective term associated with adjacent vertex A to obtain a second perspective ratio associated with said given pair of adjacent vertices.
Claim 19
Dependent Claim
251 words
In a computer controlled graphics display system wherein objects are represented by data structures defining a plurality of polygons and texture data defining surface characteristics of said object, a method for subdividing polygons having a high degree of perspective, said method comprising the steps of: (a) selecting, from said computer memory, a selected polygon from said plurality of polygons, said selected polygon comprising at least three vertices wherein each vertex has a perspective term, W, associated therewith that defines a display perspective of said associated vertex with respect to a given viewing angle; (b) determining perspective ratios for each pair of adjacent vertices of said at least vertices of said selected polygon; (c) subdividing said selected polygon to generate a plurality of new polygons provided any of said perspective ratios exceeds a preselected perspective threshold amount, wherein said step (c) comprises the steps of: (c1) dividing said selected polygon into four new polygons provided three edges of said selected polygon have perspective ratios exceeding said preselected threshold amount; (c2) dividing said selected polygon into three new polygons provided only two edges of said selected polygon have perspective ratios exceeding said preselected threshold amount; and (c3) dividing said selected polygon into two new polygons provided only one edge of said selected polygon has a perspective ratio exceeding said preselected threshold amount; and (d) rendering and displaying said selected polygon on a display screen of said computer controlled graphics display system provided none of said perspective ratios exceeds said preselected perspective threshold amount.
Claim 20
Dependent Claim
251 words
In a computer controlled graphics display system wherein objects are represented by data structures defining a plurality of polygons and texture data defining surface characteristics of said object, a method for subdividing polygons having a high degree of perspective, said method comprising the steps of: (a) selecting, from said computer memory, a selected polygon from said plurality of polygons, said selected polygon comprising at least three vertices wherein each vertex has a perspective term, W, associated therewith that defines a display perspective of said associated vertex with respect to a given viewing angle; (b) determining perspective ratios for each pair of adjacent vertices of said at least vertices of said selected polygon; (c) subdividing said selected polygon to generate a plurality of new polygons provided any of said perspective ratios exceeds a preselected perspective threshold amount, wherein said step (c) comprises the steps of: (c1) dividing said selected polygon into four new polygons provided three edges of said selected polygon have perspective ratios exceeding said preselected threshold amount; (c2) dividing said selected polygon into three new polygons provided only two edges of said selected polygon have perspective ratios exceeding said preselected threshold amount; and (c3) dividing said selected polygon into two new polygons provided only one edge of said selected polygon has a perspective ratio exceeding said preselected threshold amount; and (d) rendering and displaying said selected polygon on a display screen of said computer controlled graphics display system provided none of said perspective ratios exceeds said preselected perspective threshold amount.
Claim 21
Dependent Claim
41 words
A method as described in claim 17 further comprising the steps of: (e) repeating said steps (a)-(d) for each polygon of said plurality of polygons; and (f) repeating said steps of (a)-(c) for each new polygon generated by said step (c).
Claim 22
Dependent Claim
94 words
A method as described in claim 17 wherein said step (c1) comprises the step of inserting three mid-points between adjacent vertex pairs of said selected polygon to constitute new vertices for said four new polygons, wherein said step (c2) comprises the step of inserting two midpoints between adjacent vertex pairs of said selected polygon to constitute new vertices for said three new polygons, and wherein said step (c3) comprises the step of inserting one mid-point between one adjacent vertex pair of said selected polygon to constitute a new vertex for said two new polygons.
Claim 23
Dependent Claim
90 words
A method as described in claim 17 wherein for a given pair of adjacent vertices, A and B, said step (b) comprises the steps of: (b1) dividing a perspective term associated with vertex A with a perspective term associated with adjacent vertex B to obtain a first perspective ratio associated with said given pair of adjacent vertices; and (b2) dividing said perspective term associated with vertex B with said perspective term associated with adjacent vertex A to obtain a second perspective ratio associated with said given pair of adjacent vertices.
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) | 2001-11-23 | 2002-05-25 | 2002-11-24 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-11-23 | 2006-05-25 | 2006-11-24 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-11-23 | 2010-05-25 | 2010-11-24 | $7700.00 | Window Closed / Lapsed |