“Hierarchical geometric models for visible-surface algorithms” by Clark

The research described in this paper addresses the problems associated with the design of systems for efficiently producing computer-generated pictures and picture sequences of very complex, three-dimensional environments. The thesis of the research is that the geometric structure inherent in the definition of the shapes of three-dimensional objects and environments must be used not just to define their relative motion and placement but also to assist in solving many other problems of systems for producing pictures by computer.The implications are that by using an extension of traditional structure information, or a geometric hierarchy, five significant improvements to current techniques are possible. First, the range of complexity of an environment is greatly increased while the visible complexity of any given scene is kept within a fixed upper limit. Second, a meaningful way is provided to vary the amount of detail presented in a scene both according to the screen area occupied by the objects in the scene and according to camera and object motions. Third, by using the geometric hierarchy, “clipping” becomes a very fast logarithmic search for the resolvable parts of the environment within the field-of-view. Fourth, by using this positional hierarchy in conjunction with a storage hierarchy of the sort used in virtual memory computing systems, frame-to-frame coherence and clipping define a graphical “working set”, or fraction of the total structure that should be present in primary store for immediate access by the visible-surface algorithms. Finally, the proposed structural framework suggests a new recursive descent visible-surface algorithm in which the computation time grows almost linearly with a scene’s visible complexity rather than as a worse than linear function of its object-space complexity.

1. Bouknight, W.J. A procedure for generation of three-dimensional half-toned computer graphics representations. Comm. ACM, 13, 9 (Sept. 1970), 527. 
2. Computer Aided Operations and Research Facility, U.S. Maritime Service Simulator (principal contractor Philco-Ford, visible-surface processor by Evans and Sutherland Comptr. Corp.).
3. Catmull, E. A subdivision algorithm for computer display of curved surfaces. Tech. Rep. UTEC-CSc-74-133, U. of Utah, Salt Lake City, Utah, Dec. 1974.
4. Clark, J.H. 3-D design of free-form B-spline surfaces. UTEC-CSc-74-120, Ph.D. Th., U. of Utah, Salt Lake City, Utah, (abridged version Designing surfaces in 3-D. Comm. ACM 19, 8 (Aug. 1976), 464-470.) 
5. Coons, S.A. Surfaces for computer-aided design of space forms. Project MAC TR-41., M.I.T., Cambridge, Mass., June 1967. 
6. Crow, F.C., and Bui-Tuong Phong. Improved Rendition of Polygonal Models of Curved Surfaces. Proc. Second USAJapan Comptr. Conf., Aug. 1975, p. 475.
7. Csuri, C. Computer animation, Computer Graphics 9, 1 (1975), 92-101 (Issue of Proc. Second Ann. Conf. Comptr. Graphics and Interactive Techniques). 
8. Denning, P.J. The working set model for program behavior. Comm. ACM, 11, 5 (May 1968), 323-333. 
9. Electonic scene generator expansion system. Final Rep., NASA Contract NAS 9-11065, Defense Electronic Div., General Electric Corp., Syracuse, N.Y., Dec. 1971.
10. Gouraud, H. Computer display of curved surfaces. IEEE Trans. Computers C-20 (June 1971), 623.
11. Nasa-Ames Short Take-off and Landing Simulator (built by Evans and Sutherland Comptr. Corp.).
12. New York Inst. Tech., Comptr. Animation Dep.
13. Newell, M. The utilization of procedure models in digital image synthesis. Ph.D. Th., Comptr. Sci., U. of Utah, Salt Lake City, Utah, 1975. 
14. Newell, M.E., NeweU, R.G., and Sancha, T.L. A new solution to the hidden-surface problem. Proc. ACM 1972 Ann. Conf., pp. 443-448. 
15. 15Bui-Tuong Phong. Illumination for computer generated pictures. Comm. ACM 18, 6 (June 1975), 311-317. 
16. Rediflow Flight Simulation, Ltd., NOVOVIEW Visual Systems (video system provided by E&S Comptr. Corp.).
17. Riesenfeld, R.E. Applications of B-spline approximation to geometric problems of computer aided design. Ph.D. Th., Syracuse U., Syracuse, N.Y., 1972. 
18. Schumacker, R.A., Brand, B., Gilliland, M., and Sharp, W. Study for applying computer-generated images to visual simulations. AFHRL-TR-69-74, US Air Force Human Resources Lab., Washington, D.C., Sept. 1969.
19. Sutherland, I.E. Sketchpad: a man-machine graphical communication system. TR 296, M.I.T Lincoln Labs, M.I.T., Cambridge, Mass., Jan. 1963.
20. Sutherland, I.E., Sproull, R.F., and Schumacker, R.A. A characterization of ten hidden-surface algorithms. Computing Surveys, 6, 1 (March 1974), 1-55. 
21. Watkins, G.S. A real-time visible-surface algorithm. UTECH- CSc-70-101, Ph.D. Th., Comptr. Sci. Dep., U. of Utah, Salt Lake City, Utah, June, 1970. 
22. Wipke, T., et al. Computer Representation and Manipulation of Chemical Information. Wylie Interscience, New York, 1974.
23. Wylie, C., Romney, R.S., Evans, D.C., and Erdahl, A. Halftone perspective drawings by computer. Proc. AFIPS 1967 FJCC, Vol. 31, AFIPS Press, Montvale, N.J., pp. 49-58.