Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Reexamination Certificate
1998-06-18
2001-04-24
Luu, Matthew (Department: 2779)
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
C345S440000, C345S182000, C345S440000
Reexamination Certificate
active
06222556
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a method of image processing and an image processing apparatus. In particular, the present invention relates to the rendering of images composed from a number of discrete polygonal surfaces, known as image primitives.
It is a common technique in real time consumer graphics to model objects as meshes of polygons,especially triangles for ease of handling. This is particularly the case for three-dimensional object modelling wherein, to obtain a two-dimensional image from three-dimensional image data, the polygons making up the object surface in three-dimensional space are projected into two-dimensional space and, following any necessary calculation or reference to look-up tables, appropriate pixel values (including colour, texture etc.) are mapped onto pixel positions within the projected two-dimensional polygon. The calculation following the translation of the polygons from three- to two-dimensional space is suitably handled by a processor pipeline in order to produce the set of display pixel values.
An example of such a processor pipeline for use in a 3D graphics display system, and comprising a series coupled chain of polygon processors, is described in U.S. Pat. No. 4,855,703 (Deering/Schlumberger). Following translation of polygons from three to two dimensions, the polygons are sorted into scan order by reference to the first display pixel line on which they appear. Prior to processing of a scan line, each newly-introduced polygon is loaded into a respective one of the processors in the chain where they are also stored, such that their contribution to successive scan lines may also be derived. When a scan line is reached which is not covered by a particular polygon (i.e. the first clear line below the bottom vertex of, say, a triangular polygon), that polygon is unloaded from the processor in the chain to make way for new polygon data. After processing of a scan line, the pixel data for that line may be sent directly to a display (such as a cathode ray tube [CRT] device) or may be stored in a frame buffer for later accessing.
Before the scan line processing can begin, there is the preliminary process of preparing the two-dimensional polygons which requires, amongst other actions, the calculation of edge slopes, which preliminary process can often consume sufficient computational resources to limit the overall performance of the system. A technique which seeks to simplify this stage somewhat is described in U.S. Pat. No. 4,930,091 (Schroeder & Deering/Schlumberger) which technique is applied to the system of the above-referenced U.S. Pat. No. 4,855,703. In the technique, a triangle classification is introduced whereby a plurality of parameters of a triangle are calculated from the supplied coordinates of the vertices. These parameters are then used to address a look-up table containing a triangle classification with all possible forms of triangle being covered by the varying combinations of parameters: the triangle classification, once read from the look-up table, determines how that triangle is to be processed in the pipeline. In the case of degenerate triangles, where all three vertices lie on a line (such that the triangle itself is just a line) or they are so close together that the triangle does not enclose a pixel (and hence would not show up in the displayed image) no further processing is undertaken.
SUMMARY OF THE INVENTION
Whilst identifying these degenerate cases avoids some of the unnecessary processing of an image, we have recognised that further savings are desirable, and it is accordingly an object of the present invention to improve the efficiency of the graphics rendering process.
In accordance with the present invention there is provided a method of image processing for rendering a two-dimensional pixel image composed of a plurality of polygonal image primitives, said method comprising the steps of:
(a) sorting the image primitives in relation to their locations within the completed image and generating an ordered list of said primitives;
(b) designating image primitives having a maximum horizontal or maximum vertical dimension of one pixel as degenerate and removing said degenerate primitives from the list prior to rendering;
(c) designating image primitives having a maximum horizontal or maximum vertical dimension of two pixels as special, classifying said special primitives according to their arrangement of vertices, and identifying said special primitives in the list; and
(d) rendering the image with those special primitives identified in step (c) being treated according to their particular classification, and for each other primitive, for each scan line crossed by that primitive, ignoring the primitive contribution to an end pixel of that part of each such scan line crossed by the image primitive together with all pixels of a predetermined one of the uppermost and lowermost pixels lines crossed by the image primitive.
The invention makes use of the observation that in certain cases other than the initial degenerate primitives the full computation is not necessary. By identifying these cases and using a simplified computation according to the primitives classification in step (c) above, we have recognised that it is possible to save significant processing time where there are many small polygons in the scene, as is likely to occur where objects are being viewed at a considerable distance (such that each polygon is small by the time it has been projected onto the 2D screen) and for the display of objects which have been composed out of a very large number of small polygons to simulate a smoothly curved surface.
Of the per-primitive pixel contributions to be ignored, suitably the right hand pixel of each scan line part covered by a primitive and the lowermost pixel line are selected: this helps to avoid rendering problems at primitive boundaries. The special primitives fall into a number of categories depending on their arrangement. Each class of special primitive has a common rendering technique which is recited in the claims attached hereto, and will be apparent from the following description of embodiments of the invention.
The initial step of sorting the image primitives may take into account more than just the x,y location of the vertices. For example, where each image primitive has an associated depth value, the step of sorting may further comprise sorting of the images primitives according to their respective depth values. Alternatively, or additionally, where each image primitive has an associated transparency value, the step of sorting may further comprise deleting from the list those primitives wholly covered by one or more opaque primitives: in this way no time is wasted on trying to render either degenerate or occluded primitives.
Also in accordance with the present invention there is provided an image processing apparatus comprising a data processor coupled with first and second memories, the first memory holding image primitive data for processing and the second holding an operating program for the data processor, when operating according to the operating program the data processor providing:
means for sorting the image primitives on the basis of the data in the first memory and in relation to their locations within a completed image and generating an ordered list of said primitives;
means for designating image primitives having a maximum horizontal or maximum vertical dimension of one pixel as degenerate and arranged to remove said degenerate primitives from the list prior to rendering;
means for designating image primitives having a maximum horizontal or maximum vertical dimension of two pixels as special and arranged to classify said special primitives according to their arrangement of vertices, and identify said special primitives in the list; and
image rendering means arranged to render an image from the data in the first memory, with those primitives identified as special being treated according to their particular classification, and for each other primitive, for e
Chung Daniel
Gross Russell
Luu Matthew
U.S. Philips Corporation
LandOfFree
Fast processing of image primitives 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 processing of image primitives, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast processing of image primitives will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2483708