JP3036395B2 - Parallel execution of progressive radiosity - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a technique relating to high-quality image synthesis, and more particularly to a parallel execution method of progressive radiosity.

[0002]

2. Description of the Related Art Radiosity, an image synthesis technique, is one of the most advanced computer graphics algorithms. This image synthesis technique calculates the interaction of diffused light between the surfaces of objects in a screen description. Radiosity is applied to, for example, architectural model design and high-quality virtual reality (virtual reality), but there are many other fields of application. Images created by ray tracing show strong reflections and dark shadows for shiny objects, whereas images with radiosity show gentle shadows and color bleeding between diffuse surfaces. Since the processing of radiosity requires a wide range of computer processing, it is better to execute the algorithm on a parallel processor in order to increase the processing speed.

Thesis "Fast Radiosity by Parallelizatio
n "(in Photorealism in Computer Graphics, Eurogr
aphics Seminors, Springer-Verlag 1992 by W. Purgath
oferand M. Zeiller) has proposed a parallel execution of basic full matrix radiosity using a transputer network. However, this implementation does not utilize a more efficient progressive refinement algorithm.

[0004] Also, the paper "Acceleration Techniques for
Progressive Refinement Radiosity ”(Computer Graph
ics (1990 Symposium on Interactive 3D Graphics)
by RJRecker, DWGeorge and D. Greenberg) have proposed a progressive refinement algorithm implemented on a group of loosely coupled powerful workstations. Each workstation has a large amount of physical and virtual memory. The complete target database has been copied to the memory of each workstation. The server node selects one group of projection subsections and sends it to the client node, which returns the shape factor to the server node. However, the load parallelism is not as good as the proposed method because the particles in the partition are coarse. In addition, the paper “The Implementaion of an Extended Radiosity on th
e VOXARMachine ”(Transputer 92 Conf. Proc. IOS Pr
ess by J. Jessel and R. Caubet) proposes an augmented radiosity method implemented on a transputer-based multiprocessor voxar (Voxel Architecture). In this method, there are four types of light transfer types: diffusion to diffusion, specular reflection to diffusion, diffusion to specular reflection, and specular reflection to specular reflection. The target database is sent via the processing node. This method is based on a progressive refinement algorithm, and the selection of the projection subsection is performed in a quasi-parallel manner.

[0005]

As described above, to increase the processing speed, it is a good method to execute the algorithm by a parallel processor, but since the local program memory of the processing node is relatively small, The application program needs to be divided into smaller subroutines.

[0006]

According to the progressive radiosity parallel execution method of the present invention, a progressive radiosity parallel execution method for a processor array is provided in which a master node of the processor array includes an object divided into patches. Preprocesses the rendered screen description, transmits the preprocessed screen to each slave node in the processor array, and divides the screen into the patches
Selecting a projection subsection corresponding to each patch of the object , transmitting the projection subsection to the slave node , receiving a ray tracing result from the slave node,
Calculating the shape factor of the projection subsection, updating the luminosity of the patch, repeating the operation from the point of selection of the projection subsection until a specified number of repetitions is reached, transmitting the luminosity to the slave node, and host computer And transmitting the field-of-view parameter to the slave node, and repeating the operation from the point of receiving the field-of-view parameter until the host computer terminates an iterative loop. In the slave node, the pre-processing screen Receiving the projection subsection, performing ray tracing from the projection subsection to the screen, sending a result of the ray tracing to the master node, and performing an operation after receiving the projection subsection, the master node ending signal. Until the light is transmitted, receiving the light intensity, receiving the visual field parameter Ray tracing is performed from the field point which is a part of the field parameter to the screen, the result of the ray tracing is sent to the host computer, and the operation from the time of receiving the field parameter is sent by the master node to the end signal. It repeats until it does.

[0007]

The present invention is a parallel execution method of progressive radiosity, and applies ray tracing not only to hemispherical projection but also to final image rendering (plotting). MI
An MD (Multiple Instruction Multiple Data) processor array is composed of n processing nodes and one or several host nodes. The host node has an interface to the host computer and displays an image. One of the processing nodes is designated as a host node, and the remaining n-1 processing nodes are designated as slave nodes. The master node receives the screen description from the host computer and performs preprocessing of the object, that is, calculation of various object identification constants. Thereafter, the master node sends the preprocessed object to the slave node. Thus, each node contains a complete screen description. The masternode joins the progressive radiosity loop,
For each hemispheric projection, the projection subsection is sent to the slave node. The slave node traces light rays from the projection subsection to the screen. Each slave node is assigned a number of hemisphere lines in an interleaved order to improve load balancing. The number of each object hit by the ray is returned to the master node. The master node calculates a shape factor from the received object number.

[0008] After the progressive radiosity calculation, the screen intensity values are sent to the slave nodes so that the final rendering can be started. By performing ray tracing on the final rendering, the program code for projection can be reused. Thus, not only is the code compact, but it also supports four light transport types: diffuse to diffuse, specular to diffuse, diffuse to specular, and specular to specular.

[0009]

Embodiments of the present invention will be described with reference to the drawings.

FIG. 1 is a block diagram showing one embodiment of a processor array to which the progressive radiosity parallel execution method of the present invention is applied. The processor array includes n processing nodes 2, one or several host nodes 3 have an interface to a host computer 4, and the host computer 4 displays an image on a display 5. One of the processing nodes 2 is a master node 8
, And the remaining n−1 processing nodes are designated as slave nodes 7.

FIGS. 2, 3 and 4 are flow charters showing an embodiment of the progressive radiosity parallel execution method of the present invention. The operation of the present invention will be described with reference to FIG. The screen description is sent to the host computer (S2
1) Sent to the master node (S22). The master node receives the screen description (S31), and performs preprocessing of the object, that is, calculates various object specifying coefficients (S3).
2). Thereafter, the master node sends the pre-processed screen description to the slave node (S33). In this way, each node contains the entire screen. The slave node receives the pre-processed screen description (S41).

The master node enters a progressive radiosity loop, and for each hemispherical projection, a projection subsection is selected (S34) and sent to the slave node (S35). The slave node receives the projection subsection (S43), and traces a ray from the projection subsection to the screen (S44). To obtain good load balancing, each slave node is assigned a given number of semi-cube lines in interleaved order. The number of each object hit by the ray is returned to the master node. The master node calculates a shape factor from the received object number. The user's specified number of iterations determines when the progressive radiosity loop ends. The light intensity value of the object is sent to the slave node (S37), and the final rendering is enabled.

[0013] The visual field parameters are given by the user (S
23), and sent to the master node (S24). The master node receives the view parameter (S38), and the view parameter is sent to the slave node (S39). After receiving the luminous intensity of the object (S46), the slave node receives the visual field parameter (S47). Ray tracing is performed via a screen from a field point which is a part of the field parameters (S48). The final image pixel value is sent to the host computer (S49). The host computer receives the image pixel value from the slave node (S
25), an image is displayed. Thereafter, new view parameters can be specified and a new image can be created.

[0014]

According to the present invention, ray tracing is applied not only to half-cube projection but also to final drawing, and the program code size of the slave node is made compact. The master node performs preprocessing work and selection of a projection subsection, and the slave node performs actual ray tracing to realize efficient distribution of program code. A half-cube projection is performed by assigning many lines of a half-cube to each processing node in an interleaving order. Further, the speed is significantly increased by the parallel execution.

[Brief description of the drawings]

FIG. 1 is a block diagram showing one embodiment of a processor array to which the present invention is applied.

FIG. 2 is a flowchart showing an embodiment of the host computer side in the progressive radiosity parallel execution method of the present invention.

FIG. 3 shows an embodiment of the master node side in the progressive radiosity parallel execution method of the present invention.

FIG. 4 shows an embodiment of the slave node side in the progressive radiosity parallel execution method of the present invention.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 Processor array 2 Processing node 3 Host node 4 Host computer 5 Display 7 Slave node 8 Master node

Claims (4)

(57) [Claims] In a parallel execution method of progressive radiosity for a processor array, a master node of the processor array pre-processes a screen description composed of objects divided into patches, and processes the pre-processed screen by the processor. Communicate to each slave node in the array, and
Selecting a projection subsection corresponding to each patch, transmitting the projection subsection to the slave node , receiving ray tracing results from the slave node, calculating a shape factor of the projection subsection, and calculating a luminous intensity of the patch. Update and repeat the operation from the point of selection of the projection subsection until a specified number of repetitions is reached, transmit the luminous intensity to the slave node, receive a visual field parameter from a host computer, and transmit the visual field parameter to the slave node. The operation from the point of receiving the field-of-view parameter is repeated until the host computer ends an iterative loop, and in the slave node, the pre-processing screen is received , the projection subsection is received , and the screen is received from the projection subsection. Ray tracing to the master node, and sends the result of the ray tracing to the master node. The operation after receiving the minute is repeated until the master node sends an end signal, receiving the luminous intensity, receiving the visual field parameter, and performing ray tracing from a visual field point which is a part of the visual field parameter to the screen. Transmitting the result of ray tracing to the host computer, and repeating the operation from the time of receiving the view parameter until the master node sends an end signal. 2. The progressive radiosity of claim 1, wherein said ray tracing from said projection subsection to said screen is performed by assigning a number of semi-cubic lines to processing nodes in an interleaved order. Parallel execution method. Wherein the processor array, wherein the processor
N-1 slave nodes among the processing nodes of the array
A MIMD (Multiple Intraction Multiple Data) type processor array comprising one master node and one or more host nodes for interfacing the processor array with the host computer. 2. The parallel execution method of progressive radiosity according to 1. 4. The progressive radiosity parallel execution method according to claim 3, wherein said processing nodes are connected to four processing nodes by a communication link comprising a message transmission network.