Pixel merging for object-parallel rendering: A distributed snooping algorithm

In the purely object-parallel approach to multiprocessor rendering, each processor is assigned responsibility to render a subset of the graphics database. When rendering is complete, pixels from the processors must be merged and globally z-buffered. On an arbitrary multiprocessor interconnection network, the straightforward algorithm for pixel merging requires d^-A total network bandwidth per frame, where d^- is the depth complexity of the scene and A is the area of the screen or window. This algorithm is used by the Kubota Pacific Denali and appears to be used by the Evans and Sutherland Freedom series. An alternative algorithm, the PixelFlow algorithm, requires nA network bandwidth per frame, where n is the number of processors. But the merging is pipelined in PixelFlow so that each network link must only support A bandwidth per frame. However, that algorithm requires a separate special-purpose network for pixel merging. In this paper we present and analyze an expected-case log (d^-)A algorithm for pixel merging that uses network broadcast, and we discuss the algorithm´s applicability to shared-memory bus architectures