Optimal Processor Allocation for Sort-Last Compositing Under BSP-Tree Ordering

In this paper, we consider a parallel rendering model that exploits the fundamental distinction between rendering and compositing operations, by assigning processors from specialized pools for each of these operations. Our motivation is to supports the parallelization of general scan-line rendering algorithms with minimal effort, basically by supporting a compositing back-end (i.e., a sort last architecture) that is able to perform user-controlled image composition. Our computational model is based on organizing rendering as well as compositing processors on a BSP-tree, whose internal nodes we call the compositing tree. With such a compositing tree, most known rendering algorithms, such a volumetric ray casting, polygon rendering, and so on, can be easily parallelized. In such a framework, it is paramount to minimize the processing power devoted to compositing, by minimizing the number of processors allocated for composition as well as optimizing the individual compositing operations.
In this paper, we address the problems related to the static allocation of processor resources to the composting tree. In particular, we present an optimal algorithm to allocate compositing operations to compositing processors. We also present techniques to evaluate the compositing operations within each processor using minimum memory while promoting concurrency between computation and communication. We provide experimental evidence of the validity of our techniques in practice