In:
International Journal of Pattern Recognition and Artificial Intelligence, World Scientific Pub Co Pte Ltd, Vol. 06, No. 02n03 ( 1992-08), p. 417-436
Abstract:
This paper describes the parallel implementation of the Z-Buffer algorithm on a distributed memory machine. The Z-Buffer is one of the most popular techniques used to generate a representation of a scene consisting of objects in a three-dimensional world. We propose and compare two different parallel implementations on a reconfigurable network of Transputers. In the first approach, the description of the scene is distributed among the processors configured as a tree. The picture is processed in a pipelined fashion, in order to output parts of the image during the computation of the remainder. We show the influence of the degree and the height of the tree on the global performance of the algorithm. In a second approach, both the picture and the scene description are distributed to the processors. We have therefore to redistribute dynamically the tiles among the processors at the beginning of the computation. To perform this redistribution, a special algorithm is designed for the case where the processors are configured as a unidirectional or bidirectional ring. Then we implement a greedy algorithm that enables us to perform the redistribution on an arbitrary interconnection network. We show that the two approaches are complementary: for small pictures or large scenes, a tree-based algorithm performs better than a redistribution-based algorithm, but for large pictures or smaller scenes, it is the other way round. We obtain substantial speedups over the sequential implementation, with up to 32 processors.
Type of Medium:
Online Resource
ISSN:
0218-0014
,
1793-6381
DOI:
10.1142/S0218001492000254
Language:
English
Publisher:
World Scientific Pub Co Pte Ltd
Publication Date:
1992
Permalink
