A Hypercube Ray-tracer

Abstract

We describe a hypercube ray-tracing program for rendering computer graphics. For small models, which fit in the memory of a single processor, the ray-tracer uses a scattered decomposition of pixels to balance the load, and achieves a very high efficiency. The more interesting case of large models, which cannot be stored in a single processor, requires a decomposition of the model data as well as the pixels. We present algorithms for constructing a decomposition based upon information about the frequency with which different elements of the model are accessed. The resulting decomposition is approximately optimized to minimize communication and achieve load balance.