Skip to main content

An efficient output-sensitive hidden-surface removal algorithm and its parallelization

Publication ,  Conference
Reif, JH; Sen, S
Published in: Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988
January 6, 1988

In this paper we present an algorithm for hidden surface removal for a class of polyhedral surfaces which have a property that they can be ordered relatively quickly like the terrain maps. A distinguishing feature of this algorithm is that its running time is sensitive to the actual size of the visible image rather than the total number of intersections in the image plane which can be much larger than the visible image. The time complexity of this algorithm is O((k +n) log n log log n) where n and k are respectively the input and the output sizes. Thus, in a significant number of situations this will be faster than the worst case optimal algorithms which have running time Ω(n2) irrespective of the output size (where as the output size k is O(n2) only in the worst case). We also present a parallel algorithm based on a similar approach which runs in time O(log4(n+k)) using O((n + k)/log(n+k)) processors in a CREW PRAM model. All our bounds are obtained using ammortized analysis.

Duke Scholars

Published In

Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988

DOI

ISBN

9780897912709

Publication Date

January 6, 1988

Start / End Page

193 / 200
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Reif, J. H., & Sen, S. (1988). An efficient output-sensitive hidden-surface removal algorithm and its parallelization. In Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988 (pp. 193–200). https://doi.org/10.1145/73393.73413
Reif, J. H., and S. Sen. “An efficient output-sensitive hidden-surface removal algorithm and its parallelization.” In Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988, 193–200, 1988. https://doi.org/10.1145/73393.73413.
Reif JH, Sen S. An efficient output-sensitive hidden-surface removal algorithm and its parallelization. In: Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988. 1988. p. 193–200.
Reif, J. H., and S. Sen. “An efficient output-sensitive hidden-surface removal algorithm and its parallelization.” Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988, 1988, pp. 193–200. Scopus, doi:10.1145/73393.73413.
Reif JH, Sen S. An efficient output-sensitive hidden-surface removal algorithm and its parallelization. Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988. 1988. p. 193–200.

Published In

Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988

DOI

ISBN

9780897912709

Publication Date

January 6, 1988

Start / End Page

193 / 200