PROPOSAL FOR RESEARCH
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 .
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:
- 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
- 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."  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
- How can these adaptations be incorporated into an existing
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.
- 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.
I have taken several courses that have prepared me for this study as
an honors student in Computer Science. Most significantly, in Data
Structures (CMSC420) I began the study of spatial data structures and
how they can be used to more efficiently process two- and
three-dimensional information. As a result, I have become extremely
interested in this field of study. Additionally, through prior work
experience, I have had some exposure to the importance of realistic
images and the time it takes to generate these images. I look forward
to the opportunity to do this research as part of the Seniors Summer
- Glassner, Andrew S. Introduction to Ray Tracing.
Academic Press Limited. 1989.
- Samet, Hanan. The Design and Analysis of Spatial Data
Structures. Addison-Wesley Publishing Company, Inc. 1990.