JPH0814853B2 - Load balancing processing method for parallel ray tracing - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Outline] When the light emitted from a light source hits an object and is reflected to reach a viewpoint, the light is reflected on a two-dimensional screen provided on a passage between the object and the viewpoint. It relates to so-called ray tracing (ray tracing method) in which a two-dimensional image of an object is obtained by drawing a point having a brightness corresponding to the brightness of the In distributed execution of ray tracing including smoothing image processing), in order to solve the load variation on each processor of the parallel computer, the calculation processing of several sub-pixels in one pixel, which is performed in the anti-aliasing processing, By sharing the load among several processors, the load on each processor is equalized.

TECHNICAL FIELD The present invention relates to a ray tracing distributed processing method including anti-aliasing processing in a parallel computer.

Ray tracing including anti-aliasing is an excellent algorithm for generating realistic images, but it is disadvantageous in that it requires enormous processing time.
Therefore, in recent years, attention has been paid to the inter-pixel independence of ray tracing processing, and parallel ray tracing in which a plurality of processor processings are dispersed has been attempted.

In this case, a distribution method that makes the processing distributed to each processor uniform is required.

[Prior Art] FIG. 4 shows a conventional ray tracing distributed processing method including anti-aliasing processing on a parallel computer. In the figure, (a) shows a screen screen, in which the divided pixels are shared by 16 parallel computers. The same figure (b) shows 16 parallel computers numbered from 0 to 15, and the numbers in the figure (a) show the corresponding computers. FIG. 3C is a diagram showing a case where one pixel is divided into four to form four sub-pixels A, B, C, and D.

In the conventional method, each processor is assigned to each pixel and the processing work is evenly distributed, paying attention to the fact that ray tracing can be calculated independently for each pixel.

However, in order to remove the gathering of the object boundary on the display image in the anti-aliasing process,
As shown in FIG. 3C, four virtual pixels (sub-pixels) finer than one pixel are taken for each pixel, and the average value of these four sub-pixels is displayed as the value of one pixel. Therefore, sub-pixels within one pixel take an average value, and complete independent processing cannot be performed in sub-pixel units. The processor in charge of the pixel sequentially calculates the sub-pixels in the pixel and displays the average value, and then shifts to the processing of the next pixel in charge.

[Problems to be Solved by the Invention] In a conventional ray tracing distributed processing method including anti-aliasing processing on a parallel computer, a processor in charge of a pixel sequentially calculates sub-pixels in the pixel and displays an average value. After that, since the processing was moved to the next pixel processor, the processing distribution between the processor that was in charge of a large number of pixels with a large amount of processing such as a specular body and the processor that was in charge of a large amount of background. There are variations. That is, in the anti-aliasing process, simply 1
There is a problem that the number of sub-pixels per pixel is doubled.

The present invention has been made in view of the above circumstances, and a plurality of processors share the processing of calculating sub-pixels of several points under one pixel, which is performed in the anti-aliasing processing. It is an object of the present invention to provide a load balancing processing method of parallel ray tracing capable of equalizing the above load.

[Means for Solving Problems] FIG. 1 is a flowchart showing the principle of the method of the present invention. The present invention provides a load balancing processing method for parallel ray tracing, which executes ray tracing processing including anti-aliasing processing by using a parallel processor,
First, one pixel forming an image is divided into a plurality of sub-pixels (step), a status memory indicating how many sub-pixels are currently the average value is provided for each sub-pixel (step), and each processor is pixel-parallelized. In addition, the sub-pixels of the anti-aliasing processing are assigned (step), and each processor averages the processing results individually according to the contents of the status memory (step).
It is characterized by doing so.

[Operation] FIG. 2 is a diagram showing a state of processing sharing of the processor according to the present invention. In the figure, the portion surrounded by the solid line corresponds to the display pixel, and the four portions divided by the broken line for each of them are anti-aliasing sub-pixels. That is, one display pixel is composed of four sub-pixels. In the method of the present invention, in order to make the load of ray tracing including the anti-aliasing processing uniform among the processors, the processor is assigned to each sub-pixel unit of the anti-aliasing processing. In addition to the RGB information of each pixel, the video memory has a status memory indicating the average value of the number of sub-pixels for each pixel at present.

When each processor finishes the calculation of the sub-pixel in charge,
From the target pixel of the video memory, read the contents of the status memory indicating how many subpixels are currently averaged. If it is "0", the calculation result is written as it is to the target pixel of the video memory. If "1", the content of the target pixel of the video memory and the calculation result are averaged, and if "2", the content of the target pixel of the video memory is doubled, the value of the calculation result is added and divided by 3. Then, the average value according to the number of sub-pixels is sequentially accumulated.

In the present invention, by distributing the processing to each processor in sub-pixel units of the anti-aliasing processing, the ray tracing processing including the anti-aliasing processing is distributed to each processor in pixel units. It is possible to improve the point that the load variation between the processor that is in charge of a large number of pixels with a lot of reflections and the processor that does not, is increased by a multiple of the number of sub-pixels.

[Example] Hereinafter, an example of the present invention will be described in detail with reference to the drawings. FIG. 3 is a main part configuration diagram showing an embodiment for realizing the method of the present invention. In the figure, 21 is a group of 16 processors (designated by numbers 0 to 15).
22 is a pixel address selection circuit, 23 is a color / sub-pixel selection circuit, and 24 is a video memory. Each of the 16 processors
Under the control of a host computer (not shown), a ray tracing program and data are given, and a sub-pixel address in charge is given from the pixel address selection circuit 22, and the processing proceeds independently. In each processor, when the assigned sub-pixel calculation is completed, the color / sub-pixel selection circuit 23 is used to read from the video memory 24 the current average number of sub-pixels in the pixel.

If the average number read is "0", the calculation result is written in the video memory 24 as it is. At the same time, "1" is written as the average number of sub-pixels. When the average number of times of reading is "1", the content (data) of the pixel in the video memory 24 and the calculation result are obtained, and the value is written in the video memory. At the same time, "2" is written as the average number of sub-pixels.

When the average number of times of reading is "2", the content of the video memory is doubled and the calculation result is added to this, and the calculation result is divided by 3 to obtain an average value, which is written in the video memory. At the same time, “3” is written as the average number of sub-pixels.

When the average number of times of reading is 3, the content of the video memory is tripled, the calculation result is added to this, and the calculation result is divided by 4 to obtain an average value, which is written in the video memory. When the value averaged four times is written, the processing of the pixel is completed.

The content of the sub-pixel is RGB information, but the process of obtaining the average value is performed for each RGB signal.

Further, each processor may perform the above processing in any order. The order is usually managed by the host computer. In this way, by sharing the processing of one pixel by a plurality of processors, it is possible to eliminate variations in the load on the processors.

Although the number of divisions of one pixel is four in the embodiment, it may be another number. Further, the present invention is not necessarily limited to color images, but can be applied to monochrome images.

Furthermore, the number of processors in charge of each sub-pixel is not limited to 16 as in the embodiment, and the number may be arbitrarily increased or decreased.

[Effects of the Invention] As described in detail above, according to the present invention, the load generated in the conventional method in which the ray tracing process including the anti-aliasing process is distributed to each processor in pixel units. Not only solves the problem that the variation increases by a multiple of the number of sub-pixels, but also does not perform anti-aliasing processing because multiple processors share sub-pixels within pixels that have almost the same load size. It will also be improved in terms of load equalization ratio for ray tracing.

Further, in the conventional method, the image display is delayed because the image is not displayed until the calculation of the sub-pixel is completed and the average value is calculated. However, in the method of the present invention, one pixel of the sub-pixels is displayed. There is an advantage that the image is displayed immediately after the calculation is completed, and the image is sequentially changed to the image subjected to anti-aliasing as the number of times the sub-pixel is calculated.

[Brief description of drawings]

FIG. 1 is a flowchart showing the principle of the method of the present invention.
FIG. 3 is a diagram showing a state of processing sharing of a processor according to the present invention, FIG. 3 is a configuration diagram of an essential part showing an embodiment for realizing the method of the present invention, and FIG. 4 is an anti-ariy on a conventional parallel computer. It is a figure which shows the distributed processing method of ray tracing including an ashing process. In the figure, 21 ... Parallel processor group, 22 ... Pixel address selection circuit, 23 ... Color / subpixel selection circuit, 24 ... Video memory.

Continuation of the front page (56) Reference JP-A-61-133482 (JP, A) JP-A-59-65888 (JP, A) JP-A-62-260276 (JP, A) JP-A-61-86876 (JP , A)

Claims (1)

[Claims] 1. A load distribution processing method of parallel ray tracing for executing ray tracing processing including anti-aliasing processing by using a parallel processor, wherein one pixel constituting an image is divided into a plurality of sub-pixels (steps). A status memory is provided for each sub-pixel to show how many sub-pixels are currently averaged (step), each processor is arranged in parallel with each other, and each sub-pixel for anti-aliasing processing is allocated (step). According to the contents of the status memory
A load balancing processing method for parallel ray tracing, characterized by averaging the processing results individually (steps).