“Special purpose automatic programming for hidden surface elimination” by Goad

In many applications of three dimensional computer graphics, the appearance of the same scene must be computed repeatedly for many different positions of the viewer. This paper concerns a scheme for exploiting this property of an application for the purpose of improving the efficiency of the hidden surface computation. The scheme involves a kind of automatic programming: for each scene to be considered, a different special purpose program is automatically constructed. The special purpose program then takes the position of the viewer as input, and generates a suitable description of the scene with hidden surfaces removed as output. Since the special purpose program has a very limited task to perform – it is adapted to handling just one scene – it can be much faster than any general purpose algorithm would be for the same scene. The paper describes a method by which special purpose programs for hidden surface elimination can be constructed in a fully automatic manner. The method has been implemented, and results of experiments are given.

1. Beckeman,L., Haraldsson, A., Oskarsson,O., and Sandewall, E.{1976}, A partial evaluator and its use as a programming tool, Artificial Intelligence Journal 7,1976, pp. 319-357
2. Burstall R.M., and Darlington, J.{1977}, A transformation system for developing recursive programs, JACM, Vol. 24, No. 1, January 1977
3. Fuchs, H., Kedem, Z.M., and Naylor, B.F.{1980}, On visible surface generation by a priori tree structures, Computer Graphics, Vol. 14, No. 3, July 1980,p. 124
4. Knuth, D.E.{1968}, The art of computer programming, vol 1: Fundamental algorithms, Addison-Wesley, Reading Mass., 1968, pp. 258-268
5. Newell, M.E., Newell, R.G., and Sancha, T.L.{1972}, A new approach to the shaded picture problem, Proc. ACM National Conference, 1972
6. Robson, J.{1979}, The height of binary search trees, The Australian Computer Journal, 11(1979), pp 151-153
7. Sutherland, I.E.,Sproull, R.F., and Schumacker, R.A.{1974}, A characterization of ten hidden-surface algorithms, Computing Surveys, Vol. 6, No. 1, March 1974
8. Yao, F.F{1980}, On the priority approach to hidden surface algorithms, Proc. 21st Symposium on Foundations of Computer Science, October 1980