“An efficient algorithm for hidden surface removal” by Mulmuley

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).

1. Ben-Or M., “Lower bounds for algebraic computation tres”, Pro,. o} the 15th STOG, 83.
2. Chazelle B., Edelsbrunner It., “An optimal algorithm for intersecting line segments in the plane”, Proceedings of the FOCS, 1988.
3. Clarkson K., “Applications of random sampling to computational geometry, II”, Pro,. 4th Ann. ACM Symposium on Computational Geom., 1988.
4. Clarkson K., Shor P., “Algorithms for diametral pairs and convex hulls that axe optimal, randomized, and incremental”, Proc. 4th Ann. A CM Symposium on Computational Geometry, 1988.
5. ttamlin G., Gear C., “Raster-Scan hidden surface algorithm techniques”, Computer Graphics, vol. i1, no. 2, pp. 1206-213.
6. Haussler D., Welzl E., “Epsilon nets and simplex range queries”, Pro,. 2nd Ann. A CM Symposium on Computational Geometry, 86.
7. Mckenna M., “Worst-case optimal hidden surface remowl algorithm”, ACM transactions on graphics, vol.6, no. 1, 1987.
8. Mulmuley K., “A fast planar partition algorithm, I”, Proceedings of the 29th FOCS, 1988, full version to appear in a special computational geometry issue of the Journal of Symb. Logic.
9. Mulmuley K., “A fast planar partition algorithm, II”, To appear in the Proceedings of the 5th Ann. ACM symposium on Computational Geometry, 89, full version submitted to JACM.
10. Mulmuley K., “On levels in arrangements and Voronoi diagrams”, Technical report, TR 88-21, University o} Chicago, December,88, submitted to the Journal of Discrete and Computational Geom.
11. Mulmuley K., “An efficient algorithm for hidden surface removal, I’, a complete manuscript.
12. Mulmuley K., “An efficient algorithm for hidden surface removal, II”, in preparation.
13. Newell M., Newell R., Sancha T., “A new approach to the shaded picture problem”, Proc. ACM. National Conf., 1972.
14. Schmitt A. “Time and space bounds for hidden line and hidden surface algortithms’, Eurographics, 81.
15. Sutherland, I. E., R. F. Sproull, and R. A. Schumaker, “A characterization of ten hidden surface algorithms”, Computing Surveys 6: 1-55, 1974.
16. Warnock J., “A hidden surface algorithm for computer generated half-tone pictures”, computer science dept., University o} Utah, TR J-15, 1969.
17. Weiler K., Athetton P., “Hidden surface removal using polygon axes sorting”, computer graphics (Proc. SIGGRAPH), July, 77.