1. Field of the Invention
The present invention relates to a system for sorting image data in real time and an image synthesizing system using such a sorting processing system.
2. Description of the Related Art
Such an image synthesizing system as shown in FIG. 18 has been used, for example, in pseudo 3-D video games, a flight simulator, or other driving simulators. The image synthesizing system has previously stored image data relating to a 3-D object 300. If the image synthesizing system is used in a driving game, the 3-D object is in the form of a racing car. The image synthesizing system also forms a variety of other 3-D objects which are roads, houses and other background images disposed in a 3-D space.
When a player 302 operates a handle or other tool on a player's control panel 304 to rotate or translate the 3-D object or racing car 300, the image synthesizing system responds to operation signals to compute information of images after the rotation or translation of the 3-D object 300 in real time. The computed images are then projected onto a screen 306 in a perspective transformation manner. As a result, the player 302 can virtually simulate the pseudo 3-D space as he or she actually rotates or translates the 3-D object 300 in real time.
One of such image synthesizing systems is shown in FIG. 19.
Image data relating to the 3-D object 300 are represented as a polyhedron divided into 3-D polygons as shown by (1)-(6) in FIG. 18 (polygons (4)-(6) being not shown in this Figure). As shown in FIG. 19, the coordinates and associated data of vertex in each of the 3-D polygons have been stored in a 3-D data memory 314 in an image supply unit 308. The coordinates of vertices are read out by a 3-D computing unit 316. According to control signals from an operator's control unit 310 through a main CPU 312, the image synthesizing system performs the computations of rotation, translation or other motions relating to the coordinates of vertices and the transformations of coordinate such as perspective transformation or others. Thereafter, image data of polygons will be outputted through the image supply unit 308.
An image display unit 360 then responds to the polygon image data or coordinates of vertices of polygon from the image supply unit 308 to paint all the dots in the polygons with corresponding color data or other data.
If two polygons are overlapped on each other in such a painting operation, it is required that polygon parts farthest from the view point are not displayed (hidden surface removal) and that only polygon parts closest to the view point are displayed on the screen. One of such hidden surface removal techniques is known as Z-buffer technique which is described, for example, in "Jyoho-Shori (Information Processing)", Vol. 24, No. 4, issued by Information Processing Society of Japan on Apr. 15, 1983.
In order to perform the hidden surface removal through the Z-buffer technique, the image synthesizing system of the prior art comprises a polygonizer 322 and a Z-buffer 324 which is disposed in the image display unit 360. The Z-buffer 324 is an image memory having a memory space which corresponds to all the dots in the displayed scene. The image memory stores Z-value (distance from the view point) of each of the dots in a corresponding polygon. FIGS. 20A and 20B show the concept of the Z-buffer technique.
As shown in FIG. 20A, 3-D polygons X and Y in 3-D objects 300 and 301 are perspectively transformed onto a screen 306. According to such a procedure as shown in FIG. 20B, Z-values of the dots in the respective polygons are written in the Z-buffer 324.
In other words, the maximum Z-value M (usually, infinite value) is written in the Z-buffer 324 as an initial value. If the polygon X is to be drawn, it is judged for each dot in that polygon whether or not the Z-value of the polygon X is smaller than the Z-value stored in the Z-buffer 324 at each dot. If it is judged that the Z-value of the polygon X is smaller than that of a dot in the Z-buffer 324, that dot is color-painted by the polygonizer 322. In addition, the Z-value stored in the Z-buffer 324 at the corresponding dot is also updated. More particularly, all the Z-values of the corresponding parts will be updated from M to X1-X12.
If the polygon Y is to be drawn, the Z-buffer 324 is referred to for all the dots to be drawn. According to the same procedure as described above, the color painting will be carried out with the updating of the Z-buffer 324. More particularly, the Z-values X7, X8, X11 and X12 are updated respectively into Y1, Y2, Y5 and Y6 while the M-values in the parts of Z-buffer over which the polygon Y is drawn are updated into Y3, Y4, Y7, Y8-Y12. In other words, the Z-values at the parts of the polygon X overlapped by those of the polygon Y will be changed to the Z-values of the polygon Y since the polygon Y is located closer to the view point than the polygon X.
In the image display unit 360, each of the polygons is color painted according to the above procedure. The painted color data is transformed into RGB data by a palette circuit 328 and displayed on a CRT 330 as images.
Such image synthesizing systems are usually required to process images in real time. Image data for one scene (two scenes according to circumstances) must be updated for every field, for example, for every 1/60 seconds. Thus, the image synthesizing system is required to have an increased image processing speed. If the image processing speed is not increased, the quality of image will be reduced. The processing part of the image synthesizing system which is most used to increase the image processing speed is one for finally painting the dots with a given color.
This is because the polygonizer 322 must perform the processing step for all the dots in the displayed scene, unlike the image supply unit 308 of FIG. 19 which is only required to process the 3-D polygon for each vertex. More particularly, if the image display is to be made on a CRT of 640.times.400 pixels, all the dots equal to 640.times.400=256,000 must have been completely painted within one field or for 1/60 seconds. It is therefore preferable that a computation used to perform such a color painting is as simple as possible, with the number of computations being as small as possible.
In the Z-buffer technique, however, the color painting must be carried out by referring to the Z-buffer 324 to compare the Z-values at the respective dots with those stored in the Z-buffer, the comparison results being written in the Z-buffer. The computation used to make the color painting becomes a burden on the image synthesizing system. Therefore, the Z-buffer technique is unsuitable for use in performing the hidden surface removal in the image synthesizing system which should process high-quality images in real time.