US5630039A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Tessellating complex in polygons in modeling coordinates
Assignee: International Business Machines Corp
•
Filing: 1994-02-28
•
Granted: 1997-05-13
•
Expires: 2014-02-28
Abstract
Abstract A computer graphics system, that manipulates the vertices contained within a group of possibly self intersecting, free space, over lapping polygons, into simple, convex polygons. A normal axis to the complex polygon is determined such that the surface of the polygon is viewed along this normal axis. The polygon surface is then bounded by a rectangle and subdivided into a group of slabs, or smaller rectangles, each rectangular slab being bounded by a pair of interior vertices of the complex polygon. An active edge table is used to store values corresponding to the edges crossing through the slabs, which are used to determine if these edges cross are another at any point within the slab. If a crossing point does exist, the slabs are divided at the crossing point into rectangular sub-slabs until it is determined that no edge intersects another edge within the sub-slabs, of the original slab being considered. At this point, the edges contained within the rectangular slabs can be viewed as simple polygons, or trapezoids which can be filled by a conventional graphics adapter and then displayed.
Inventors
- 👤 Gordon C. Fossum
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 21:44
CPC Classifications
G; G06; G06T; G06T15/00; G06T15/50; G06T15/80; G06T11/00; G06T11/40
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
175 words
A computer program, including instructions which implement specific operations and are stored as a unique data structure on a computer readable media in a computer graphics system, for displaying at least one complex polygon, having at least one edge that intersects itself, comprising: means for determining an angle from which said complex polygon is to be viewed; means, implemented by said instructions in said data structure, for causing said complex polygon to be encompassed by a bounding rectangle which is the smallest rectangle that will encompass said complex polygon, said bounding rectangle intersecting at least two exterior vertex coordinates of said complex polygon; means, implemented by said instructions in said data structure, for dividing said bounding rectangle into rectangular regions, such that none of said regions contain any interior vertices where at least one of said complex polygon edges intersects itself; means for controlling a graphics adapter to fill portions of said complex polygon within said rectangular regions; and means for causing all of said complex polygon to be displayed, based upon said filled portions.
Claim 2
Dependent Claim
175 words
A computer program, including instructions which implement specific operations and are stored as a unique data structure on a computer readable media in a computer graphics system, for displaying at least one complex polygon, having at least one edge that intersects itself, comprising: means for determining an angle from which said complex polygon is to be viewed; means, implemented by said instructions in said data structure, for causing said complex polygon to be encompassed by a bounding rectangle which is the smallest rectangle that will encompass said complex polygon, said bounding rectangle intersecting at least two exterior vertex coordinates of said complex polygon; means, implemented by said instructions in said data structure, for dividing said bounding rectangle into rectangular regions, such that none of said regions contain any interior vertices where at least one of said complex polygon edges intersects itself; means for controlling a graphics adapter to fill portions of said complex polygon within said rectangular regions; and means for causing all of said complex polygon to be displayed, based upon said filled portions.
Claim 3
Dependent Claim
68 words
A computer program according to claim 1 wherein said means for determining comprises: computing an axis perpendicular to a surface of said complex polygon: means for comparing said perpendicular axis to the x,y,z axes contained within a cartesian coordinate system to determine the closest one of said x,y,z axes to said perpendicular axis: and means for characterizing said perpendicular axis by one of the x,y,z, axes closes thereto.
Claim 4
Dependent Claim
89 words
A computer program according to claim 1 wherein said means for dividing comprises: means for determining a longest axis of said bounding rectangle havng a length longer that any other axis of said bounding rectangle; means for determining a shortest axis of said bounding rectangle having s length shorter than any other axis of said bounding rectangle; and means for determining dimensions of said rectangular regions, each region and a width determined by two planes perpendicular to said longest axis end intersecting a vertex coordinate of said complex polygon.
Claim 5
Dependent Claim
59 words
A computer program according to claim 3 wherein said means for dividing comprises: means for subdividing said rectangular regions into rectangular sub-regions, said regions being subdivided by at least one additional plane that is perpendicular to said longest axis and contains at least one of said interior vertices where at least one of said complex polygon edges intersects itself.
Claim 6
Dependent Claim
32 words
A computer program according to claim 4 wherein said means for subdividing comprises: means for determining point of intersection of any of said edges contained within said complex polygon that intersects itself.
Claim 7
Dependent Claim
29 words
A computer program according to claim 4 wherein said means for subdividing is repeated until there are no said points of intersection contained within said regions or said sub-regions.
Claim 8
Dependent Claim
24 words
A computer program according to claim 1 further comprising: first means for storing values representative of all of the edges of said complex polygon.
Claim 9
Dependent Claim
26 words
A computer program according to claim 7 further comprising: second means for storing values representative of the edges of said complex polygon contained within said regions.
Claim 10
Dependent Claim
47 words
A computer program according to claim 8 wherein said second means for storing values representative of the edges of said complex polygon contained within said regions, comprises: means for storing information representative of a color value of said edges contained within said first means for storing values.
References Cited (Backward Citations)
US3816726A
Cited
JPS6074086A
Cited
US4715005A
Cited
US4709231A
Cited
US4710876A
Cited
US4812988A
Cited
US4841292A
Cited
US4855934A
Cited
US4815009A
Cited
JPS6476373A
Cited
US4855938A
Cited
US4912659A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-05-12 | 2000-11-11 | 2001-05-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-05-12 | 2004-11-11 | 2005-05-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-05-12 | 2008-11-11 | 2009-05-13 | $7700.00 | Window Closed / Lapsed |