A comparison of spatial subdivision algorithms for sort-first rendering

This paper describes and experimentally evaluates three adaptive spatial subdivision heuristics for sort-first parallel graphics rendering on distributed-memory multicomputers. In sort-first rendering, imagespace, or screen, is divided into regions. Each processor is assigned one or multiple regions to render. Primitives in the scene are redistributed among the processors according to region assignments. The total number of primitives in the system may increase due to duplication of primitives crossing multiple regions assigned to different processors. The common characteristic of the algorithms discussed in this paper is that a 2-dimensional mesh is superimposed on the screen and screen is subdivided using the primitive distribution on this mesh. Each processor is assigned a single region to render. The first algorithm uses summed area table for subdividing the screen. The second algorithm uses quadtrees for subdivision. The third algorithm utilizes a graph partitioning approach. The second and the third algorithms are new approaches to adaptive screen subdivision in sort-first rendering. We compare the algorithms in terms of load balancing performance, execution time of the algorithms, and percent increase in the total number of primitives after redistribution step. In this paper, we do not target a specific rendering method such as polygon rendering or volume rendering. Our load balancing criteria is the number of primitives in each processor. We present experimental results on a Parsytec's CC parallel system.