JPH0679342B2 - Image generator - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION Industrial Field of the Invention The present invention relates to CAD (Computer Aided Design), CAM (Comp
uter Aided Manufacturing) and the like.

2. Description of the Related Art Algorithms for generating three-dimensional shapes from numerical values using a computer include scanline method, Z-buffer method, ray-tracing method.
tacing algorithm), but in particular, the document T. Whitt
ed `` An Illumination Model for Shaded Displa
y ”“ Communications of the ACM, June, 1980, Vol.23,
The ray tracing algorithm detailed in No. 6 "can generate a simple and realistic image. The outline will be described with reference to FIG.

In FIG. 2, 1 is a line of sight, 2 is an element (i,
j) 3 is a screen on which an object is projected, 4 and 5 are objects in a three-dimensional space, 6 is a viewpoint, 7 is an intersection, and 8 is a light source. The point of intersection between the line of sight 1 emitted from the viewpoint 6 and passing through the pixel (i, j) 2 on the screen 3 and the objects 4 and 5 is obtained, and the object closer to the viewpoint 6 is the object 4 in this case. , The brightness of the intersection 7 between the line of sight 1 and the object 4 is calculated according to the model of phong shown below, and the brightness of the pixel (i, j) 2 is calculated. By performing the above operation for all pixels,
Get the image.

phong model However, the drawback is that it takes a lot of time to determine the intersection with the object in the three-dimensional space and the huge calculation value is caused by performing the calculation for each pixel for all pixels.

As a method for compensating for this drawback, the literature Nishimura et al., "LINKS-1:
Computer Graphic System "(Information Processing Society of Japan Microcomputer Study Group Material, 24-1 (1982, 11, 2))
Then, by paying attention to the possibility of parallel processing inherent in the ray tracing algorithm, that is, the calculation of each pixel can be performed completely independently of other pixels, and by adopting large-scale parallel processing, Enormous calculation of is shortened. The basic structure of the LINKS _-1 is shown in FIG.
In FIG. 3, reference numeral 9 is a database, 10 is a root computer which is a control processor for controlling and monitoring a node computer, and 11 is a processor element which calculates the luminance of pixels in a small area of the screen using the ray tracing algorithm. A node computer, 12 is a data collector that collects the pixel intensities calculated in the node computer in a frame memory, 13 is a frame memory that stores the intensities collected by the data collector, and 14 is a CRT display that displays the contents of the frame memory. .

The numerical value indicating the object in the three-dimensional space, which is input to the database 9, is sent to the node computer 11 via the route computer 10. Then the root computer
10 is a node computer that divides the screen into small areas
Allocate to 11. The node computer generates an image of pixels in the allocated small area based on a ray tracing algorithm. The node computer, which has completed the image generation of the pixels in the allocated small area, requests the root computer to generate the small area which has not been generated. The brightness obtained by the node computer is stored in the frame memory 13 via the data collector 12 and displayed on the CRT 14. When all the node computers finish the image generation of the allocated small areas and there is no ungenerated small area, the image generation of one screen is ended.

Problems to be Solved by the Invention In the image generation system, since the calculation of all node computers is not completed at the same time, the effect proportional to the number of node computers is not obtained. Further, requests from the node computers to the root computer are concentrated for a period of time, and some of the node computers have a long waiting time for allocation, and in this respect, it is difficult to obtain an effect proportional to the number of computers.

Means for solving the problem Means for selecting a pixel obtained by sampling the screen with a certain roughness, means for obtaining the pixel calculation time and the calculation time value as the average calculation time of the small area including the pixel, An image generation method that consists of means for allocating a small area, which is divided into screens so that the calculation time of each node computer becomes equal based on the value, by each node computer.

Operation The present invention has the above-described method, and when the calculation time of the node computers becomes equal, the end of the calculation of each node computer becomes the same, and an effect proportional to the number of node computers is obtained.

Embodiment FIG. 1 is a flowchart of the present invention. The present invention will be described below with reference to FIG.

In FIG. 1, the root computer 10 in FIG. 3 starts up and the node computer 11 in FIG. 3 starts operating.

When an image is generated using the ray tracing algorithm, there is a high probability that the lines of sight of adjacent pixels intersect the same object. Therefore, the calculation time of a certain pixel can represent the average calculation time of the pixels in the small area including the pixel. Therefore, as shown in FIG. 1, the root computer 10 allocates coarse pixels to each node computer 11. FIG. 4 shows a screen composed of the rough pixel (i, j) 21 and the small area (i, j) 22 including the pixel (i, j) at this time. The broken line indicates the small area (i,
Indicates the boundary of j).

Lead computer 1 assigned to pixel (i, j) 21
1 performs image generation of the pixels shown in FIG.

The node computer 11 responds to the root computer with the calculation time of each pixel as shown in FIG. FIG. 6 is a graph in which the vertical axis represents the calculation time of each pixel (i, j) 21 and the horizontal axis represents each pixel (i, j) 21.

Next, in the root computer 10, each node computer 11 based on the previously calculated calculation time of the pixel (i, j) 21.
A small area (i,
j) Assign 22 to each node computer. The problem of equalization at this time is described in the document "Operating System Theor".
y (operating system theory) "(Edwar
d G. Coffman Jr., Peter J. Denning), NP-co
mplete (Non-Polynominal complete) That is, a heuristic method is required for a problem that cannot be solved in polynomial time. This typical method is based on LPT (Largest Proc
It is said to be a problem. In the LPT problem, when the allocation to the node computers 11 is decided in order from the one with the longest calculation time, the calculation time of each node computer 11 becomes the maximum optimal solution. It shows that it can be suppressed to. m indicates the number of node computers.

Next, the small area shown in FIG. 1 is allocated. Allocation from the root computer 10 to the node computer 11 is performed based on the equalized allocation obtained above.

Next, the node computer 11 executes the image generation of the allocated small screen based on the ray tracing algorithm.

Each node computer 11 notifies the root computer 10 that the image generation of the plurality of allocated small areas (i, j) 22 is completed.

Root computer 10 is all node computers
When the image generation of the plurality of small areas (i, j) 22 assigned with 11 is completed, the image generation of one screen is ended.

In the conventional technique, a small area (i,
j) 22 are allocated one by one, and when the image generation of the small area (i, j) 22 is completed, the next small area (i, j) 22 is allocated. If you increase the number of node computers 11, the parallel processing of only the number of node computers 11 will be possible, but at some point there will be competition for access to the root computer 10,
Since the response to the node computers 11 becomes poor, even if the number of node computers is increased, the number of parallel processes will not be the same.

However, if this method is used, the problem of the response of the root computer 10 to the node computer 11 can be avoided while the image generation is being executed because the entire screen area is allocated at one time. As a result, an effect proportional to the number of node computers 11 can be obtained.

EFFECTS OF THE INVENTION As is apparent from the above description, according to the present invention, access competition of node computers to the root computer does not occur. In addition, it is possible to generate images at high speed without waiting for node computers to be allocated.

Further, since there is no waiting for allocation, the number of node computers that execute image generation can be significantly increased, and images can be generated at high speed in proportion to the number.

[Brief description of drawings]

FIG. 1 is a flowchart of processes from No. O to No. n of a root computer and a node computer, FIG. 2 is a diagram showing a ray tracing algorithm, FIG. 3 is a conventional image generation system diagram, and FIG. The figure is a simplified diagram of the generated image. Fig. 5 is a diagram showing a split screen. Fig. 6 is a diagram showing the distribution of the calculation time of pixel (i, j). Fig. 7 is the calculation time of each node computer. It is a figure which shows the distribution of. 9 ... Database, 10 ... Root computer, 11 ...
… Node computer, 12 …… Data collector, 13 ……
Frame memory, 14 …… CRT display.

Claims (4)

[Claims] 1. An area dividing means for dividing a screen into a plurality of small areas when an image of a screen is generated, a plurality of processor elements for executing image generation of pixels in each of the small areas, and the processor element. A device used for image generation, which is connected via a bus or a shared memory and includes a control processor that controls and monitors the processor element, and an estimating unit that roughly calculates a calculation time required for image generation of each of the small areas, An image generation apparatus comprising: a region allocation unit that allocates a plurality of small region calculations to each processor element so that the calculation time of each processor element becomes equal based on the calculation time calculated by the approximate calculation unit. 2. The image generating apparatus according to claim 1, wherein the area allocating means allocates to the processor elements in order from a small area having a long calculation time obtained by the estimating means. 3. The image generating apparatus according to claim 1, wherein the processor element uses a ray tracing algorithm to generate an image of pixels. 4. The calculation means for calculating an image of a certain pixel is set as an approximate calculation time of a small area including the pixel by the rough calculating means, in any one of claims 1 to 3. An image generation device according to claim 1.