An efficient algorithm for hidden surface removal
- 1 July 1989
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGGRAPH Computer Graphics
- Vol. 23 (3) , 379-388
- https://doi.org/10.1145/74334.74372
Abstract
We give an efficient, randomized hidden surface removal algorithm, with the best time complexity so far. A distinguishing feature of this algorithm is that the expected time spent by this algorithm on junctions which are at the "obstruction level" l , with respect to the viewer, is inversely proportional to l . This provably holds for any input, regardless of the way in which faces are located in the scene, because the expectation is with respect to randomization in the algorithm, and does not depend on the input. In practice, this means that the time complexity is roughly proportional to the size of the actually visible output times logarithm of the average depth complexity of the scene (this logarithm is very small generally).Keywords
This publication has 10 references indexed in Scilit:
- A fast planar partition algorithm, IJournal of Symbolic Computation, 1990
- A fast planar partition algorithm, IIPublished by Association for Computing Machinery (ACM) ,1989
- Applications of random sampling in computational geometry, IIPublished by Association for Computing Machinery (ACM) ,1988
- Algorithms for diametral pairs and convex hulls that are optimal, randomized, and incrementalPublished by Association for Computing Machinery (ACM) ,1988
- An optimal algorithm for intersecting line segments in the planePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Worst-case optimal hidden-surface removalACM Transactions on Graphics, 1987
- Epsilon-nets and simplex range queriesPublished by Association for Computing Machinery (ACM) ,1986
- Lower bounds for algebraic computation treesPublished by Association for Computing Machinery (ACM) ,1983
- Hidden surface removal using polygon area sortingPublished by Association for Computing Machinery (ACM) ,1977
- A Characterization of Ten Hidden-Surface AlgorithmsACM Computing Surveys, 1974