Abstract
In computer graphics, it is well known that the radiosity method can generate high quality image for diffuse environments. But it suffers from extensive computation and requires a great amount of memory. As parallel computing environments become widely available, it is natural to exploit parallel computation to speed up radiosity computations. Recently, several parallel algorithms for the radiosity problem have been proposed, however, most existing parallel algorithms are designed for simple scenes and based on ad hoc parallel architectures. In this thesis, we propose a general parallel hierarchical radiosity algorithm for complex scenes based on distributed computing environments. To achieve the generality, the computation structure is primarily designed on a parallel model machine, however, we will show that the parallelism can be easily realized on a set of homogeneous or heterogeneous machines with message passing capability. Data volume and geometry complexity are two major factors that distinguish simple scene algorithm from that of complex scene. For example, in a complex scene, such as an architectural building, the complexity of each room is unpredictable, and the data size is usually greater than available memory size. To cope with these problems and to obtain good performane on a distributed computing environment, the following issuses are proposed and studied in this thesis, namely, scene partitioning, job scheduling, load-imbalance, data redundancy, and communication overhead. Furthermore, several techniques such as visibility buffer operations, distributed shooting and scene block scheduling are proposed in this study to eliminate redundant computations and to reduce communication overhead. In order to demonstrate the feasibility and the performance of our algorithm, we implemented our parallel algorithm on the PVM (Parallel Virtual Machine) programming environment which has been ported to many commercially available machines to form a distributed computing system. The experiment results show that our parallel algorithm is efficient in the aspect speed up parameters. Moreover, some performance issues and further improvement are also addressed.