Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Reexamination Certificate
1999-09-16
2001-09-11
Luu, Matthew (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
C345S111000, C707S793000
Reexamination Certificate
active
06288724
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
The technical field of this invention is printers and more particularly the electronics of printers that converts input data in the form of a page description file into control signals for the print engine.
BACKGROUND OF THE INVENTION
Current printers, particularly printers adapted to connect to a local area network and service plural network users, employ a page description language. PostScript is an example of such a page description language. Page description languages are programming languages that allow compact, flexible and device independent description of a page. A print file in a page description language lists the text and graphics to be printed on the page described. The description of the objects to be printed must be converted into a raster bitmap in a process called rasterization in order to be printed. Rasterization is the process of converting the page description into the individual dots making up the lines of the page in the order to be printed. This process enables the page to be printed by the print engine, which generally prints the page line by line from one edge to an opposite edge. The page rasterizer typically consists of an interpreter and a rasterizer. The interpreter parses the input data stream and creates drawing primitives, termed display list elements. The rasterizer does scan-conversion of these primitives.
Many objects in computer graphics applications and page description languages are described through polygons. Even curved shapes are generally approximated to nearest polygons and then rendered. To be printed or displayed these polygons must be converted into the scan technique used by the output device. Polygon scan conversion may be invoked thousands of times to render a graphics image into a refresh buffer. This method must not only create satisfactory images, but also must execute as rapidly as possible. Especially in applications like printers, the real time requirements are stringent to meet. Hence, faster techniques are always wanted.
Currently there are many known techniques to scan convert a polygon. The most popular technique is based on the edge and scan line coherence. If scan line n intersects an edge of a polygon, then scan line n+1 will generally also intersect the same edge. This can be exploited to scan convert a polygon by working with only a set of edges for any scan line. This set of edges is called the active edge table (AET). For the next scan line the new X intersections are computed by merely adding the slope of the edge to the current values. Any new edges intersecting this scan line are added to the active edge table. Further, edges in the active edge table which no longer intersect the next scan line are deleted.
Clipping a polygon against another polygon is very common in many computer graphics applications. Especially in the PostScript page descriptions, every polygon is clipped against the page boundaries. In addition to this rectangle clipping, the PostScript language allows clipping of any irregular shape with any other irregular shape.
If the polygons are of irregular shape, then it may not be possible to scan convert them in real time. So polygons are typically converted to a series of trapezoids. Since trapezoids have regular shape, they may be rendered in real time. In PostScript page rasterization, the decomposition of polygons to trapezoids is done in the interpreting stage. If the input page description involves clipping, then the process of page interpretation becomes slower. The decomposition into trapezoids is a two step process. The first step is clipping two polygons and obtaining the resultant polygon. The second step is converting the resultant polygon to a series of trapezoids. One way of converting a polygon to trapezoids draws scan lines at every vertex. This fixes the bottom and top scan lines for every trapezoid.
SUMMARY OF THE INVENTION
This invention cures many inefficiencies with known scan conversion methods. This invention permits integrated clipping of a subject polygon by a clip polygon and forming trapezoids filling the clipped area. This is achieved by activating trapezoid formation at every vertex of either polygon and at every edge intersection. This integrated process saves code space and computer time because page description languages often require both polygon clipping and trapezoid generation of the clipped area.
REFERENCES:
patent: 3889107 (1975-06-01), Sutherland
patent: 4933889 (1990-06-01), Meshkat et al.
patent: 4958305 (1990-09-01), Piazza
patent: 5051737 (1991-09-01), Akeley et al.
patent: 5268995 (1993-12-01), Diefendorff et al.
patent: 5276783 (1994-01-01), Fossum
patent: 5295235 (1994-03-01), Newman
patent: 5630039 (1997-05-01), Fossum
patent: 5720019 (1998-02-01), Koss et al.
patent: 5877773 (1999-03-01), Rossin et al.
patent: 6128767 (2000-10-01), Chapman
Easwar Venkat V.
Ghose Arunabha
Kumar Suvarna Harish
Brady III W. James
Havan Thu-Thao
Luu Matthew
Marshall, Jr. Robert D.
Telecky , Jr. Frederick J.
LandOfFree
Clipping and trapezoid decomposition of polygons for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Clipping and trapezoid decomposition of polygons for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Clipping and trapezoid decomposition of polygons for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2447420