Computer graphics processing and selective visual display system – Computer graphics processing – Graphic manipulation
Reexamination Certificate
1999-09-09
2004-12-07
Bella, Matthew C. (Department: 2676)
Computer graphics processing and selective visual display system
Computer graphics processing
Graphic manipulation
C345S418000, C345S421000, C345S426000, C345S428000
Reexamination Certificate
active
06828985
ABSTRACT:
FIELD OF INVENTION
The present invention relates to the rendering of object graphic elements into raster pixel images and, in particular, to efficient rendering of such elements to pixel image data without the use of frame or line storage of the pixel data as part of the rendering process.
BACKGROUND
Most object based graphics systems utilise a frame store or page buffer to hold a pixel-based image of the page or screen. Typically, the outlines of the graphic objects are calculated, filled and written into the frame store. For two-dimensional graphics, objects which appear in front of other objects are simply written into the frame store after the background objects, thereby replacing the background on a pixel-by-pixel basis. This is commonly known in the art as the “Painter's algorithm”. Objects are considered in priority order, from the rearmost object to the foremost object, and, typically, each object is rasterised in scan line order and pixels are written to the frame store in sequential runs along each scan line.
There are essentially two problems with this technique. The first is that it requires fast random access to all the pixels in the frame store. This is because each new object considered could affect any pixel in the frame-store. For this reason, the frame store is normally kept in semiconductor random access memory (RAM). For high resolution colour printers the amount of RAM required is very large, typically in excess of 100 MBytes, which is costly and difficult to operate at high speed. The second problem is that many pixels which are painted (rendered), are over-painted (re-rendered) by later objects. Painting the pixels with the earlier objects was a waste of time.
One method for overcoming the large frame-store problem is the use of “banding”. When banding is used, only part of the frame-store exists in memory at any one time. All of the objects to be drawn are retained in a “display list”. The whole image is rendered as above, but pixel painting (rendering) operations that try to paint (render) outside the fraction of the frame-store which exists are “clipped” out. After all the objects have been drawn, the fractional part of the frame-store is sent to the printer (or some other location) and another fraction of the frame-store is selected and the process repeated. There are penalties with this technique. For example, the objects being drawn must be considered and re-considered many times—once for each band. As the number of bands increases, so too does the repetitious examination of objects requiring rendering. The technique of banding does not solve the problem of the cost of over-painting.
Some other graphic systems consider the image in scan line order. Again, all the objects to be drawn are retained in a display list. On each scan line the objects which intersect that scan line are then considered in priority order and for each object, spans of pixels between object edge intersection points are set in a line store. This technique also overcomes the large frame store problem, but still suffers from the over-paint problem.
There are other techniques which overcome both the large frame-store problem and the over-painting problem. In one such technique, each scan line is produced in turn Again, all the objects to be drawn are retained in a display list. On each scan line, the edges of objects which intersect that scan line are held in order of increasing coordinate of intersection with the scan line. These points of intersection, or edge crossings, are considered in turn and used to toggle an array of active flags. There is one active flag for each object priority which is of interest on the scan line. Between each pair of edges considered, the colour data for each pixel which lies between the first edge and the next edge is generated by using a priority encoder on the active flags to determine which priority is topmost, and using the colour associated with that priority for the pixels of the span between the two edges. In preparation for the next scan line, the coordinate of intersection of each edge is updated in accordance with the nature of each edge. Adjacent edges which become mis-sorted as a result of this update are swapped. New edges are also merged into the list of edges.
This technique has the significant advantages that there is no frame store or line store, there is no over painting, and the object priorities are dealt with in constant order time, rather than order N time (where N is the number of priorities).
However, there are several limitations to this technique:
(i) The technique only supports the “odd-even” fill rule, known in the art for determining the inside versus outside state of an object from its edges. The “non-zero winding” fill rule, which is a required feature of many graphic description languages, is not supported by that technique.
(ii) Large mis-sorting can occur for which a simple swapping technique is inadequate to repair. While a brute-force sort of the whole of the edge list on each scan line can be performed, this is very slow.
(iii) The technique does not support raster (pixel-based) images as an object type. Such images are a required feature of most graphic description languages.
(iv) The technique only supports objects which are opaque, where each painted pixel strictly obscures the pixels of objects with lesser priority. The technique does not support raster operations in which the colour of two or more graphic objects interact. Such operations include drawing in XOR mode, or the compositing of partially transparent objects. These modification operations are a required feature of most graphic description languages.
(v) The technique does not support clipping, where one or more clip shapes suppress some number of other graphics objects inside (or outside) the bounds of the clip shapes. Clipping is a required feature of most graphic description languages.
(vi) The technique uses voluminous and inefficient encoding of object edges, particularly for text. It is desirable for such an extremely common element of graphic descriptions to be represented in a simpler fashion.
(vii) The technique in some instances does not provide for accurate evaluation of complicated compositing expressions where the activity of one or more objections is variable.
The inability of the technique to implement many features required by existing graphic description languages severely limits its use.
Further, some existing rendering interfaces require implementation of the bit-wise logical combination of the colour of two or more graphic objects. Other existing rendering interfaces require implementation of an alpha channel (also referred to as transparency, opacity, or matte) based combination of the colour of two or more graphic objects. Current techniques do not allow these two features to be implemented in a unified fashion.
SUMMARY OF THE INVENTION
It is an object of the present invention to substantially overcome, or at least ameliorate, one or more deficiencies with prior art systems.
In accordance with one aspect of the present invention there is disclosed a method of rendering at least one graphic object described by at least one edge into a raster pixel image having a plurality of scan lines and a plurality of pixel locations on each said scan line, said method comprising, for each said scan line, the steps of:
determining in a predetermined order coordinates of intersection of those edges of said objects that intersect said scan line;
for each adjacent pair of edge intersections, examining information associated with the corresponding said object to determining a set of active objects for a span of pixel locations between the corresponding pair of edge intersections; and
for each said span of pixel locations, using the corresponding set of active objects to determine a value for each of said locations within said span.
In accordance with another aspect of the present invention there is disclosed a method of rendering a plurality of graphic objects described by at least one edge to form a raster pixel image having a plurality of
Fraser Christopher
Lie Kok Tjoan
Long Timothy Merrick
Moore Kevin
Bella Matthew C.
Sajous Wesner
LandOfFree
Fast rendering techniques for rasterised graphic object... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast rendering techniques for rasterised graphic object..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast rendering techniques for rasterised graphic object... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3323685