TO:            Selection Committee, Seniors Summer Scholars

FROM:      Maria E. Jump

DATE:        March 20, 1998

SUBJECT:  Effects of Using Hierarchical Data Structures on the Implementation of an Adaptive Ray Tracer

Graphics are used in virtually every aspect of computer science from user interfaces to data visualization to television commercials and motion pictures. As computers become more powerful, the demand for more realistic graphics continues to grow. As a result, computer graphics and the creation of realistic images in a timely manner is one of the most exciting and rapidly growing computer fields.

One of the simplest methods for image synthesis started with an idea from physics. Here, photons of light starting at their source are traced through a scene. This process is called ``ray tracing.'' Because of its simplicity and elegance, ray tracing is considered one of the best overall synthesis techniques available [1].

Consider the world around you, every surface, texture, shadow, irregularity of surrounding objects adds complexity to the image that you see. This is the fundamental difficulty in using a computer to create images with a high degree of visual realism. The ultimate goal is to create an image that is indistinguishable from a photograph. To achieve this using ray tracing techniques, millions of rays, representing individual photons of light, need to be cast for even the smallest image. Each photon must be followed as it travels through the scene requiring significant processing power and, consequently, large amounts of computer time on conventional machines.

In order for realistic computer-generated graphics to become more prominent, the computational time is of utmost importance. Certainly nobody wants to sit and wait 15-60 seconds for a computer to generate an image that is only the size of a postage stamp, regardless of the realism that this image possesses. Let alone the hours that it would take to get the same degree of realism in an image that is the size of a photograph. Thus a great deal of study is being conducted to devise techniques for speeding up this process.

One possible approach would be to develop an Adaptive Ray Tracer (ART) as a method for varying the densities of rays in order to concentrate the greatest number of rays in areas of greatest interest. In order to develop an ART, several questions must be addressed:

1. What constitutes an area of interest?
   Using traditional ray casting techniques, the rays to be cast are known. This is not the case in an ART. An ART requires that a general but flexible mathematical model be developed to determine that an area is sufficiently interesting to warrant a higher degree of rays.
2. What data structures can be used for efficient ART?
   In The Design and Analysis of Spatial Data Structures, Dr. Hanan Samet of the University of Maryland states that "Hierarchical data structures are useful because of their ability to focus on the interesting subsets of data. This focusing results in an efficient representation and in improved execution times." [2] Since the basic problem in developing an ART is the problem of selecting interesting subsets of data, hierarchical data structures, such as octrees, k-d trees, and binary space partition (BSP) trees, will be evaluated for their effectiveness for solving this problem.
3. How can these adaptations be incorporated into an existing rendering engine?
   The traditional method for performing the ray tracing operation is to shoot rays in a one-to-one correspondence with the pixels of the final image. In an ART this would not be the case. As rays are shot with varying densities, a dual meaning is given to a low density of photons. The difficulty that arises is how to distinguish between a low density of photons indicating low interest and a low density of photons indicating low light.
4. How does ART affected the computational time?
   The final step is to evaluate the effectiveness of an ART in reducing the computational time while maintaining visual realism by comparing it to traditional ray tracing techniques. To accomplish this, a profiler will be used to measure CPU time. In addition, as an interesting "machine independent" measurement of ART's performance, the numbers of nodes of the data structure that are visited will be counted.

Background

References

1. Glassner, Andrew S. Introduction to Ray Tracing. Academic Press Limited. 1989.
2. Samet, Hanan. The Design and Analysis of Spatial Data Structures. Addison-Wesley Publishing Company, Inc. 1990. p. vii.