ALCOMFT-TR-02-95

Tomas Plachetka
Perfect Load-Balancing (Demand-Driven) Parallel Ray Tracing
Paderborn. Work package 2. May 2002.

Abstract: A demand-driven parallelization of the ray tracing algorithm is presented. Correctness and optimality of a perfect load balancing algorithm for image space subdivision are proved and its exact message complexity is given. An integration of antialiasing into the load balancing algorithm is proposed. A distributed object database allows rendering of complex scenes which cannot be stored in the memory of a single processor. Each processor maintains a permanent subset of the object database as well as a cache for a temporary storage of other objects. A use of object bounding boxes and bounding hierarchy reduces the number of requests for missing data to a necessary minimum. The proposed parallelization is simple and robust. It should be easy to implement with any sequential ray tracer and any message-passing system. Our implementation is based on POV-Ray and PVM.

Postscript file: ALCOMFT-TR-02-95.ps.gz (1686 kb).