A flexible algorithm for multiprocessor ray tracing

Ray tracing programs are widely used to generate photo-realistic images, bu t the high computation time may discourage their implementation on single-p rocessor machines; moreover, cost reduction of multi-processor general purp ose architectures makes parallel rendering an attractive field of research. We propose a new algorithm which addresses the main issues of a parallel i mplementation of ray tracing on a message-passing-based machine. We adopt e fficient strategies for dynamic workload distribution among processors, tas k synchronization and communication delay reduction. The resulting implemen tation is highly flexible, since any number of processors can be employed w ithout introducing synchronization problems. We show an implementation of o ur algorithm on an nCUBE 2 supercomputer which is a general purpose paralle l architecture with distributed memory. A theoretical evaluation of our alg orithm allows us to identify a decreasing function for rendering times; the considered examples confirm the theoretical expectations showing that the efficiency of our system may reach up to the 91% of the value achievable by dividing the sequential rendering time by the number of processors employe d.