Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Reexamination Certificate
1999-02-05
2001-09-04
Luu, Matthew (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
C345S441000, C345S443000
Reexamination Certificate
active
06285375
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates in general to graphics rendering in data processing systems and in particular to polygon processing to generate primitives during graphics rendering. Still more particularly, the present invention relates to converting general polygons to trapezoidal primitives which a display adapter within a data processing system is capable of rendering.
2. Description of the Related Art
Data processing systems commonly include graphics adapters (also referred to as “display adapters”) which receive primitives (e.g., points, lines, or polygons) from the processor for rendering, the process of generating pixel information for a display. The processor may thus write certain, simple primitives to the graphics adapter, which breaks the primitive into scan lines and renders the pixels within each scan line, thereby shifting the overhead associated with breaking the primitive into scan lines and freeing the processor to execute other tasks.
While most contemporary graphics adapters support primitives which are triangles or trapezoids, other polygons, including general polygons, are typically broken into scan lines by the display engine for the operating system or an application, and the scan lines are then sent to the graphics adapter. This consumes processor cycles and may leave the graphics adapter idle, negating the benefits of having a graphics adapter within the data processing system.
It would be desirable, therefore, to provide a mechanism for sending general polygons to a display adapter for rendering.
SUMMARY OF THE INVENTION
It is therefore one object of the present invention to provide an improved method and apparatus for graphics rendering in data processing system.
It is another object of the present invention to provide and method and apparatus for polygon processing to generate primitives during graphics rendering in data processing systems.
It is yet another object of the present invention to provide a method and apparatus for converting general polygons to trapezoidal primitives which a display adapter within a data processing system is capable of rendering.
The foregoing objects are achieved as is now described. General polygons are broken into trapezoids and/or triangles and exported to a graphics adapter for rendering. Intersecting line segments are broken at the point of inter-section. Simple polygons are then derived from the general polygon by starting at an outside corner and selecting line segments defining the general polygon utilizing criteria which will identify closed paths bounding a single area (e.g., always selecting the line segment which extends in a direction identical to or clockwise from the direction of the last selected line segment). Selected line segments are added to a current polygon definition. Each time an inter-section point is entered twice, the selected line segments from the first exit to the second entry of that intersection point are segregated into a separate polygon definition in the polygon list. Once all simple polygons have been identified, each polygon is broken into trapezoids and/or triangles. A base connection point or line segment having the lowest y-coordinate value is identified, together with adjoining line segments. A trapezoid or triangle is then delimited including at least one adjoining line segment, and the process in repeated until all line segments bounding the simple polygon have been added to at least one primitive definition in a primitive list. The primitives may then be exported to the graphics adapter for rendering. Although processor cycles are required to break the general polygon into primitives, in most cases the work required should be significantly less than that involves in breaking the general polygon into scan lines and generating pixel information for the graphics adapter.
The above as well as additional objects, features, and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 4933889 (1990-06-01), Meshkat et al.
patent: 4962468 (1990-10-01), Beauregard et al.
patent: 5129051 (1992-07-01), Cain
patent: 5268995 (1993-12-01), Diefendorff et al.
patent: 5276783 (1994-01-01), Fossum
patent: 5283860 (1994-02-01), Einkauf et al.
patent: 5295235 (1994-03-01), Newman
patent: 5349643 (1994-09-01), Cox et al.
patent: 5371840 (1994-12-01), Fischer et al.
patent: 5570460 (1996-10-01), Ramanujam
patent: 5579459 (1996-11-01), Jennye
patent: 5613050 (1997-03-01), Hochmuth et al.
patent: 5630039 (1997-05-01), Fossum
Parallel Polygon Clipping, May 1994, IBM Technical Disclosure Bulletin, vol. 37, No. 05, pp. 295-307.
Bracewell & Patterson L.L.P.
Havan Thu-Thao
International Business Machines - Corporation
LaBaw Jeffrey S.
Luu Matthew
LandOfFree
Algorithm to transform generalized polygons to trapezoids does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Algorithm to transform generalized polygons to trapezoids, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithm to transform generalized polygons to trapezoids will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2497207