“A graph-theoretic real-time visible surface editing technique” by Tanimoto

Efficient visible surface (hidden surface) algorithms must make use of information about the structure of the environment, constraints on viewpoint locations and the coherence between successive views in a sequence. Here the visible surface problem is posed as a problem in graph theory. A new technique based on ‘updating cut-sets in a graph is presented as a means to streamline the culling of back faces during visible surface computations. The technique can be used for general environments that contain some convex polyhedra. Since the method saves the most computation when convex polyhedra having many faces appear in the environment, it is particularly appropriate for handling geodesic domes and polyhedral approximations to spheres. A direct extension for nonconvex polyhedra is suggested.

1. Jones, C. B., A new approach to the “hidden-line” problem. Computer Journal Vol. 14, No. 3, (Aug. 1971), pp. 232-237.
2. Sutherland, I. E., Sproull, R. F., and Schumacker, R. A., A characterization of ten hidden-surface algorithms. Computing Surveys Vol. 6, No. 1, (March 1974), pp. 1-55.
3. Schumacker, R. A., Brand, B., Gilliland, M. and Sharp, W., Study for applying computer-generated images to visual simulation. AFHRL-TR-69-14, U.S. Air Force Human Resources Laboratory (Sept. 1969).
4. Warnock, J. E., A hidden-surface algorithm for computer-generatedhalftone pictures. Computer Science Dept., University of Utah, TR 4-15 (June 1969).
5. Roberts, L. G., Machine perception of three-dimensional solids. MIT Lincoln Laboratory, TR 315 (May 1963).
6. Watkins, G. S., A real-time visible surface algorithm. Computer Science Dept., University of Utah, UTECH-CSC-70-101, (June 1970).
7. Loutrel, P. P., A solution to the hidden-line problem for computer-drawn polyhedra. IEEE Trans. Comput. C-19, 3, (March 1970) p. 205.
8. Galimberti, R. and Montanari, U., An algorithm for hidden line elimination. Comm. A.C.M. Vol. 12, No. 4, (April 1961), pp. 206-211.
9. Bouknight, W. J., A procedure for generation of half-tone computer graphics representations. Comm. A.C.M. Vol. 13, No. 9, (Sept. 1970) p. 527.
10. Bramall, R., Three dimensional data display with hidden line removal. TR CSRG-12, University of Toronto. (April 1972).
11. Clark, J. H., Hierarchical geometric models for visible surface algorithms. Comm. A. C. M. Vol. 19, No. 10 (Oct. 1976) pp. 547-554.
12. Tanimoto, S. L., An iconic/symbolic data structuring scheme, Pattern Recognition and Artificial Intelligence, Academic Press, N. Y. 1976, pp. 452-471.
13. Cheston, G. A., Incremental algorithms in graph theory, Techn. Rept. No. 91, University of Toronto, Dept. of Computer Science (March 1976).
14. Newell, M. E., Newell, R. G., and Sancha, T. L. A new approach to the shaded picture problem. Proc. ACM National Conf., 1972.
15. Busacker, R. G. and Saaty, T. L., Finite Graphs and Networks, McGraw-Hill, N. Y., 1965.
16. Newell, M. E., The utilization of procedural models in digital image synthesis. Ph.D. dissertation, Computer Science Dept., University of Utah, 1975.