{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T21:49:23Z","timestamp":1648936163193},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"02n03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Patt. Recogn. Artif. Intell."],"published-print":{"date-parts":[[1992,8]]},"abstract":"<jats:p> 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. <\/jats:p>","DOI":"10.1142\/s0218001492000254","type":"journal-article","created":{"date-parts":[[2004,11,24]],"date-time":"2004-11-24T19:50:24Z","timestamp":1101325824000},"page":"417-436","source":"Crossref","is-referenced-by-count":0,"title":["IMPLEMENTATION OF THE Z-BUFFER ALGORITHM ON A RECONFIGURABLE NETWORK OF PROCESSORS"],"prefix":"10.1142","volume":"06","author":[{"given":"JIAN-JIN","family":"LI","sequence":"first","affiliation":[{"name":"Laboratoire de l'Informatique du Parall\u00e9lisme LIP-IMAG, Ecole Normale Sup\u00e9rieure de Lyon, 69364 Lyon Cedex 07, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"SERGE","family":"MIGUET","sequence":"additional","affiliation":[{"name":"Laboratoire de l'Informatique du Parall\u00e9lisme LIP-IMAG, Ecole Normale Sup\u00e9rieure de Lyon, 69364 Lyon Cedex 07, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"YVES","family":"ROBERT","sequence":"additional","affiliation":[{"name":"Laboratoire de l'Informatique du Parall\u00e9lisme LIP-IMAG, Ecole Normale Sup\u00e9rieure de Lyon, 69364 Lyon Cedex 07, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"container-title":["International Journal of Pattern Recognition and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218001492000254","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T22:15:28Z","timestamp":1565129728000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218001492000254"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,8]]},"references-count":0,"journal-issue":{"issue":"02n03","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[1992,8]]}},"alternative-id":["10.1142\/S0218001492000254"],"URL":"https:\/\/doi.org\/10.1142\/s0218001492000254","relation":{},"ISSN":["0218-0014","1793-6381"],"issn-type":[{"value":"0218-0014","type":"print"},{"value":"1793-6381","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,8]]}}}