Hierarchical geometric models for visible surface algorithms

ABSTRACT

The geometric structure inherent in the definition of the shapes of three-dimensional objects and environments is 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. 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. Third, “clipping” becomes a very fast logarithmic search for the resolvable parts of the environment within the field of view. Fourth, 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 algorithm. Finally, the geometric structure suggests a recursive descent, visible surface algorithm in which the computation time potentially grows linearly with the visible complexity of the scene.

REFERENCES

• 1: W. Jack Bouknight, A procedure for generation of three-dimensional half-toned computer graphics presentations, Communications of the ACM, v.13 n.9, p.527-536, Sept. 1970 [doi>10.1145/362736.362739]
• 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: James H. Clark, Designing surfaces in 3-D, Communications of the ACM, v.19 n.8, p.454-460, Aug. 1976 [doi>10.1145/360303.360329]
• 5: S. A. Coons, SURFACES FOR COMPUTER-AIDED DESIGN OF SPACE FORMS, Massachusetts Institute of Technology, Cambridge, MA, 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: Charles Csuri, Computer animation, Proceedings of the 2nd annual conference on Computer graphics and interactive techniques, p.92-101, June 25-27, 1975, Bowling Green, Ohio
• 8: Peter J. Denning, The working set model for program behavior, Communications of the ACM, v.11 n.5, p.323-333, May 1968 [doi>10.1145/363095.363141]
• 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: Martin Edward Newell, The utilization of procedure models in digital image synthesis., 1975
• 14: M. E. Newell , R. G. Newell , T. L. Sancha, A solution to the hidden surface problem, Proceedings of the ACM annual conference, August 01-01, 1972, Boston, Massachusetts, United States [doi>10.1145/800193.569954]
• 15: Bui Tuong Phong, Illumination for computer generated pictures, Communications of the ACM, v.18 n.6, p.311-317, June 1975 [doi>10.1145/360825.360839]
• 16: Rediflow Flight Simulation, Ltd., NOVOVIEW Visual Systems (video system provided by E&S Comptr. Corp.).
• 17: Richard Franklin Riesenfeld, Applications of b-spline approximation to geometric problems of computer-aided design., 1973
• 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: Ivan E. Sutherland , Robert F. Sproull , Robert A. Schumacker, A Characterization of Ten Hidden-Surface Algorithms, ACM Computing Surveys (CSUR), v.6 n.1, p.1-55, March 1974 [doi>10.1145/356625.356626]
• 21: Gary Scott Watkins, A real time visible surface algorithm, 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.

INDEX TERMS

Keywords:
geometric models, hidden surface algorithms, hierarchical data structures, visible surface algorithms