Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1995-06-06
2001-07-31
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S440000
Reexamination Certificate
active
06268859
ABSTRACT:
FIELD OF THE INVENTION
The present invention is directed to imaging systems, and more particularly to the manner in which overlapping opaque graphical objects are rendered to produce an image in output devices for such systems.
BACKGROUND OF THE INVENTION
Image output devices for imaging systems, such as display monitors and printers, operate as raster devices. In these types of devices, the output image comprises a two-dimensional grid of picture elements, or pixels, which is known as a “raster”. To generate an image on a screen or a page, these devices store a representation in memory of a display value for each pixel in the image. This stored representation of the image is referred to as a “pixel map” (sometimes abbreviated “pixmap”), or a frame buffer. The display value for each pixel comprises multiple components, e.g. red, green and blue components for a monitor which operates in an RGB color space, or cyan, magenta and yellow components for a printer which operates in a CMY color space.
In the operation of an exemplary imaging system, a user might be running a graphics application program on a computer. The user can instruct the program to draw an object, such as a square, at a particular location on the screen of the display monitor. The user might also designate that the square be filled with a certain color, such as 50% purple. In response to these user inputs, the graphics program issues high-level instructions to the computer's operating system to draw a 50% purple square. A display manager, or similar such portion of the computer's operating system for controlling the operation of the display monitor, interprets the command to draw a 50% purple square into low-level instructions for the display monitor. As part of this interpretation process, the high-level description of the purple square from the application program is translated into individual red, green and blue pixel display values that are stored in the frame buffer. In this particular example, each entry in the frame buffer for a corresponding display pixel that is covered by the square stores value of 50% red, 50% blue and 0% green. If the output device is a printer, corresponding values for cyan, magenta and yellow are stored in the frame buffer.
The process of converting the high-level graphical data into pixel values is known as rendering. In a device which employs a three-dimensional color space, such as RGB or CMY, the frame buffer is comprised of three sections, or planes, which respectively relate to the three components. For each pixel of an image, the rendering process involves the steps of determining the display value for one of the components, e.g. the red component, storing that value at an appropriate location in the corresponding section of the frame buffer, and repeating these steps for each of the other two components. In other words, each of the three color space components is individually rendered for each pixel.
The rendering process requires an appreciable amount of processing power, and hence time, in the overall generation of an image. As a general objective, therefore, it is desirable to optimize the rendering process wherever possible, and thereby improve the efficiency with which images are generated. One area of particular interest in this regard pertains to overlapping graphical objects. Typically, each individual object in an image is separately rendered. For example, if the user creates an image containing three overlapping rectangles, when this image is to be displayed on a monitor or printed on a printer, the first rectangle to have been created by the user is initially rendered, followed by the second rectangle and then the third rectangle. In the areas where the rectangles overlap, the information pertaining to the later-generated rectangle overwrites the pixel data for the earlier-generated rectangle, to account for the opacity of the objects. This procedure, by which later-generated data replaces earlier-generated data, is known as the “painter's algorithm.” In essence, data for a later object is “painted over” the data for an earlier object in the frame buffer.
It can be seen that the rendering process is inherently inefficient when overlapping objects are present in the image. Since each object is individually rendered, earlier-generated objects are rendered without consideration of later-generated objects. As a result, any rendering that is carried out with respect to a portion of an object that is obscured by a later-generated object is unnecessary, inefficient and results in wasted processing time. It is desirable, therefore, to avoid rendering portions of objects which are obscured by other objects in an image.
SUMMARY OF THE INVENTION
The present invention provides an optimization for rendering pixels in an image which dynamically avoids the rendering of objects that are obscured in the image. In the implementation of the invention, information pertaining to objects in an image is preferably stored in a suitable form prior to rendering, for example in a display list or a metafile. Image data pertaining to one object is retrieved from the display list and stored in a designated memory location, such as a buffer. Image data for a subsequent object is retrieved from the list and the area of intersection between the two objects is determined. This area of intersection is subtracted from the first object, and the image data for the second object is added to the memory. As the memory is filled, the data for the oldest object is removed and the object is rendered. After all objects in the list have been processed in this manner, those which remain in the memory are also rendered, and removed from the memory.
This approach results in deferred rendering of objects. At each step of the process, portions of an object which are obscured by later-generated objects are removed. As a result, by the time an object is rendered, less of its area, and preferably only the visible portions, remain for processing. The complexity of this approach can be adjusted by varying the size of the memory, e.g. buffer, in which the object data is stored. In a simple implementation, only a single object is stored in the buffer at a time. For even greater simplicity, only particular types of objects, such as rectangles, can be processed in this manner.
Further features of the invention, as well as the advantages attained thereby, are described in greater detail hereinafter with reference to preferred embodiments illustrated in the accompanying drawings.
REFERENCES:
patent: 3944997 (1976-03-01), Swallow
patent: 4791579 (1988-12-01), Kranitzky
patent: 4901252 (1990-02-01), Fitzgerald et al.
patent: 5075876 (1991-12-01), Seki et al.
patent: 5086496 (1992-02-01), Mulmuley
patent: 5125074 (1992-06-01), Labeaute et al.
patent: 5481662 (1996-01-01), Kouyama et al.
patent: 5509110 (1996-04-01), Latham
Andresen Kevin W.
Chen Kok S.
Apple Computer Inc.
Burns Doane Swecker & Mathis L.L.P.
Zimmerman Mark
LandOfFree
Method and system for rendering overlapping opaque graphical... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for rendering overlapping opaque graphical..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for rendering overlapping opaque graphical... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2563683