Interactive-rate animation generation by parallel progressive ray-tracing on distributed-memory machines

We describe a dynamic load-balancing algorithm for ray-tracing by progressi ve refinement on a distributed-memory parallel computer. Parallelization of progressive ray-tracing for single images is difficult because of the inhe rent sequential nature of the sample location generation process, which is optimized (and different) for any given image, Parallelization of progressi ve ray-tracing when generating image sequences at a fixed interactive rate is even more difficult, because of the time and synchronization constraints imposed on the system. The fixed frame rate requirement complicates matter s and even renders meaningless traditional measures of parallel system perf ormance (e.g., speedup). We show how to overcome these problems, which, to the best of our knowledge, have not been treated before. Exploiting the tem poral coherence between frames enables us to both accelerate rendering and improve the load-balance throughout the sequence. Our dynamic load-balance algorithm combines local and global methods to account not only for renderi ng performance, but also for communication overhead and synchronization iss ues. The algorithm is shown to be robust to the harsh environment imposed b y a time-critical application, such as the one we consider. (C) 2000 Academ ic Press.