An improved output-size sensitive parallel algorithm for hidden-surface removal for terrains

Gupta, Neelima ; Sen, Sandeep (1998) An improved output-size sensitive parallel algorithm for hidden-surface removal for terrains ACM Int'l Parallel Processing Symp . No pp. given.

[img]
Preview
PDF - Author Version
74kB

Official URL: http://ipdps.cc.gatech.edu/1998/papers/092.pdf

Abstract

We describe an efficient parallel algorithm for hiddensurface removal for terrain maps. The algorithm runs in O(log4 n) steps on the CREW PRAM model with a work bound of O((n + k)polylog(n)) where n and k are the input and output sizes respectively. In order to achieve the work bound we use a number of techniques, among which our use of persistent data-structures is somewhat novel in the context of parallel algorithms. To the best of our knowledge this is the most efficient parallel algorithm for hidden-surface removal for an important class of 3-D scenes.

Item Type:Article
Source:Copyright of this article belongs to ACM Int'l Parallel Processing Symp.
ID Code:90079
Deposited On:04 May 2012 14:29
Last Modified:19 May 2016 04:24

Repository Staff Only: item control page