US5276783A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Tessellating complex polygons in modeling coordinates
Assignee: International Business Machines Corp
•
Filing: 1989-11-21
•
Granted: 1994-01-04
•
Expires: 2009-11-21
Abstract
Abstract A method, in a computer graphics system, 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-10-31 14:59
CPC Classifications
G; G06; G06T; G06T15/00; G06T15/50; G06T15/80; G06T11/00; G06T11/40
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
123 words
A method of displaying, at least one complex polygon, having at least one edge that intersects itself, requested to be displayed by a program application running on a computer graphics system, said method comprising the steps of: determining an angle from which said complex polygon is to be viewed; encompassing said complex polygon by a bounding rectangle that intersects at least two exterior vertex coordinates of said complex polygon; 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; filling portions of said complex polygon within said rectangular regions by a graphics adapter; and displaying all of said complex polygon, based upon said filled portions.
Claim 2
Independent Claim
123 words
A method of displaying, at least one complex polygon, having at least one edge that intersects itself, requested to be displayed by a program application running on a computer graphics system, said method comprising the steps of: determining an angle from which said complex polygon is to be viewed; encompassing said complex polygon by a bounding rectangle that intersects at least two exterior vertex coordinates of said complex polygon; 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; filling portions of said complex polygon within said rectangular regions by a graphics adapter; and displaying all of said complex polygon, based upon said filled portions.
Claim 3
Dependent Claim
66 words
A method according to claim 1 wherein said step of determining comprises the steps of: computing an axis perpendicular to a surface of said complex polygon; 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 characterizing said perpendicular axis by one of the x,y,z, axes closest thereto.
Claim 4
Dependent Claim
93 words
A method according to claim 1, wherein said step of dividing comprises the steps of: determining a longest axis of said bounding rectangle having a length longer that any other axis of said bounding rectangle; determining a shortest axis of said bounding rectangle having a length shorter than any other axis of said bounding rectangle; and determining dimensions of said rectangular regions, each region having a length equal to said shortest axis, and a width determined by two planes perpendicular to said longest axis and intersecting a vertex coordinate of said complex polygon.
Claim 5
Dependent Claim
59 words
A method according to claim 3 wherein said step of dividing comprises the step of: 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
27 words
A method according to claim 1 further comprising the step of: providing first means for storing values representative of all of the edges of said complex polygon.
Claim 7
Dependent Claim
29 words
A method according to claim 5 further comprising the step of: providing second means for storing values representative of the edges of said complex polygon contained within said regions.
Claim 8
Dependent Claim
30 words
A method according to claim 4 wherein said step of subdividing comprises: determining a point of intersection of any of said edges contained within said complex polygon that intersects itself.
Claim 9
Dependent Claim
28 words
A method according to claim 4 wherein said step of subdividing is repeated until there are no said points of intersection contained within said regions of said sub-regions.
Claim 10
Dependent Claim
52 words
A method according to claim 8 wherein said step of providing means for storing values representative of the edges of said complex polygon contained within said regions, comprises the step of: providing means for storing information representative of a color value of said edges contained within said first means for storing values.
References Cited (Backward Citations)
US3889107A
Cited
JPS6074086A
Cited
US4791582A
Cited
JPS6324969A
Cited
US4815009A
Cited
US4855938A
Cited
US4897805A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-01-03 | 1997-07-05 | 1998-01-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-01-03 | 2001-07-05 | 2002-01-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-01-03 | 2005-07-05 | 2006-01-04 | $7700.00 | Window Closed / Lapsed |