“A 3-dimensional representation for fast rendering of complex scenes” by Rubin and Whitted

Hierarchical representations of 3-dimensional objects are both time and space efficient. They typically consist of trees whose branches represent bounding volumes and whose terminal nodes represent primitive object elements (usually polygons). This paper describes a method whereby the object space is represented entirely by a hierarchical data structure consisting of bounding volumes, with no other form of representation. This homogencity allows the visible surface rendering to be performed simply and efficiently. The bounding volumes selected for this algorithm are parallelepipeds oriented to minimize their size. With this representation, any surface can be rendered since in the limit the bounding volumes make up a point representation of the object. The advantage is that the visibility calculations consist only of a search through the data structure to determine the correspondence between terminal level bounding volumes and the current pixel. For ray tracing algorithms, this means that a simplified operation will produce the point of intersection of each ray with the bounding volumes. Memory requirements are minimized by expanding or fetching the lower levels of the hierarchy only when required. Because the viewing process has a single operation and primitive type, the software or hardware chosen to implement the search can be highly optimized for very fast execution.

1. Clark, J.H. Hierarchical geometric models for visible surface algorithms. CACM, 19-10, October 1976, pp. 547-554.
2. Reddy, D.R. and Rubin, S., Representation of three-dimensional objects, CMU-CS-78-113, Dept of Computer Science, Carnegie-Mellon University, April 1978.
3. Brooks, J. et al, An extension of the combinatorial geometry technique for modeling vegetation and terrain features, Mathematical Applications Group Inc., NTIS AD-782-883, June 1974.
4. Csuri, C. et al, Towards an interactive high visual complexity animation system, SIGGRAPH ’79 proceedings, August 1979, pp. 289-299.
5. Whitted, T., An improved illumination model for shaded display, to appear |CACM
6. Kay, Douglas S., Transparency, refraction and ray tracing for computer synthesized images, M.S. Thesis, Cornell University, January 1979.
7. Sutherland, I., Sproull, R., and Schumacher, R., A characterization of ten hidden surface elimination algorithms. ACM Computing Surveys, Vol. 6, No. 1, March 1974, pp. 1-55.
8. Forrest, A.R., On Coons and other methods for the representation of curved surfaces. Computer Graphics and Image Processing, vol 1, 1972.
9. Riesenfeld, R.F., Applications of b-spline approximation to geometric problem of computer aided design, PhD thesis, Syracuse University, 1972.
10. Newell, M., The utilization of procedure models in digital image synthesis, PhD Thesis, Computer Science, University of Utah, Salt Lake City, Utah, 1975.
11. Rosenfeld, A. and Kak, A.C., Digital Picture Processing, Academic Press, New York, 1976.
12. Kelly, M.D., Visual identification of people by computer, AIM-130, PhD Thesis, Computer Science, Stanford University, Stanford, Ca., July 1970.
13. Price, K. and Reddy, D.R., Matching segments of images, IEEE Trans. on Pattern Analysis and Machine Intelligence, 1 ,1, 1979, pp 110-116.
14. Catmull, E., A subdivision algorithm for computer display of curved surfaces, UTEC-CSc-74-133, PhD thesis, Computer Science Dept., Univ. of Utah, Dec. 1974.
15. Lane, J.M., Carpenter, L.C., Blinn, J.F., and Whitted, T., Scan Line Methods for Displaying Parametrically Defined Surfaces. CACM, 23-1, January 1980, pp. 23-34.