Kingston University
Jean-Christophe Nebel

Parallel Ray Tracing

Position: Research Assistant (PhD Project)

Funding: CEA

Duration: 1994-1997

Jump to: Project description | Keywords | Publications

Project description

The aim was the parallelization of the raytracing algorithm using MPPs and networks of workstations.

Ray tracing has become established as one of the most important and popular rendering techniques for synthesizing photo-realistic images. However, the high quality images require long computation times and memory-consuming scene description. Parallel architectures with distributed memories are increasingly being used for rendering and provide more memory and CPU power. This paper describes a new way to employ such computers efficiently for ray tracing. As here each pixel is processed independently, so natural method of parallelization is to distribute pixels over the machine nodes. If the entire scene can be duplicated in the memory of each processor (in the absence of global memory), a scheme without dataflow is used, otherwise, objects composing the scene have to be distributed over processor nodes. In this last case two strategies are applicable to the computation: object dataflow or ray dataflow. The fastest of these algorithms is the one without dataflow. If we want to deal with realistic pictures described by large scenes, we have to distribute objects among processors. Accordingly a choice has to be made between object and ray dataflow. This choice is not easy because of variability in computers, communication networks and scenes, also algorithms might not be based on the same sequential model. Here, we propose a method which chooses the type of flow to use dynamically. This arose from the development of a parallel ray tracing algorithm that included the two modes of dataflow, i.e. a concurrent dataflow algorithm. As our scheme allows the use of both algorithms, processors need to exchange objects and rays. The processors' load and some local parameters are used to choose between ray or object dataflow at any instant. Global information is transmitted by a non-centralized strategy, which assures scalability and the production of relevant messages. Finally, our algorithm offers a dynamic management of concurrent dataflows, which intrinsically assures dynamic load balancing. Our algorithm using concurrent dataflow gives very encouraging results, as the computation time for rendering pictures and the number of exchanged messages are reduced by significant factors in relation to classical dataflow algorithms. This concurrent algorithm is scalable as performances on a CRAY T3E with 128 processors shows. Finally the reduction of the magnitude of the flow of data communication reduces the risk of network saturation, which might otherwise compromise the algorithm.

Research interest keywords

computer graphics, parallelism, ray tracing, rendering  

Publications

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

1998

1997


Last updated on June 2004
j.nebel@kingston.ac.uk