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

Abstract

We describe an efficient parallel algorithm for hiddensurface removal for terrain maps. The algorithm runs in O(log⁴ 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.