Steven M. Rubin
Turner Whitted
ABSTRACT
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. Google Scholar
Digital Library
- 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.Google Scholar
- 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.Google Scholar
- 4.Csuri, C. et al, Towards an interactive high visual complexity animation system, SIGGRAPH '79 proceedings, August 1979, pp. 289-299. Google ScholarDigital Library
- 5.Whitted, T., An improved illumination model for shaded display, to appear |CACM Google ScholarDigital Library
- 6.Kay, Douglas S., Transparency, refraction and ray tracing for computer synthesized images, M.S. Thesis, Cornell University, January 1979.Google Scholar
- 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. Google ScholarDigital Library
- 8.Forrest, A.R., On Coons and other methods for the representation of curved surfaces. Computer Graphics and Image Processing, vol 1, 1972.Google Scholar
- 9.Riesenfeld, R.F., Applications of b-spline approximation to geometric problem of computer aided design, PhD thesis, Syracuse University, 1972. Google ScholarDigital Library
- 10.Newell, M., The utilization of procedure models in digital image synthesis, PhD Thesis, Computer Science, University of Utah, Salt Lake City, Utah, 1975. Google ScholarDigital Library
- 11.Rosenfeld, A. and Kak, A.C., Digital Picture Processing, Academic Press, New York, 1976. Google ScholarDigital Library
- 12.Kelly, M.D., Visual identification of people by computer, AIM-130, PhD Thesis, Computer Science, Stanford University, Stanford, Ca., July 1970. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
Index Terms
- A 3-dimensional representation for fast rendering of complex scenes
Recommendations
An improved illumination model for shaded display
SIGGRAPH '79: Proceedings of the 6th annual conference on Computer graphics and interactive techniquesTo accurately render a scene, global illumination information that affects the intensity of each pixel of the image must be known at the time the intensity is calculated. In a simplified form, this information is stored in a tree of “rays” extending ...
An improved illumination model for shaded display
SIGGRAPH '05: ACM SIGGRAPH 2005 CoursesTo accurately render a two-dimensional image of a three-dimensional scene, global illumination information that affects the intensity of each pixel of the image must be known at the time the intensity is calculated. In a simplified form, this ...
An improved illumination model for shaded display
To accurately render a two-dimensional image of a three-dimensional scene, global illumination information that affects the intensity of each pixel of the image must be known at the time the intensity is calculated. In a simplified form, this ...
Comments