The present invention relates to computer graphic techniques, in particular to an apparatus and a method for fast generating realistic pictures by using a data base storing data of objects in a virtual three-dimensional space.
The ray tracing method directs a ray from a visual point toward each picture element on a screen and sets an object which is hit by the ray as an object to be drawn on the picture element to which the color of the object is allocated. In color processing of the object, this method can render effects of optical attributes, such as the reflection or the refraction of the object on the color of the object drawn on the screen by using the colors of the reflected ray from another object or the refracted ray through another object. Therefore, this method can precisely express reflexes by the reflection or the refraction of other objects surrounding the object. The ray tracing method needs principally a process of searching for an object which is firstly hit (hereinafter the word "hit" is replaced with "intersect") by a shot ray, to every ray. Hereinafter, the process will be referred to as an intersection point searching process. It is well known that the major part of computing time in ray tracing is consumed in the intersection point searching process. The intersection point searching process needs calculation for each of the points intersected by all objects, and the total computing time of the intersection point searching process for making a picture is obtained by the following equation. ##EQU1## where (Ray number) is the number of rays needed to make a screen picture, (Object number) is the calculation number of intersection points of the objects and one ray and (Computing time of intersection points) is the computing time of an intersection point of a ray and an object.
The speeding up of the picture generating process, including the intersection point searching process, is an important subject. For example, the computer generated perspective pictures of the three dimensional arrangement of pipes and other components from various visual points are used in the piping design of buildings in a nuclear power plant. Since about a hundred thousand pipes and components exist in a building, it conventionally takes more than thirty minutes to generate a perspective picture. So it has been strongly desired to speed up the generation of such three dimensional pictures as mentioned above. The speed-up technique of the computing time of the intersection point searching process involves a method of reducing each term in the right hand side of Eq.(1). Especially, a method of reducing the term (Object number) is most effective and is known as what is called a fast processing method by space division (hereinafter referred to as the space subdivision method). Briefly the space subdivision method judges in advance whether the ray intersects an object and executes a precise calculation on the intersected object only in the case the ray intersects the object.
The octree subdivision method presented in the paper "Space Subdivision for Fast Ray Tracing" by Glassner, Andrew S., IEEE Computer Graphics and Applications, Vol. 4, No. 10, October 1984, pp. 15-22, is known as one of the space subdivision methods. The octree subdivision method divides the space including objects into 8 sub-spaces. In this method, the subdivision is continued until the number of the object included by a sub-space comes up to only one. The cells obtained in the above-mentioned way have a hierarchy structure by the unit of 8 leaves, which is generally called an octree.
And, as another space subdivision method, there is known the voxel subdivision method presented in the paper "ARTS: Accelerated Ray-Tracing System", by Akira Fujimoto, Takayuki Tanaka and Kansei Iwata, IEEE Computer Graphics and Applications, Vol. 6, No. 4, April 1986, pp. 16-26. Also in Japan Patent Laid Open 139890/1986, the voxel subdivision method is presented. The voxel subdivision method divides the space including all objects into equal parts. The processing speed of the voxel subdivision method is faster than that of the octree subdivision method since the space is equally divided. That is, the next cell calculation can be done by 3DDDA (3 Dimensional Digital Differential Analysis: calculation by one increment of an integer and one floating point addition in one calculation step). In the voxel subdivision method, the number of the cells to be searched is less than that of the octree method, even if the ray does not intersect an object.
Further, another subdivision method known as the hierarchy type voxel subdivision method is presented in the paper "Adaptive Voxel Subdivision for Ray Tracing", by David Jevans et al., Graphics Interface' 89, pp.164-172. The hierarchy type voxel subdivision variation is a variation of the generalized octree subdivision method. The method, at first, divides the space including all objects into equal parts and forms voxels. Next, the method again divides the cells more minutely if there exist cells in which the number of objects registered exceeds a predetermined number. The cell searching for the cells formed in the above-mentioned manner is carried out by the same algorithm as in the voxel subdivision method. The hierarchy type voxel subdivision method can process the cell searching faster than the above-mentioned other two methods since the method combines the advantageous points of the two methods.
The processing speed of the above-mentioned space subdivision methods strongly depends on the space distribution of the objects composing the 3D virtual space.
The octree subdivision method has the problem that its computing time is longer than that of the voxel subdivision method in the case the space distribution of the objects is uniform, since all octrees formed by the octree subdivision method need to be traversed by the ray. In one time of traverse, the traverse processing up and down on the tree structure is executed. Further, the octree subdivision method also needs more computing time than the voxel subdivision method when a scene (3 dimensional scene) is traversed by the ray, since many octree should be traversed in such a case. Especially, the trend becomes more remarkable when the ray penetrates a scene without an intersection point, since the ray traverse should be carried out for all octrees.
On the other hand, the voxel subdivision method has the problem that its processing speed is lower than that of the octree subdivision method when the space distribution of objects is localized. The localization of the space distribution means that more objects exist in local parts. In the process of searching intersection points in the cells, the intersection calculations with all objects registered in the cell is needed. When many objects are localized to one cell, the intersection calculation needs much time, since the computing time consumed by the intersection calculation is longer than that of the cell searching. Increasing the division number to avoid the-problem of the localization causes a decrease in the processing speed, since much computing time is consumed by the cell searching. The above-mentioned conventional voxel subdivision method in which the division number should be input by a user in advance has the problem that it is necessary to input the division number by a user's experience, corresponding to the space distribution of objects. The problem of the hierarchy type voxel method is that its processing performance depends on such factors as the initial division number, the predetermined threshold of the object number to further subdivision, the subdivision number after the first layer and the depth of the layer structure.