Computer graphics processing and selective visual display system – Computer graphic processing system
Reexamination Certificate
2001-05-04
2004-06-15
Razavi, Michael (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphic processing system
C345S503000, C345S506000, C345S418000
Reexamination Certificate
active
06750867
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to apparatus for the processing of images.
The invention is particularly, though not exclusively, suitable for use in systems for the real-time rendering, texturing or shading of three-dimensional (3D) images. Real-time here means sufficiently quickly for the image to be displayed without appreciable perceptible delay to the viewer.
The best known existing system for generating real-time 3D images is the Z-buffer (or depth buffer) image precision algorithm. The Z-buffer algorithm requires a frame buffer in which color values are stored for each pixel (elementary picture element) in an image. In addition to this it requires a Z-buffer with an entry for each pixel. In this Z-buffer, a Z value or depth value is stored for each pixel. To generate a 3D representation, polygons are rendered into the frame buffer in arbitrary order. As a subsequent polygon is entered into the frame buffer, if a point on the polygon is nearer to the viewer than the point already in the frame buffer for that pixel, then the new point's color and Z value replace the previously-stored values. If texture or shading of the polygon is desired, the texturing or shading is applied to the polygon before it is rendered into the frame buffer. The system is fed with a list of vertices which define the polygons, and texture and shading operations are performed on each polygon before a depth test is executed. The performance of such systems is limited by various factors, including the input data bandwidth, the speed of texturing and shading, and the local memory interface bandwidth. It has been proposed to improve the system performance by the use of dual rendering devices, which are ‘scan line interleaved’. That is, there are two processors which process alternate scanlines of the image raster, thus sharing the processing between them.
Another system for generating real-time 3D images is described in United States Patent U.S. Pat. No. 5,729,672 assigned to VideoLogic Limited. This system uses a ‘ray-casting’ technique for the rendering of three-dimensional images rather than conventional polygon-based rendering techniques. In this system, objects are each represented by a set of surfaces which are stored as sets of data. An image plane is deemed to lie between a viewer and the scene to be viewed, and this image plane is composed of a plurality of pixels. A ray is assumed to pass from the viewpoint through a pixel of the screen into the scene to be viewed and will intersect various surfaces which represent objects in the scene. By analysis of these intersections and their distances from the viewer, the system can determine whether any surface is visible. If it is visible, that surface is then textured or shaded as desired. However if the surface is not visible, texturing and shading of the surface is not necessary. One advantage of this system over the Z-buffer is that non-visible surfaces do not have to be textured or shaded.
Texturing or shading of images requires a great deal of processing power. The reduction in processing achieved by the system of the above-mentioned United States Patent is therefore very useful, and can be quite dramatic with certain types of image, particularly those having many overlapping polygons or surfaces.
In the system of the United States Patent, the surfaces defining an object are assumed to extend across the whole of the image plane, that is to say they are ‘infinite’ in extent. Also, each surface is defined as being a forward surface, if it is at the front of the object and thus faces towards the observer, or a reverse surface if it forms part of the back of the object and thus faces away from the observer. To determine whether any given object is visible at any given pixel, in the ray-casting technique, a comparison is made of the distances from the observation point to (a) the forward surface intersection with the ray which is furthest from the observation point and (b) the reverse surface intersection with the ray which is closest to the observation point. If (a) is greater than (b), then, as illustrated in the Patent, that indicates that the ray does not intersect with that object, and thus that that particular object is not visible at the pixel in the image plane through which the ray passes. With this technique, the edges of the surfaces do not have to be defined or calculated as such; it is sufficient to know the vertices of the object as a whole and to calculate the planes occupied by the surfaces. It will be appreciated that the technique requires that every object is checked for every pixel in the image plane to determine whether or not that object is visible at that location.
As described in that patent, the technique makes it particularly easy to apply shadows to appropriate parts of the image. The system is also able to deal with transparency which can take various forms.
The technique has advantages over the Z-buffer system, but nevertheless processing requirements can still be a constraint. It is proposed in the Patent to improve performance by subdividing the image plane or screen into a plurality of sub-regions or ‘tiles’. The tiles are conveniently rectangular (including square). Then for each tile, those objects having surfaces which could fall within the tile are first determined, and only those objects within the tile are processed, thus decreasing the number of surfaces to be processed. The determination of which objects could contribute to each tile may be achieved by surrounding the object with a bounding volume, namely a cuboid which fully contains the object, and comparing the tile area with the bounding volume. To do this, all the bounding volumes are projected onto the image plane and are tested against the corners of the tiles. Those objects which have bounding surfaces which are completely outside the tile are discarded for that tile. Thus the number of surfaces which need to be processed per pixel within a tile becomes less, and hence the total time to render an image is reduced, since the total processing time for all the tiles will be reduced.
The United States Patent describes the use of tiles of variable size. This reflects the fact that objects are not normally evenly distributed over the entire screen. As shown in
FIG. 1
of the drawings of the present application, three tiles
10
are
10
pixels square to accommodate three particular objects, and four tiles
12
are 5 pixels square to accommodate four smaller objects. The image portions for the several tiles are processed in pipeline fashion in a processing system as described in the patent.
We have appreciated that even despite all these features, processing power can still be a constraint, but can be improved by use of the present invention.
SUMMARY OF THE INVENTION
The invention in its various aspects is defined in the appended claims to which reference should now be made. Preferred features of the invention are set forth in the dependent claims.
A preferred embodiment of the invention is described in more detail below with reference to the drawings. Briefly, this preferred embodiment of the invention takes the form of image processing apparatus for rendering (i.e. coloring, texturing or shading) an image includes a tiling device which divides the screen into sub-regions or tiles. Two rendering devices are provided, and the tiles are allocated so that some are processed by one-rendering device and some by the other. Polygons representing objects to be displayed are tested against the tiles. If the surface falls into one sub-region only, the data is sent to one rendering device only. On the other hand, if the polygon falls into two sub-regions being handled by the different rendering devices, then the data is sent to both rendering devices. The result is that a substantial proportion of the data need only be supplied to and processed by one rendering device, thereby speeding the operation of the apparatus. The outputs of the two rendering devices are subsequently combined by tile interleaving and image display circuitry.
REFERENCES
Fouladi Faranak
Imagination Technologies Limited
Razavi Michael
LandOfFree
Image processing apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image processing apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image processing apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3357383