Facsimile and static presentation processing – Static presentation processing – Communication
Reexamination Certificate
1999-09-16
2003-05-20
Evans, Arthur G. (Department: 2622)
Facsimile and static presentation processing
Static presentation processing
Communication
C358S001100
Reexamination Certificate
active
06567182
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 employs a edge array rather than a set linked list from an array of pointers equal in number to the number of scan lines. This invention thus eliminates storage of linked list pointers which in the prior art included many null pointers. This storage method better utilizes on-chip memory when employing a single chip microprocessor. This invention sorts the active edge table only at edge intersections and vertices, thus eliminating much of the sorting of the prior art.
REFERENCES:
patent: 4007362 (1977-02-01), Sindermann
patent: 5764271 (1998-06-01), Donohue
Boggs Lowell
Easwar Venkat V.
Ghose Arunabha
Gupta Sadhana
Kumar Suvarna Harish
Evans Arthur G.
Marshall, Jr. Robert D.
LandOfFree
Scan conversion of polygons for printing file in a page... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scan conversion of polygons for printing file in a page..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scan conversion of polygons for printing file in a page... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3012480