A worst-case efficient algorithm for hidden-line elimination†
- 1 January 1985
- journal article
- research article
- Published by Taylor & Francis in International Journal of Computer Mathematics
- Vol. 18 (2) , 93-119
- https://doi.org/10.1080/00207168508803482
Abstract
Many practical algorithms for hidden-line and surface elimination in a 2-dimensional projection of a 3-dimensional scene have been proposed. However surprisingly little theoretical analysis of the algorithms has been carried out. Indeed no non-trivial lower bounds for the problem are known. We present a plane-sweep-based hidden-line-elimination algorithm for 2-dimensional projections of scenes consiting of arbitrary polyhedra. It requires, in the worst case0(n log n) space and 0((n + k) log2 n) time, where n is the number of edges in the 3-dimensional scene, and k is the number of edge intersections in the specific projection.Keywords
This publication has 15 references indexed in Scilit:
- Solving visibility problems by using skeleton structuresPublished by Springer Nature ,2006
- A fast algorithm for the Boolean masking problemComputer Vision, Graphics, and Image Processing, 1985
- Plane-sweep algorithms for intersecting geometric figuresCommunications of the ACM, 1982
- Rectilinear line segment intersection, layered segment trees, and dynamizationJournal of Algorithms, 1982
- On the equivalence of some rectangle problemsInformation Processing Letters, 1982
- A Lower Bound on the Complexity of Orthogonal Range QueriesJournal of the ACM, 1981
- Frame-to-frame coherence and the hidden surface computationACM SIGGRAPH Computer Graphics, 1981
- Raster-scan hidden surface algorithm techniquesACM SIGGRAPH Computer Graphics, 1977
- A Characterization of Ten Hidden-Surface AlgorithmsACM Computing Surveys, 1974
- Binary Search Trees of Bounded BalanceSIAM Journal on Computing, 1973