Optimal Processor Allocation for Sort-Last Compositing under BSP-tree Ordering

C. R. Ramakrishnan, Claudio T. Silva


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 support 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. Many known rendering algorithms, such as volumetric ray casting and polygon rendering can be easily parallelized based on the structure of the BSP-tree. 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 compositing 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 describe the implementation details and provide experimental evidence of the validity of our techniques in practice.

Bibtex Entry:

author = {C. R. Ramakrishnan and  Claudio T. Silva},
title = {Optimal Processor Allocation for Sort-Last Compositing under BSP-tree Ordering},
booktitle = {Visual Data Exploration and Analysis VI, Electronic
series = {Proceedings of SPIE Vol},
volume = {3643},
month = {January},
year = {1999}

Full Paper: [pdf]

Home | Papers

C. R. Ramakrishnan