\S Introduction

This paper surveys the ray tracing papers I have obtained. Abstracts of the
papers have been entered and classified by certain topics. If a paper does not
have an abstract, I entered some other part of the paper or briefly summarized
the paper myself. While this document is public domain, remember the abstracts
and papers are copyrighted by the authors/publishers.

If you know of a paper not in this document, send the abstract or paper to the
address above (I would prefer getting the paper). Because of the constant
``finding'' of new and old papers, this collection will be updated
periodically. If you think a paper should be reclassified, your suggestions are
welcome. A paper will only be classified in one area even if it covers several
topics.

My comments appear in [\ ]. Each section has papers arranged by date first and
then by first author's last name. Ordering of sections was done arbitrarily.
I do not have a copy of a paper whose reference is followed by '*'. I hope you
find this as useful as I thought it might be.

There is a new subsection: \E Basic Ray Tracing\}.

\S Ray Tracing

\s The Ray Tracing Technique

\R Appel, Arthur. ``Some Techniques for Shading Machine Renderings of
Solids.'' \B AFIPS Spring Joint Computer Conference\}, 1968, p. 37-45.

\A
[No abstract. Excerpt from Introduction]

This paper presents some recent experimental results in the automatic shading
of line drawings. The purpose of these experiments was to generate pictures
of objects consisting of flat surfaces on a digital plotter and to evaluate
the cost of generating such pictures and the resultant graphical quality.

\R Goldstein, Robert A., and Roger Nagel. ``3-D Visual Simulation.'' \B
Simulation\}, January 1971, p. 25-31.

\A
This paper describes a visual simulation technique by which fully
computer-generated perspective views of three-dimensional objects may by
reproduced. The method is based on a relatively simple geometric modeling
technique for the mathematical representation of the three elements essential
to the picture-taking process, namely, a camera, a light source, and the object
or objects to be photographed. Once these three basic components have been
defined, geometric ray tracing is employed to compute a ``picture'' of the
object as it appears in the simulated camera. In essence, individual light rays
are traced from their sources to the surface of the object. The reflected
component of each ray is computed and traced to its point of intersection with
the film plane. Thus, each reflected ray provides the intensity at a single
point on the picture, and, when a sufficient number of points have been
computed, the entire area of intensity data may be displayed on a cathode ray
tube. Several are shown, and the application to the computer-generated films is
discussed.

\R Kay, Douglas Scott, and Donald Greenberg. ``Transparency for Computer
Synthesized Images.'' \B SIGGRAPH '79\}, p. 158-164.

\A
Simple transparency algorithms which assume a linear transparency over an
entire surface are the type most often employed to produce computer synthesized
images of transparent objects with curved surfaces. Although most of the images
created with these algorithms do give the impression of transparency, they
usually do not look realistic. One of the most serious problems is that the
intensity of the light that is transmitted through the objects is generally not
proportional to the amount of material through which it must pass. Another
problem is that the image seen behind the objects is not distorted as would
naturally occur when the light is refracted as it passes through a material of
different density.

Use of a non-linear transparency algorithm can provide a great improvement in
the realism of an image at a small additional cost. Making the transparency
proportional to the normal to the surface causes it to decrease towards the
edges of the surface where the path of the light through the object is longer.
The observer, through the picture plane and through each transparent object
until an opaque surface is intersected. Since the direction of the ray would
change as each material of differing optical density was entered, the hidden
surface calculations required would be very time consuming. However, if a few
assumptions are made about the geometry of each object and about the conditions
under which they are viewed, a much simpler algorithm can be used to
approximate the refractive effect. This method proceeds in a back to front
order, mapping the current background image onto the next surface, until all
surfaces have been considered.

\R Kay, Douglas Scott. \B Transparency, Refraction and Ray Tracing for
Computer Synthesized Images\}, Masters Thesis, Cornell University, 1979.

\A
Computer synthesized images of transparent objects often do not appear to be
realistic. The problems associated with producing such images are discussed and
some simple methods of improvement are offered. In particular, a refraction
algorithm is presented that adds little complexity to the standard transparency
algorithm and greatly improves the images created.

When sufficiently complex environments are modeled, realistic images can only
be produced if the subtle interactions such as reflections, refractions and
shadows are considered. This can be accomplished with the ray tracing method
presented. The deviations from a theoretically correct model are discussed, a
practical system is detailed and images from a limited implementation are
presented.

\R Whitted, Turner. ``An Improved Illumination Model for Shaded Display.''
\B CACM\}, Vol. 23, \#6, June 1980, p. 343-349. Also appears in \B Tutorial:
Computer Graphics: Image Synthesis\}, Kenneth I. Joy, Charles W. Grant, Nelson
L. Max, and Lansing Hatfield (eds.), Computer Society Press, Washington, 1988,
p. 132-138.

\A
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 information is stored in a tree of ``rays'' extending
from the viewer to the first surface encountered and from there to other
surfaces and to the light sources. A visible surface algorithm creates this
tree for each pixel of the display and passes it to determine the intensity
of the light received by the shader to accurately simulate true reflection,
shadows, and refraction, as well as the effects simulated by conventional
shaders. Anti-aliasing is included as an integral part of the visibilty
calculations. Surfaces displayed include curved as well as polygonal surfaces.

\R Davis, Jonathan Earl. \B Recursive Ray Tracing for the Realistic Display of
Solid Models\}, M.S.M.E. Thesis, Purdue University, May 1982. *

\A
One of the roles of computer-aided-design is the visualization of a designed
part or an entire assembly of parts. Hidden surface algorithms are used on
geometric data to determine a realistic rendering of a created model on a
raster graphics device.

An image synthesis algorithm with an advanced shading method is implemented
and evaluated. Rays are traced from an observer's position. These rays
encounter surfaces and spawn additional rays toward other surfaces and the
light sources. A tree of rays is created containing surface intersection data
for each picture element on the raster screen. A shading algorithm traverses
the tree recursively and computes the color and intensity of light reflected.
This method is known as a ray tracing algorithm and evaluates only a single
pixel at any given time.

The advantage of a ray tracing algorithm is the use of a global shading model.
The global shading model incorporates the environment surrounding the
intersected surface and can reproduce the optical effects of diffuse
reflection, specular reflection, specular reflections between surfaces,
transparency, refraction, and shadows from multiple light sources. These
subtle effects greatly enhance the realism of an image.

The ray tracing algorithm is designed to render images of solid models
prepared by a solid geometric modeler. A geometric model can be displayed on a
raster device with the global illumination effects of true reflection,
refractions, and shadows from multiple light sources.

\R Roth, Scott D. ``Ray Casting for Modeling Solids.'' \B Computer Graphics
and Image Processing\}, Vol. 18, 1982, p. 109-144.

\A
This paper presents ray casting as the methodological basis for a CAD/CAM solid
modeling system. Solid objects are modeled by combining primitive solids, such
as blocks and cylinders, using the set operators union, intersection, and
difference. To visualize and analyze the composite solids modeled, virtual
light rays are cast as probes. By virtue of its simplicity, ray casting is
reliable and extensible. The most difficult mathematical problem is finding
line-surface intersection points. So surfaces such as planes, quadrics, tori,
and probably even parametric surface patches may bound the primitive solids.
The adequacy and efficiency of ray casting are issues addressed here. A fast
picture generation capability for interactive modeling is the biggest
challenge. New methods are presented, accompanied by sample pictures and CPU
times, to meet the challenge.

\R Bouville, Christian. ``Image Synthesis Through Ray Tracing.''
\B Banc-Titre\}, Mar. 1985, p. 50-51.

\A
[No abstract. Very brief introduction to ray tracing.]

\R Amanatides, John. ``Realism in Computer Graphics: A Survey.'' \B IEEE
CG\&A\}, January 1987, p. 44-56.

\A
This article surveys most of the major issues to be dealt with when generating
realistic images, and covers papers up to December 1985. It begins with an
overview of the rendering process and a quick review of visible
surface-determination algorithms. Then, in more detail, it discusses shading,
antialiasing, texture mapping, shadows, and optical effects and closes with a
discussion of modeling primitives.

\R Kuchkuda, Roman. ``An Introduction to Ray Tracing.'' \B Theoretical
Foundations of Computer Graphics and CAD\}, NATO ASI Series, Vol. F40,
Springer-Verlag, 1988, p. 1039-1060.

\A
This paper is a practical guide to ray tracing for those familiar with
graphics. It consists of a conceptual model of ray tracing, C code for a basic
system, and an explanation of how and why the code works.

\R Schmitt, Alfred, Heinrich M\"uller, and Wolfgang Leister. ``Ray Tracing
Algorithms --- Theory and Practice.'' \B Theoretical Foundations of
Computer Graphics and CAD\}, NATO ASI Series, Vol. F40, Springer-Verlag, 1988,
p. 997-1030.

\A
This paper gives a survey on recent advances in making ray tracing a practical
technique for realistic image synthesis from spatial scenes. First, the
structure of the Karlsruhe ray tracing software VERA is described as an example
of practical ray tracing. Then a comprehensive analysis of worst case time
bounds of the ray tracing procedure and of some related algorithms, e.g.\ the
visible surface reporting algorithm, is carried out.

\R Glassner, Andrew S., James Arvo, Robert L. Cook, Eric Haines, Pat Hanrahan,
Paul Heckbert, and David B. Kirk. \B An Introduction to Ray Tracing\}.
Academic Press, San Diego, 1989.

\A
[No abstract. The following is taken from the back cover summary.]

The creation of realistic 3-D images is one of the most powerful applications
of computer graphics. The ray tracing technique has quickly become one of the
popular approaches to creating synthetic images. The algorithm is simple,
elegant, and easily implemented by the professional and novice programmer
alike. Ray tracing is a powerful tool both for understanding image rendering,
and for creating new pictures.

\B An Introduction to Ray Tracing\} begins with the basic ideas of ray
tracing, and builds to a survey of the state-of-the-art in efficient
implementations. Along the way the book covers basic algorithms in depth, and
reviews important material from surface physics, the geometry of shapes and
surfaces, and a detailed analysis of the intersection routines at the heart of
every ray tracing program. The book is heavily illustrated with color and
black-and-white figures. This book will be welcomed by anyone interested in
the art and science of creating realistic 3-D computer graphics for
applications ranging from science to art.

[This is THE source for ray tracing. It references just about every important
paper published before 1988.]

\R Glassner, Andrew S. ``Ray Tracing for Realism.'' \B Byte\}, December 1990,
p. 263-271.

\A
[No abstract. Beginner-level explanation of the ray tracing technique.]

\R Wilson, Thomas B. \B Ray Tracing Techniques\}. M. S. Thesis, Computer
Science Department, University of Central Florida, 1989.

\A
This thesis provides a survey of the many techniques applicable to ray
tracing. Ray tracing is a popular image synthesis technique that provides very
realistic images. Unfortunately, the various methods remain scattered
throughout the literature. Thus, this thesis solves the problem by bringing a
large number of these references together in one paper.

First, an overview of other image rendering algorithms is presented as well as
a brief survey of popular shading techniques and object representations. The
ray tracing technique is introduced, and its initial advantages and
disadvantages are described. The remainder of the survey presents improvements
and other extensions to the basic ray tracing algorithm and object
representations.

\s Basic Ray Tracing

\R Whitted, Turner. ``Processing Requirements for Hidden Surface
Elimination and Realistic Shading.'' \B IEEE Digest of Papers, COMPCON\},
Spring 1982, p. 245-250.

\A
Synthesis of realistic pictures requires enormous amounts of computing power.
An analysis of the various image making operations shows that each element
that contributes to realism also adds substantially to the processing costs.
Although the efficiency of the operations can be improved, performance
breakthroughs are rare.

\R Bouville, Christian, R. Brusq, J. L. Dubois, and I. Marchal. ``Generating
High Quality Pictures by Ray-Tracing.'' \B Computer Graphics Forum\}, 4 (1985),
p. 87-99. Also appears in \B Proceedings of Eurographics '84\}, Ketil B\o and
Hugh A. Tucker (eds.), p. 161-177.

\A
Ray-casting techniques provide a very general framework in which many problems
can be solved in a much easier way than with conventional methods. This is
particularly true for the illumination model when a high level of realism is
required. Another interesting feature of ray-casting is its ability to display
a wide class of algebraic surfaces with a minimum of approximations. Both
aspects are developed in this paper where a full lighting model, based on a
theoretical approach, is presented. Then, an algorithm for the display of
surfaces of revolution is described.

\s Textbooks and Other Sources

\R Rogers, David F. \B Procedural Elements for Computer Graphics\},
McGraw-Hill Book Company, New York, 1985.

\R Magnenat-Thalmann, Nadia, and Daniel Thalmann. \B Computer Animation:
Theory and Practice\}, Springer-Verlag, 1985.

\R Magnenat-Thalmann, Nadia, and Daniel Thalmann. \B Image Synthesis:
Theory and Practice\}, Springer-Verlag, 1987.

\R Haines, Eric, n\E et al\}. \B Ray Tracing News\}. Electronic newsletter,
1988-1990, available from erich@eye.com.

\R Burger, Peter, and Duncan Gillies. \B Interactive Computer Graphics:
Functional, Procedural, and Device-Level Methods\}. Addison-Wesley Publishing
Company, Reading, Massachusetts, 1989.

\R Hall, Roy. \B Illumination and Color in Computer Generated Imagery\},
Springer-Verlag, 1989.

\R Salmon, Rod, and Mel Slater. \B Computer Graphics: Systems \& Concepts\}.
Addison-Wesley Publishing Company, Reading, Massachusetts, 1989.

\R Watt, Alan. \B Fundamentals of Three-Dimensional Computer Graphics\},
Addison-Wesley Publishing Company, Reading, Massachusetts, 1989.

\R Foley, James D., Andries Van Dam, Steven K. Feiner, and John F. Hughes.
\B Computer Graphics, Principles and Practice\}, Second Edition, Addison-Wesley
Publishing Company, Reading, Massachusetts, 1990.

\R Glassner, Andrew S. (ed.). \B Graphics Gems\}, Academic Press, Inc., San
Diego, 1990.

\R Hill, Francis S., Jr. \B Computer Graphics\}. MacMillian Publishing Company,
New York, 1990.

\R Samet, Hanan. \B Applications of Spatial Data Structures: Computer
Graphics, Image Processing, and GIS\}, Addison-Wesley, 1990.

\S Image Synthesis Systems

\R Hall, Roy A., and Donald P. Greenberg. ``A Testbed for Realistic Image
Synthesis.'' \B IEEE CG\&A\}, November 1983, p. 10-20.

\A
[No abstract. Excerpt from end of paper]

As we have shown here, Cornell University's testbed image synthesis system
has helped in the development of a number of improvements of existing
ray-tracing techniques. In summary, these include a hybrid reflection model,
a spectral-sampling method, the incorporation of light sources, and adaptive
tree-depth control. Nevertheless, we point out again that many of the problems
of realistic image generation through ray tracing have not been solved. The
inherent point-sampling technique is prone to aliasing, the reflection models
proposed do not include the correct energy formulations, and the computational
expense is currently too high. The use of environmental image coherence
techniques would probably make these approaches more tractable. It is our hope
that the testbed imaging system will provide an appropriate environment for
further exploration of these problems.

\R Peachey, Darwyn R. ``PORTRAY - An Image Synthesis System for Realistic
Computer Graphics.'' Research Report 84-18, Department of Computational
Science, University of Saskatchewan, 1984.

\A
Image synthesis is an area of computer graphics that addresses the problem of
generating a synthetic image resembling a photograph of a real scene. The
input to an image synthesis program is a symbolic description of the objects
in the scene and the other factors (camera position and orientation, light
sources, etc.) that influence the image. This report describes the design and
use of an image synthesis system called PORTRAY, which generates realistic
pictures of three-dimensional scenes using a technique known as ``ray tracing.''

\R van Wijk, J. J., and F. W. Jansen. ``Realism in Raster Graphics.'' \B
Computers and Graphics\}, Vol. 8, \#2, 1984, p. 217-219.

\A
[No abstract. Describes the RAYMO renderer.]

\R Kitaoka, Shoichi. ``Experimental CSG Environment for Modelling Solid.''
\B The Visual Computer\}, Vol. 2, 1986, p. 9-14.

\A
The purpose of this research is to develop an experimental environment for
solid modelling which can provide a wide range of graphics primitives and
operations toward making the modelling process more flexible. The system can
handle different types of representations and combine them with an
extended-CSG structure. A new geometric editor to enter and modify the data
is also reported. To handle different types of representation, the system has
an object-oriented structure and the idea of a `common function' is introduced
to give the interface between them. Ray tracing is used as the rendering
method. New techniques for generating images for complex objects are shown
with several modelling examples.

\R Peachey, Darwyn R. ``PORTRAY - An Image Synthesis System.'' \B
Proceedings of Graphics Interface '86/Vision Interface '86\}, p. 37-42.

\A
PORTRAY is an image synthesis system which uses ray tracing to produce
realistic images of three-dimensional scenes. Scenes are described to PORTRAY
in a high-level description language. The basic geometric modelling technique
is constructive solid geometry using primitive solids bounded by planes and
quadrics. A variety of optical characteristics and phenomena may be specified.
The scene description language allows the user to define object \E classes\}
which may be used as if there were built-in primitives. PORTRAY uses a number
of techniques, including a novel technique exploiting bounding volume
coherence, to improve its ray tracing performance. PORTRAY is supported by an
array of image manipulation tools which share a common image storage format.

\R Marsh, Donald M. ``UgRay: An Efficient Ray-Tracing Renderer for
UniGrafix.'' Report No. UCB/CSD 87/360, Computer Science Division (EECS), UC
Berkeley, May 1987.

\A
Ray-tracing has proven to be an elegant and versatile algorithm in the pursuit
of increased realism in computer-generated images. In order to reduce the
computational expense of general ray-tracing, we utilize a uniform spatial
subdivision. We report on a number of practical issues in designing a
ray-tracing renderer, including a fast algorithm for inserting polygons into
the spatial subdivision, results of optimizations to the ray/polygon intersect
routine, and inexpensive shading and antialiasing routines.

\R Kirk, David, and James Arvo. ``The Ray Tracing Kernel.'' \B Proceedings
of Ausgraph '88\}, p. 75-82.

\A
We describe a methodology for implementing a ray tracer which provides both a
convenient testbed for developing new algorithms and a way to exploit the
growing number of acceleration techniques. These benefits are a natural
consequence of a collection of data abstractions called the ``ray tracing
kernel.'' By defining an ``object'' in a broad sense, the kernel allows a
single abstraction to encapsulate a wide spectrum of concepts including
geometric primitives, acceleration techniques, CSG operators, and object
transformations. Through hierarchical nesting of instances of these objects
we are able to construct and efficiently render complex environments.

\R Leister, W., Th. Maus, H. M\"uller, B. Neidecker, and A. St\"o\ber.
```Occursus Cum Novo' -- Computer Animation by Ray Tracing in a Network.'' \B
New Trends in Computer Graphics, Proceedings of CG International '88\}, Nadia
Magnenat-Thalmann and Daniel Thalmann (eds.), Springer-Verlag, p. 83-92.

\A
The goal of the project ``Occursus Cum Novo'' was to generate a complex
photo-realistic animation of nontrivial length in reasonable time at
reasonable costs. Photographic realism comprises complex geometric models as
well as simulation of several optical effects. This paper starts with an
introduction to the ``Occursus Cum Novo'' modeling environment. Following
the toolkit approach, it offers a set of tools for textual, graphical
interactive, and simulative modeling, embedded in the UNIX programming
environment. The second part is devoted to rendering. Photo-realistic
pictures generated by raytracing are still those of highest quality. However,
due to the tremendous time of computation, raytraced animations are rather
rare. An organization scheme for rendering on a network of work stations is
described which enabled us to generate a 5-minute raytraced animation within
2 months without affecting any of the regular users of the work stations. The
results of the project are of general interest since they show a way for
efficient high quality photo-realistic animation synthesis for the future.

\R St\"o\ber, Achim, Alfred Schmitt, Burkhard Neidecker, Heinrich
M\"uller, Thomas Maus, and Wolfgang Leister. ```Occursus Cum Novo' -- Tools
for Efficient Photo-Realistic Computer Animation.'' \B Proceedings of
Eurographics '88\}, David A. Duce and Pierre Jancene (eds.), p. 31-41.

\A
The goal of the project ``Occursus Cum Novo'' was to generate a complex
photo-realistic animation of nontrivial length in reasonable time at reasonable
cost. Photographic realism comprises complex geometric models as well as the
implementation of several optical effects. Both can be achieved by simulation.
Simulations guaranteeing high quality, as ray tracing does for rendering, are
known to be very time consuming. They require the design of powerful data
structures and algorithms taking the abilities of today's hardware into account.
The first part of this paper is devoted to rendering, here carried out by the
raytracing method. An organizing scheme for a network of work stations is
described which enabled 5-minutes of ray traced animation to be generated
within 2 months without affecting any regular user of the work station. The
second part is devoted to the simulative modeling tools applied in ``Occursus
Cum Novo.'' The recursive generator WAXI and a motion simulator METAMORPHOSIS
are described to some detail. The results of the project are of general
interest since they show a way leading to efficient high quality
photo-realistic animation synthesis in the future.

\R Williams, Tom. ``Graphics System Designers Strive for Photorealism.''
\B Computer Design\}, August 1, 1988, p. 50-61.

\A
[No abstract. This is not a technical paper. It describes how ray tracing and
radiosity are incorporated into low cost, interactive graphics systems.]

\R Cleary, John G., Brian Wyvill, and Geoff Wyvill. ``Ray Tracing in Calgary
and Otago.'' Research Report No. ??/???/??, Computer Science Department,
University of Calgary, date?.
 
\A
This paper gives a brief summary of the work in ray tracing at the University
of Calgary Department of Computer Science in cooperation with the University
of Otago in New Zealand. There are various projects: architecture for
multi-processor ray tracing machine, parallel cellular ray tracing, theory of
ray tracing, ray tracing soft objects and sketching with ray tracing.

\S Lighting Models

\R Tezenas du Montcel, Bruno, and Alain Nicolas. ``An Illumination Model for
Ray Tracing.'' \B Proceedings of Eurographics '85\}, Carlo E. Vandoni (ed.),
p. 63-75.

\A
Presented here is an illumination model adapted to meet the demands of a
ray-tracing program. This model is an extension of the Torrance-Sparrow
reflection model, described by James F. Blinn and also by Robert L. Cook and
Kenneth F. Torrance, concerning rough metallic surfaces. Special attention
has been given to the modelization of transparency phenomena in order to keep
it consistent with those mentioned above. After explaining the main
differences induced in the elaboration of the model by the constraints imposed
by a ray-tracing algorithm, the different calculations will then be clarified
which are necessary to compute the final color associated with each pixel. The
model is implemented within the ray-tracing program developed at the
``Institute National de la Communication Audiovisuelle'' (Bry s/ Mame, France)
(National Institute for Audiovisual Communication) as part of the collection
of programs designed to produce three dimensional picture sequences regrouped
under the title ``P.A.R.I.S.'' - Programmes d'Animation Realiste d'Images de
Synthese - (Programs for Realistic Animation of Synthetic Images).

\R Hall, Roy A. ``Color Reproduction and Illumination Models.'' \B
Techniques for Computer Graphics\}, David F. Rogers and Rae A. Earnshaw (eds.),
Springer-Verlag, 1987, p. 194-238.

\A
A comprehensive analysis of previous research related to color computation and
image display is presented. Physical, optical, and perceptual background
references are described relative to color determination and display.
Illumination models are cast into similar terms for a comparative analysis of
visual and computational compromises. Finally, image display issues are
discussed and illustrated.

\R Bouville, Christian, J. L. Dubois, I. Marchal, and M. L. Viaud.
``Monte-Carlo Integration Applied to an Illumination Model.'' \B Eurographics
'88\}, p. ?.

\A
The use of Monte-Carlo integration together with stochastic sampling is very
useful for dealing with the scattering phenomena that occur in the propagation
and reflection of light. In this paper, these techniques have been applied to
the implementation of a physics-based global illumination model. The
theoretical basis of this approach is presented briefly and various
applications to realistic image are then described. This concerns the rendering
of penumbra and scattered reflection effects, antialiasing and accurate color
modelling through spectral integration. For all these applications, both
theoretical and implementation aspects are developed and it is shown that
stochastic techiques can provide very simple and efficient algorithms.

\R Whitted, Turner, and Robert L. Cook. ``A Comprehensive Shading Model.''
\B Tutorial: Computer Graphics: Image Synthesis\}, Kenneth I. Joy, Charles
W. Grant, Nelson L. Max, and Lansing Hatfield (eds.), Computer Society Press,
Washington, 1988, p. 232-243. Also appears in unpublished course notes from
\B State of the Art in Image Synthesis, SIGGRAPH '85 Course Notes \#11\}.

\A
As part of the search for better display algorithms, we have tried to classify
existing shading techniques within the most comprehensive model that we could
devise. Shading is a function which depends on the illumination and reflection
at visible points in a scene. Reflection depends in turn on the geometry and
surface properties at the point of reflection. We define a general and
comprehensive model of the image synthesis process in a ``pixel equation''
whose right hand side expresses a combination of the illumination and
reflection components. We then describe various shading techniques as
approximations to this expression to illustrate the limitations of typical
shading models.

\R Bouville, Christian, Kadi Bouatouch, Pierre Tellier, and Xavier Pueyo. ``A
Theoretical Analysis of Global Illumination Models.'' \B Eurographics Workshop
on Photosimulation\}, 1990, p. ?.

\A
This paper provides a general theoretical framework in which any previous
global illumination model can be described. It gives a theoretical background
which is based on radiometric quantities and on a physical approach to insure
generality and consistency. A system of energy balance equations is obtained.
Two approaches are possible depending on the way the radiometric properties of
surfaces are characterized. Furthermore, the problem of solving this system of
equations with the two-component method is addressed, and we show how we can
take advantage of the characteristics of each component to select an
appropriate method.
 
\R Roelens, M., G. Fertey, B. Peroche. ``Light Sources in a Ray
Tracing Environment.'' Technical Report \#90-6, Ecole Nationale Sup\'erieure
des Mines de Saint-Etienne, D\'epartement Informatique Appliqu\'ee, June
1990. Also appears in \B Proceedings Eurographics Workshop on Photosimulation,
Realism and Physics in Computer Graphics\}, June 1990, p. 195-213.
 
\A
Desk lamps, automobile headlights, street lamps,..., usually illuminate by
light cones. This article describes two methods adapted to simulate those
typical light sources, using a CSG model, in a ray tracing environment. These
methods allow us to visualize not only illuminated objects but also the light
beams. The first one is completely empirical; the second one is an improvement
of the previous one, physically-based, with spherical particles inside the
light beam.

\R Shirley, Peter, Kelvin Sung, and William Brown. ``A Ray Tracing Framework
for Global Illumination Systems.'' \B Graphics Interface '90\}, p. 117-128. *

\A
The fundamental software components useful for a zonal ray tracing system are
described. The interface protocols and some implementational observations are
outlined for each of the key components. Components for sampling, ray-object
intersection, and zonal (radiosity) calculations are emphasized. Some results
from a global illumination program assembled from the components are discussed.

\R Shirley, Peter S. \B Physically Based Lighting Calculations for Computer
Graphics\}, Ph.D. Thesis, Computer Science Department, University of Illinois
at Urbana-Champaign, 1991.

\A
Realistic image generation is presented in a theoretical formulation that
builds from previous work on the rendering equation. Previous and new solution
techniques for the global illumination are discussed in the context of this
formulation.

The basic physics of reflection and light transport are used to derive the
rendering equation. The problem of generating an image is phrased in terms of
evaluating the Global Radiance Function, which consists of radiance values for
all points and directions. This formulation of the rendering equation differs
from previous formulations by rigorously accounting for transparent surfaces.

The physical rules governing reflection are used to make improvements in
reflection models. In diffuse transmission it is shown that light is filtered
to the same extent regardless of which side of the surface the light comes
from. This eliminates one of the parameters from previous diffuse transmission
models. The microscopic structure of polished surfaces was used to justify
coupling the diffuse and specular coefficients according to the Fresnel
Equations. The Fresnel Equations are commonly used to vary the reflectivity of
metal and transparent dielectrics, but have not been used before to vary the
reflectivity of the polish and underlying diffuse substrate. 

Image-based solution methods are phrased as a lazy evaluation of the Global
Radiance Function; evaluation takes place for visible points. Several
constraints were outlined for what part of the image function should contribute
to each pixel, and a separable, symmetric filter is developed that satisfies
these constraints.

A stochastic shadow ray generation method is introduced that reduces the
number of shadow rays needed for scenes with multiple light sources. The
sampling distributions used for shadow rays and other dimensions of the
integral are evaluated by introducing to computer graphics the notion of
discrepancy from numerical integration theory. The use of discrepancy provided
some insight not given by the signal processing theory traditionally used in
computer graphics. As part of this discussion a new sampling scheme, N-rooks
sampling, is introduced. N-rooks sampling is shown to be as efficient to
generate as jittered sampling, while often outperforming Poisson disk sampling.
It also can generate distributions for any positive integer number of samples,
including primes. 

The peculiarities of the sampling spaces used in distributed ray tracing are
shown to preclude naive hierarchical sampling. It is demonstrated that
hierarchical sampling can greatly reduce noise, however, if we have sufficient
knowledge of the sampling space. 

Zonal methods represent the opposite extreme of image methods, where all
function values are computed and stored, and each evaluation is a table lookup.
The zonal method is phrased as a transport simulation, similar to progressive
refinement radiosity methods. Using this direct simulation model, it is
straightforward to generate zonal methods for anisotropic reflection. This
requires storing accumulated power in a directional table for each zone. A
proof is given that, subject to certain constraints, only \$O(N)\$ rays are
required for a zonal solution with \$N\$ zones.

Simulation allows for surfaces which are not zoned to interact with those that
are. This is a generalization of the diffuse and specular ray tracing transport
work of Malley. This technique can be useful for highly complex or difficult to
zone surfaces such as a human face.

The zonal solution methods can be applied to participating media in a fairly
natural manner. This zonal method has the benefit of not requiring as much
computation time when the medium is sparse. This also applies to media with
anisotropic scattering characteristics, but such a solution requires a large
amount of storage.

Wavelength dependent solutions introduce some complications, but can be handled
by traditional point sampling techniques. Time dependent solutions are easily
handled by image-based solution methods, but are very difficult to apply using
zonal methods.

\S Antialiasing

\R Amanatides, John. ``Ray Tracing with Cones.'' \B SIGGRAPH '84\},
p. 129-135.

\A
A new approach to ray tracing is introduced. The definition of a ``ray'' is
extended into a cone by including information on the spread angle and the
virtual origin. The advantages of this approach, which tries to model light
propagation with more fidelity, include a better method of antialiasing, a
way of calculating fuzzy shadows and dull reflections, a method of calculating
the correct level of detail in a procedural model and texture map, and finally,
a procedure for faster intersection calculation.

\R Dipp\'e, Mark A., and Erling Henry Wold. ``Antialiasing Through
Stochastic Sampling.'' \B SIGGRAPH '85\}, p. 69-78.

\A
\E Stochastic sampling\} techniques, in particular \E Poisson\} and
\E jittered\} sampling, are developed and analyzed. These approaches allow
the construction of \E alias-free\} approximations to continuous functions
using discrete calculations. Stochastic sampling scatters high frequency
information into broadband \E noise\} rather than generating the false
\E patterns\} produced by \E regular\} sampling. The type of randomness used
in the sampling process controls the spectral character of the noise. The
\E average sampling rate\} and the function being sampled determine the
amount of noise that is produced. Stochastic sampling is applied \E
adaptively\} so that a greater number of samples are taken where the function
varies most. An \E estimate\} is used to determine how many samples to take
over a given region. \E Noise reducing filters\} are used to increase the
efficacy of a given sampling rate. The \E filter width\} is adaptively
controlled to further improve performance. Stochastic sampling can be applied
\E spatiotemporally\} as well as to other aspects of scene simulation. \E
Ray tracing\} is one example of an image synthesis approach that can be
antialiased by stochastic sampling.

\R Lee, Mark E., Richard A. Redner, and Samuel P. Uselton. ``Statistically
Optimized Sampling for Distributed Ray Tracing.'' \B SIGGRAPH '85\}, p. 61-67.

\A
Cook, Porter, and Carpenter coined the phrase ``distributed ray tracing'' to
describe a technique for using each ray of a super-sampled ray tracing
procedure as a sample in several dimensions to achieve effects such as
penumbras and motion blur in addition to spatial antialiasing. The shade to
be displayed at a pixel is a weighted integral of the image function. The
purpose of using many rays per pixel is to estimate the value of this
integral. In this work, a relationship between the number of sample rays and
the quality of the estimate of this integral is derived. Furthermore, the
number of rays required does not depend on the dimensionality of the space
being sampled, but only on the variance of the multi-dimensional image
function. The algorithm has been optimized through the use of statistical
testing and stratified sampling.

\R Purgathofer, Werner. ``A Statistical Method for Adaptive Stochastic
Sampling.'' \B Proceedings of Eurographics '86\}, A. A. G. Requicha (ed.),
p. 145-152.

\A
Stochastic sampling is a good alternative to pure oversampling in terms of
image quality. A method for adaptively controlling the number of required
samples to the complexity of the picture is presented. The quality of the
obtained picture can be controlled by two well-understandable parameters,
these parameters define an error interval size and the probability that a
pixel lies within it. The usefulness of the method is described by applying
it to distributed ray-tracing.

\R Mitchell, Don P. ``Generating Antialiased Images at Low Sampling
Densities.'' \B SIGGRAPH '87\}, p. 65-72.

\A
Ray tracing produces point samples of an image from a 3-D model. Constructing
an antialiased digital picture from point samples is difficult without
resorting to extremely high sampling densities. This paper describes a program
that focuses on that problem. While it is impossible to eliminate aliasing
totally, it has been shown that nonuniform sampling yields aliasing that is
less conspicuous to the observer. An algorithm is presented for fast
generation of nonuniform sampling patterns that are optimal in some sense.
Some regions of an image may require extra sampling to avoid strong aliasing.
Deciding where to do extra sampling can be guided by knowledge of how the eye
perceives noise as a function of contrast and color. Finally, to generate the
digital picture, the image must be reconstructed from the samples and
resampled at the display pixel rate. The nonuniformity reconstruction filter
is presented which solves this problem efficiently.

\R Argence, J. ``Antialiasing for Ray Tracing Using CSG Modeling.'' \B New
Trends in Computer Graphics, Proceedings of CG International '88\}, Nadia
Magnenat-Thalmann and Daniel Thalmann (eds.), Springer-Verlag, p. 199-208.

\A
Aliasing is a decisive problem in realistic image producing. Since ray tracing
is a rather slow algorithm of visualization, antialiasing an image by
systematically oversampling its pixels is quite costly. We suggest a local
adaptive oversampling algorithm for antialiasing ray tracing. We use space
coherence to determine which pixels on the screen need be oversampled. The CSG
model is used to define the scene, and also to limit it, for each pixel, to
objects of concern only. To minimize memory space needs, we work on a window
over the screen.
 
\R Cook, Robert L. ``Stochastic Sampling in Computer Graphics.'' \B
Tutorial: Computer Graphics: Image Synthesis\}, Kenneth I. Joy, Charles
W. Grant, Nelson L. Max, and Lansing Hatfield (eds.), Computer Society Press,
Washington, 1988, p. 283-304. Also appears in \B ACM TOG\}, Vol. 5, \#1,
January 1986, p. 51-72.
 
\A
Ray tracing, ray casting, and other forms of point sampling are important
techniques in computer graphics, but their usefulness has been undermined by
aliasing artifacts. In this paper it is shown that these artifacts are not an
inherent part of point sampling, but a consequence of using regularly spaced
samples. If the samples occur at appropriate nonuniformly spaced locations,
frequencies above the Nyquist limit do not alias, but instead appear as noise
of the correct average intensity. This noise is much less objectionable to our
visual system than aliasing. In ray tracing, the rays can be stochastically
distributed to perform a Monte Carlo evaluation of integrals in the rendering
equation. This is called \E distributed ray tracing\} and can be used to
simulate motion blur, depth of field, penumbrae, gloss, and translucency.

\R Cychosz, Joseph M. ``Efficient Generation of Sampling Jitter Using Look-up
Tables.'' Purdue CADLAB Technical Report No. JC-05, Purdue University, 1989.

\A
Presented in this paper is a method for generating sampling jitter using a
limited number of random numbers. The proposed jitter function is a function
of three variables, namely the sample location (\$x,y\$) and the sample number
(\$s\$) for the location. Furthermore, the method will produce repeatable
jitter for all \$x\$ and \$y\$ without requiring either the storage of a large
number of random numbers, or the consistent access of \$x\$, \$y\$, and \$s\$. This
paper examines the application of this jitter function to the ray tracing
algorithm.

\R Nakamae, Eihachiro, Takao Ishizaki, Tomoyuki Nishita, and Shinichi Takita.
``Compositing 3D Images with Antialiasing and Various Shading Effects.'' \B
IEEE CG\&A\}, March 1989, p. 21-29.

\A
To make complex images look realistic, various typpes of geometric models and
shading effects are needed. Programs capable of dealing with these are usually
large and complex, and they are expensive to develop. This article proposes a
method for compositing 3D images produced by different programs taking depth
order into consideration. This method can add the following effects to
composited images:

1. Antialiased images with scaling are displayed by a simple algorithm.

2. The algorithm can add shading effects due to various types of light, such as
area sources and skylight.

3. Such shading effects as transparency and refraction are usually
accomplished by ray tracing, but at the expense of enormous computation time.
Our method allows ray tracing to be performed in localized regions, producing
realistic results without the computational expense of ray tracing the whole
scene.

In addition to the above processes, such shading effects as fog and texture
mapping can be processed with conventional methods. Thus it becomes possible
to display complex scenes with various shading effects, using relatively
small computers.

\R Painter, James, and Kenneth Sloan. ``Antialiased Ray Tracing by Adaptive
Progressive Refinement.'' \B SIGGRAPH '89\}, p.281-288. 

\A
We describe an antialiasing system for ray tracing based on adaptive
progressive refinement. The goals of the system are to produce high quality
antialiased images at a modest average sample rate, and to refine the image
progressively so that the image is available in a usable form early and is
refined gradually toward the final result.

The method proceeds by adaptive stochastic sampling of the image plane,
evaluation of the samples by ray tracing, and image reconstruction from the
samples. Adaptive control of the sample generation process is driven by three
basic goals: coverage of the image, location of features, and confidence in the
values at a distinguished ``pixel level'' resolution.

A three-stage process of interpolating, filtering, and resampling is used to
reconstruct a regular grid of display pixels. This reconstruction can be either
batch or incremental.

\R Salesin, David, and Jorge Stolfi. ``The ZZ-Buffer: a Simple and Efficient
Rendering Algorithm with Reliable Antialiasing.'' \B Proceedings of the PIXIM
'89 Conference\}, p. 451-466.
 
\A
The ZZ-buffer is a new rendering algorithm that is simple, efficient, and
produces high-quality images. The algorithm correctly renders transparent
surfaces, shadows with real penumbrae, and depth of field effects. The
ZZ-buffer algorithm is substantially faster than ray tracing an nearly as
versatile. While the ZZ-buffer is somewhat slower than the Z-buffer or
A-buffer, it avoids the aliasing and other artifacts of these algorithms.
The algorithm's efficiency comes from a screen-space object indexing scheme,
and from the use of lazy evaluation for visibility tests. It achieves reliable
antialiasing by employing an adaptive form of stochastic supersampling. The
algorithm is simple enough that we give most of its code here in this paper.
The algorithm has been implemented as part of a commercial production system
and has proved robust over a large variety of images.

\R Thomas, D., Arun N. Netravali, and D. S. Fox. ``Anti-aliased Ray Tracing with
Covers.'' \B Computer Graphics Forum\}, 8 (1989), p. 325-336.

\A 
A fast and effective object space method for anti-aliasing ray-traced pictures
is introduced. Traditionally, anti-aliasing has been done using
super-sampling. However, this is costly since it requires casting large
numbers of rays to obtain sample densities above the displayed pixel density.
It is also wasteful since much of the information in these samples is
discarded when they are filtered to yield the anti-aliasing pixels. We avoid
these problems by performing the filtering in the object space using the
geometry of ray-surface intersections rather than by casting extra rays. In
addition, we only perform filtering at a pixel if edges are nearby. We detect
these edges by observing the order in which the pixel's rays pass through
cover surfaces constructed just inside and outside the surface of each object.
Shadows, reflections and refractions can be anti-aliased using this method and
a variety of object types can be handled including ellipsoids, polyhedra, and
objects formed using set operations.

Our anti-aliasing gives high image quality that can only be approached by
using super-sampling densities at least four times the display pixel density.
Moreover, since the overhead of our method is small, it would take three to
four times as long to render an anti-aliased image using super-sampling than
it would with our method. Furthermore, covers allow sampling densities less
than the displayed pixel density. When this is done, anti-aliased images can
be rendered twice as fast as with no anti-aliasing and six to eight times as
fast as when super-sampling is used for anti-aliasing.

\R Wyvill, Geoff, and P. Sharp. ``Fast Antialiasing of Ray Traced Images.''
\B New Trends in Computer Graphics, Proceedings of CG International '89\},
p. 578-588.

\A
The best way to antialias an image is by prefiltering. But for many ray traced
images, there is no adequate description of the ideal image to filter. The only
information you have is the sample points. An efficient algorithm for
antialiasing in these cases is presented.

\R Ohta, Masataka, and Mamoru Maekawa. ``Ray-Bound Tracing for Perfect and
Efficient Anti-Aliasing.'' \B The Visual Computer\}, Vol. 6, 1990, p. 125-133.
Revision of ``Bounded Ray Tracing for Perfect Efficient Anti-aliasing.''
Technical Report No. 87-03, Dept. of Information Science, University of Tokyo,
January 1987.

\A
A complete detection of whether aliasing occurs in a given pixel is possible by
using the concept of bounded rays and ray-bound tracing. A coherent set of rays
can be bounded by bounding both their origins (by a sphere) and directions (by
a circle on a unit sphere). By tracing bounds of rays in a pixel, along the
direction of reflection, refraction or to light sources, it is possible to
obtain an upper bound on the degree of aliasing in the pixel. Ray bound tracing
is possible against various shapes and with various shading algorithms.
 
\R Brown, William Todd. ``Filtering and Adaptive Supersampling for Ray Traced
Rendering,'' Report No. UIUCDCS-R-91-1657, Department of Computer Science,
University of Illinois at Urbana-Champaign, January 1991.
 
\A
The problems addressed by filtering of supersampled images are considered.
Issues in filter selection are considered, and upon these criteria and a
comparison of linear image filters is made. Previous work in adaptive
supersampling is then described. A revision of prior techniques for adaptive
supersampling is presented to address problems in memory consumption. This
system yields a substantial reduction in rendering time versus conventional
supersampling, yet retains image quality.

\R Mitchell, Don P. ``Spectrally Optimal Sampling for Distribution Ray
Tracing.'' \B SIGGRAPH '91\}, p. 157-164.

\A
Nonuniform sampling of images is a useful technique in computer graphics,
because a properly designed pattern of samples can make aliasing take the form
of high-frequency random noise. In this paper, the technique of nonuniform
sampling is extended from two dimensions to include the extra parameter
dimensions of distribution ray tracing. A condition for optimality is
suggested, and algorithms for approximating optimal sampling are developed. The
technique is demonstrated at low sampling densities, so the characteristics of
aliasing noise are clearly visible. At supersampling rates, this technique
should move noise into frequencies above the passband of pixel-reconstruction
filter.

\S Bounding Volumes, Data Structures, and Object Hierarchies

\R Rubin, Steven M., and Turner Whitted. ``A 3-Dimensional Representation
for Fast Rendering of Complex Scenes.'' \B SIGGRAPH '80\}, p. 110-116.

\A
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 homogeneity allows the
visible surface rendering to be performed simply and efficiently.

The bounding volumes selected for this algorithm are parallelepipeds oriented
to minimize their sizes. 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 lower levels of the
hierarchy only when required. Because the viewing process has a single
operation and primitive type, the software and hardware chosen to implement
the search can be highly optimized for very fast execution.

\R Weghorst, Hank, Gary Hooper, and Donald P. Greenberg. ``Improved
Computational Methods for Ray Tracing.'' \B ACM TOG\}, Vol. 3, \#1, January
1984, p. 52-69.

\A
This paper describes algorithmic procedures that have been implemented to
reduce the computational expense of producing ray-traced images. The selection
of bounding volumes is examined to reduce the computational cost of the
ray-intersection test. The use of object coherence, which relies on a
hierarchical description of the environment, is then presented. Finally, since
the building of the ray-intersection trees is such a large portion of the
computation, a method using image coherence is described. This visible-surface
preprocessing method, which is dependent upon the creation of an ``item
buffer,'' takes advantage of \E a priori\} image formation. Examples that
indicate the efficiency of these techniques for a variety of representative
environments are presented.

\R Tamminen, Markku, Olli Karonen, and Martti M\"antyl\"a. ``Ray-Casting
and Block Model Conversion Using a Spatial Index.'' \B CAD\}, Vol. 16, \#4,
July 1984, p. 203-208.

\A
A spatial index is a data structure designed to facilitate spatial search,
exemplified by the point-in-polyhedron inclusion problem. The 3D extendible
cell (EXCELL) index is presented together with algorithms for spatial search
and for converting a complex polyhedron (boundary representation) into an
octree-like block model. We illustrate this technique by an application to
geometric mine modelling and demonstrate the efficiency of the approach by
practical experiments.

\R Coquillart, Sabine. ``An Improvement of the Ray-Tracing Algorithm.''
\B Proceedings of Eurographics '85\}, Carlo E. Vandoni (ed.), p. 77-88.

\A
This paper describes an improvement of the ray-tracing algorithm. The new
method takes advantage of a data structure which allows us to consider only
the closest objects to the path of the ray. This technique can be applied
to primary and secondary rays. Using this method, the run-time depends more on
the complexity of the generated picture than on the complexity of the scene.

\R Jansen, Frederik W. ``Data Structures for Ray Tracing.'' \B Data
Structures for Raster Graphics\}, L. R. A. Kessener, F. J. Peters, and
M. L. P. van Lierop (eds.), Springer-Verlag, 1985, p. 57-73.

\A
Methods to improve the efficiency of the ray tracing process are reviewed.
Special attention is given to algorithms for tracing a ray through box and cell
structures of hierarchical box and spatial subdivision methods.

\R Kay, Timothy L., and James T. Kajiya. ``Ray Tracing Complex Scenes.''
\B SIGGRAPH '86\}, p. 269-278.

\A 
A new algorithm for speeding up ray-object intersection calculations is
presented. Objects are bounded by a new type of extent, which can be made to
fit convex hulls arbitrarily tightly. The objects are placed into a hierarchy.
A new hierarchy traversal algorithm is presented which is efficient in the
sense that objects along the ray are queried in an efficient order.

Results are presented which demonstrate that our technique is several times
faster than other published algorithms. Furthermore, it is demonstrated that
it is currently possible to ray trace scenes containing hundreds of thousands
of objects.

\R Goldsmith, Jeffrey, and John Salmon. ``Automatic Creation of Object
Hierarchies for Ray Tracing.'' \B IEEE CG\&A\}, May 1987, p. 14-20.

\A
Intersection calculations dominate the run time of canonical ray tracers. A
common algorithm to reduce the number of intersection tests required is the
intersection of rays with a tree of extents, rather than the whole database of
objects. A shortcomming of this method is that these trees are difficult to
generate. Additionally, manually generated trees are poor, greatly reducing
the run-time improvement available. We present methods for evaluation of
these trees in approximate number of intersection calculations required and
for automatic generation of good trees. These methods run in \$O(n \l n)\$
expected time where \$n\$ is the number of objects in the scene. Some examples
of speedup are reported.

\R Lin, Jimmy Jih-Ming. \B Fast Ray Tracing on BSP-Trees\}, Masters Thesis,
Computer Science Department, University of Central Florida, 1987.

\A
[No abstract. Excerpt from Conclusions]

Based on these analyses and experiments, the BSP-Trace Method may not be the
best solution for speeding up the ray tracing, but it is worthwhile subject for
research. The potential drawbacks of the BSP-Trace which make it no better than
the Octree Method are:

(1) The number of surfaces on the BSP-Tree is typically far more than the
original number of surfaces, because of the splitting of surfaces into two by
other surfaces' planes;

(2) The Octree Method only needs to test those objects which reside in the
selected voxels, and the BSP-Trace needs to consider the objects in the whole
half-space.

[FUJI86] mentioned that the memory requirement for the octree is very costly,
but for the BSP-Tree, it can be taken care of very efficiently. The bottleneck
of the Octree Method is the time spent on traveling up and down the Octree
[FUJI86], and our experiments show that this time is around 35\% of the total
time. The solution to reduce the traveling time is to lower the height of the
octree, but meanwhile the increase in the number of objects contained in the
voxel means more intersections per ray. Thus, a new data structure for fast
ray tracing which combines the Octree and BSP-Tree is proposed.

The new data structure contains an octree on the top, and every leaf voxel
consists of a BSP-Tree. This will cut down both the tree traveling time (by
lowering the tree height) and the memory consumed by the octree. Also, if we
can keep the number of objects inside the voxel down, the increased number of
surfaces by using the BSP-Tree is limited. This thus will reduce the number of
intersection tests made inside the voxel.

\R Peng, Qunsheng, Yining Zhu, and Youdong Liang. ``A Fast Ray Tracing
Algorithm Using Space Indexing Techniques.'' \B Proceedings of Eurographics
'87\}, Guy Mar\'echal (ed.), p. 11-23.

\A
A fast ray tracing algorithm is presented. Spatial coherency is exploited by
adopting a linear octree data structure which corresponds to an adaptive
partitioning of space. A ray strides over a number of empty regions aligning on
its way and intersects the desired objects directly. Efficiency of the
algorithm is achieved by decreasing the number of regions that the ray must be
checked with, by reducing the computations involved in skipping an empty region
and performing a binary search to find the next region. An efficient algorithm
based on linear programming for mapping the whole environment into a sorted
linear octree is also described. Only the terminal nodes containing boundary
surfaces of objects are explicitly represented, which not only shortens the
searching process but also leads to a considerable saving on storage space.

\R Scherson, Isaac D., and Elisha Caspary. ``Data Structures and the
Complexity of Ray Tracing.'' \B The Visual Computer\}, Vol. 3, 1987,
p. 201-213.

\A
The time complexity of ray tracing is a function of the data structures used
for space division. Octree and hierarchical extents have been suggested as
effective choices. In this paper, complexity parameters are suggested to
characterize images and show that both octrees and hierarchies are appropriate
choices if given most favorable images. Also, a unified technique is proposed
and shown to be better than previous methods for all images. Octrees and
hierarchies are particular cases of the new proposed algorithm.
 
\R Bouville, Christian, Jean-Luc Dubois, and Isabelle Marchal. ``A
Space Tracing Method Applied to Polygonal Models.'' Centre Commun d'Etudes de
T\'el\'ediffusion et T\'el\'ecommunications.
 
\A
The ray-tracing rendering method gives the highest possible level of realism
that can be attained in computer graphics. Recently many alternatives have
been reported on ways to speed up this process and particularly by means of a
space subdivision technique. We propose such an algorithm specially adapted to
polygonal models. A BSP tree technique is used to perform space subdivision
and a spatial index allows direct access to any cell. A method which minimizes
primary ray computations and an algorithm which avoids the tracing of a large
number of rays towards light sources have been studied. Results about time and
space required by this algorithm are presented.

\R Samet, Hanan. ``Implementing Ray Tracing with Octrees and Neighbor Finding.''
\B Computers \& Graphics\}, Vol. 13, \#4, 1989, p. 445-460.

\A
A Ray Tracing implementation is described that is based on an octree
representation of a scene. Rays are traced through the scene by calculating
the blocks through which they pass. This calculation is performed in a
bottom-up manner through the use of neighbor finding. The octrees are assumed
to be implemented by a pointer representation.

\R Charney, Mark J., and Isaac D. Scherson. ``Efficient Traversal
of Well-Behaved Hierarchicial Trees of Extents for Ray-Tracing Complex Scenes.''
\B The Visual Computer\}, Vol. 6, 1990, p. 167-178.

\A
Traversal of hierarchical trees of extents (HTE) requires computation of
intersections between rays and bounding volumes whose faces are parallel to
the cartesian axes. By redefining the HTE so that non-overlapping bounding
volumes are generated, a well-behaved data structure is obtained in which
``geometrical coherence'' is applied to speed up its traversal. We distinguish
two types of bounding volumes: \E internal\} boxes contain the ray's origin
while \E external\} bounding volumes do not contain the ray's origin. To
traverse the HTE, we look first to polygons in the internal bounding volumes
and external boxes are dealt with only when no ray-polygon intersection is
found in internal nodes. As external nodes in the HTE define pruned subtrees of
external bounding volumes, geometrical characteristics of the boxes are
exploited for HTE traversal. A coding scheme allows a 6-bit code to determine
which faces of a bounding volume need to be tested for intersection. Also, our
well-behaved HTE allows for reuse of intersection points at lower levels of the
tree.
 
\R Thirion, J. P. ``Tries: Data Structures Based on Boolean Representation for
Ray Tracing.'' Technical Report 90-3, Laboratoire d'Informatique de l'Ecole
Normale Sup\'erieure, Paris, France, February 1990. Also appears in \B
Proceedings of Eurographics '90\}, p. 530-542.
 
\A
Tries are data structures used in multidimensional searching. We introduce an
original method to build Tries for a set of convex polyhedra, show how Tries
can be used for ray tracing and compare them with other data structures. Their
advantages are mainly compactness of memory representation and fast building
of the structure due to simple boolean operations. Tries also accelerate the
ray tracing process compared to other octree-like structures. Furthermore,
they are easy to implement because they are a unified approach to
multidimensional problems. Finally we show experimental results to compare
them with other data structures used in image synthesis.

\R Subramanian, K. R., and Donald S. Fussell. ``Automatic Termination Criteria
for Ray Tracing Hierarchies.'' \B Graphics Interface '91\}, p. ?. *

\A
A common problem in space subdivision hierarchies used in ray tracing is
determining the proper termination criteria to stop subdivision. We propose a
cost model based on scene characteristics that can be used to predict the
correct termination point to optimize performance. The characteristics are
determined as the hierarchy is being built. The model is applied to a variety
of space subdivision schemes to test its accuracy. Experimental results
indicate the power and usefulness of this model when applied to some standard
ray tracing benchmarks.

\S Shadow Testing

\R Haines, Eric A., and Donald P. Greenberg. ``The Light Buffer: A
Shadow-Testing Accelerator.'' \B IEEE CG\&A\}, September 1986, p. 6-16.
Contains main points of: \B The Light Buffer: A Ray Tracer Shadow Testing
Accelerator\} by Eric A. Haines, Master's Thesis, Program of Computer Graphics,
1986.

\A
In one area of computer graphics, realistic image synthesis, the ultimate goal
is to produce a picture indistinguishable from a photograph of a real
environment. A particularly powerful technique for simulating light
reflection---an important element in creating this realism---is called ray
tracing. This method produces images of excellent quality, but suffers from
lengthy computation time that limits its practical use.

This article presents a new method to reduce shadow testing time during ray
tracing. The technique involves generating light buffers, each of which
partition the environment with respect to an individual light source. These
partition descriptions are then used during shadow testing to quickly
determine a small subset of objects that may have to be tested for
intersection.

The results of timing tests illustrate the beneficial performance of these
techniques. The tests compare the standard ray-tracing algorithm to light
buffers of varying resolution.

\R Eo, K. S., and C. M. Kyung. ``Hybrid Shadow Testing Scheme for Ray
Tracing.'' \B CAD\}, Vol. 21, \#1, January/February 1989, p. 38-48.

\A
The paper presents a new shadow testing acceleration scheme for ray tracing
called hybrid shadow testing (HST) based on conditional switching between the
conventional shadow testing method and Crow's shadow volume method, where the
shadow polygons as well as the object polygons are registered onto the
corresponding cells under the 3D space subdivision environment. Despite the
preprocessing time needed for the generation and registration of the shadow
polygons, the total shadow testing time of HST was approximately 50\% of that
of conventional shadow testing for several examples, while the total ray
tracing time was typically reduced by 30\%. This is due to the selective use
of the shadow volume method, with a compromise between maximizing use of the
shadow's spatial coherency and minimizing the computational overhead for
checking ray intersections with the shadow polygons. A parameter \$N\_th\}\$,
denoting the critical number of shadow polygons between successive reflection
points, was used as a guideline for switching the shadow testing scheme
between the conventional method and shadow volume method. A method for
calculating \$N\_th\}\$ from statistical data such as the number of object
polygons, average polygon size, and average peripheral length of the polygons
was proposed, resulting in good agreement with the experimental results.
 
\R Woo, Andrew, Pierre Poulin, and Alain Fournier. ``A Survey of Shadow
Algorithms.'' \B IEEE CG\&A\}, November 1990, p. 13-32.
 
\A
Essential to realistic and visually appealing images, shadows are difficult to
compute in most display environments. This survey characterizes the various
types of shadows. It also describes most existing shadow algorithms and
discusses their complexities, advantages, and shortcomings. We examine hard
shadows, soft shadows, shadows of transparent objects, and shadows for complex
modeling primitives. For each type, we examine shadow algorithms within
various rendering techniques.
 
This survey attempts to provide readers with enough background and insight on
the various methods to allow them to choose the algorithm best suited to their
needs. We also hope that our analysis will help identify the areas that need
more research and point to possible solutions.

\R Woo, Andrew, and John Amanatides. ``Voxel Occlusion Testing: A Shadow
Determination Accelerator for Ray Tracing.'' \B Proceedings of Graphics
Interface '90\}, p. 213-220.

A shadow determination accelerator for ray tracing is presented. It is built on
top of the uniform voxel traversal grid structure. The accelerator proves to be
rather efficient, requires little additional memory and the worst case scenario
per shadow determination just reduces down to traditional voxel traversal. It
can also be extended to model linear, area lights, as well as atmospheric
shadows.

\R Ward, Gregory J. ``Adaptive Shadow Testing for Ray Tracing.'' \B Second
Eurographics Workshop on Rendering\}, May 1991, p. ?.

\A
We present a simple technique for improving the efficiency of ray tracing
in scenes with a large number of light sources. The sources sorted
according to their potential contribution, and only those sources whose
shadows are above a specified threshold are tested. The remainder are
added into the result in proportion to a statistical estimate of their
visibility. The algorithm requires very little storage, and produces no
objectionable artifacts.

\S Coherence

\s Spatial Coherence

\R Heckbert, Paul S., and Pat Hanrahan. ``Beam Tracing Polygonal Objects.''
\B SIGGRAPH '84\}, p. 119-127.

\A
Ray tracing has produced some of the most realistic computer generated
pictures to date. They contain surface texturing, local shading, shadows,
reflections, and refractions. The major disadvantage of ray tracing results
from its point-sampling approach. Because calculation proceeds \E ab
initio\} at each pixel it is very CPU intensive and may contain noticeable
aliasing artifacts. It is difficult to take advantage of spatial coherence
because the shapes of reflections and refractions from curved surfaces are so
complex.

In this paper we describe an algorithm that utilizes the spatial coherence of
polygonal environments by combining features of both image and object space
hidden surface algorithms. Instead of tracing infinitesimally thin rays of
light, we sweep areas through a scene to form ``beams.'' This technique
works particularly well for polygonal models since for this case the
reflections are linear transformation, and refractions are often approximately
so.

The recursive beam tracer begins by sweeping the projection plane through the
scene. Beam-surface intersections are computed using two-dimensional polygonal
set operations and an occlusion algorithm similar to the Weiler-Atherton
hidden surface algorithm. For each beam-polygon intersection the beam is
fragmented and new beams created for the reflected and transmitted swath of
light. These sub-beams are redirected with a 4x4 matrix transformation and
recursively traced. This beam trree is an object space representation of the
entire picture.

\R Dadoun, N., D. G. Kirkpatrick, and J. P. Walsh. ``The Geometry of Beam
Tracing.'' \B ACM Symposium on Computational Geometry\}, 1985, p. 55-61.

\A
A solution to the hidden surface elimination problem called beam tracing is
described. Beam tracing is related to ray tracing but uses spatial coherence
within the scene, and area coherence within the image to batch computations.
Beam tracing is an object space solution to the hidden surface problem.

Beam tracing is formulated in terms of its principal subprocesses:
intersection, sorting, and clipping. A hierarchical scene representation is
proposed. This incorporates the space decomposition idea of the BSP tree
[Fuchs, Kedem, and Naylor, 80] along with the convex polytope intersection
detection technique of [Dobkin and Kirkpatrick, 83] to interleave and
efficiently solve the intersection and sorting subproblems of beam tracing.

\R Speer, L. Richard, Tony D. DeRose, and Brian A. Barsky. ``A Theoretical
and Empirical Analysis of Coherent Ray-Tracing.'' \B Computer-Generated
Images: The State of the Art, Proceedings of Graphics Interface '85\},
N. Magnenat-Thalmann and D. Thalmann (ed.), p. 11-25. Also appears in \B
Graphics Interface '85\}, p. 1-8.

\A
The use of \E coherence\} has been advocated as a means of reducing the large
computational cost of the ray-tracing method of image synthesis. This paper
examines the theoretical and empirical performance of a typical coherent
ray-tracing algorithm, one that exploits the similarity between the
intersection trees generated by successive rays. It is shown that despite the
large degree of coherence present in a scene, the need to ensure the validity
of ray-object intersections prevents any significant computational savings.
This indicates that other algorithmic methods must be used in order to
substantially reduce the computational cost of ray-traced imagery.

\R Hanrahan, Pat. ``Using Caching and Breadth-First Search to
Speed Up Ray Tracing.'' \B Proceedings of Graphics Interface '86/Vision
Interface '86\}, 1986, p. 56-61.

\A
Ray-tracing is an expensive image synthesis technique because many more
ray-surface intersection calculations are done than are necessary to shade the
visible areas of the image. This paper extends the concept of beam-tracing so
that it can be coupled with caching to reduce the number of intersection
tests. Two major improvements are made over existing techniques. First, the
cache is organized so that cache misses are only generated when another
surface is intersected, and second, the search takes place in breadth-first
order so that coherent regions are completely computed before moving onto the
next region.

\R M\"uller, H. ``Image Generation by Space Sweep.'' \B Computer Graphics
Forum\}, Vol. 5, 1986, p. 189-195.

\A
A method of using spatial coherence in image generation by ray tracing is
presented. The idea is to trace a set of rays in parallel. This is carried
out by space sweep. Space sweep consists of moving a plane through the
object space. The rays intersected by the plane are organized into a dynamic
data structure \$R\$ for range searching. When an object is met by the sweeping
plane, those rays intersecting the object are found by a range search with the
object in \$R\$. Exact complexity bounds are given for this algorithm, as well
as details to allow practical application of this approach in image operation.

\R Kaplan, Michael R. ``The Use of Spatial Coherence in Ray
Tracing.'' \B Techniques for Computer Graphics\}, David F. Rogers and Rae A.
Earnshaw (eds.), Springer-Verlag, 1987, p. 173-193.

\A
Although ray tracing has proven to be a valuable technique in realistic image
synthesis and a variety of other disciplines, it traditionally has not been
viable in highly complex, unstructured environments. Spatial coherence
algorithms for ray tracing are proposed as a solution to this problem, and the
tradeoffs between various spatial coherence schemes are discussed.

\R Ohta, Masataka, and Mamoru Maekawa. ``Ray Coherence Theorem
and Constant Time Ray Tracing Algorithm.'' \B Computer Graphics 1987 -
Proceedings of CG International '87\}, Tosiyasu L. Kunii (ed.), Springer-Verlag,
p. 303-314.

\A
The concept of ray coherence is formalized as a ray coherence theorem to
decrease the amount of computation in a ray object intersection of the ray
tracing algorithm. Using the theorem, the calculation time of ray-object
intersection in a ray tracing algorithm can be drastically decreased, by
calculating a table which is used to limit the number of objects which may
intersect with a given ray. The overhead of the algorithm is so small that it
is effective even when there are only two objects. For more objects, the
computation time of the ray-object intersection remains almost constant.

\R Shinya, Mikio, Tokiichiro Takahashi, and Seiichiro Naito. ``Principles and
Applications of Pencil Tracing.'' \B SIGGRAPH '87\}, p. 45-54.

\A
Pencil tracing, a new approach to ray tracing, is introduced for faster image
synthesis with more physical fidelity. The paraxial approximation theory for
efficiently tracing a pencil of rays is described and analysis of its errors is
conducted to insure the accuracy required for pencil tracing. The paraxial
approximation is formulated from a 4x4 matrix (a system matrix) that provides
the basis for pencil tracing and a variety of ray tracing techniques, such as
beam tracing, ray tracing with cones, ray-object intersection tolerance, and a
lighting model for reflection and refraction. In the error analysis, functions
that estimate approximation errors and determine a constraint on the spread
angle of a pencil are given.

The theory results in the following fast ray tracing algorithms; ray tracing
using a system matrix, ray interpolation, and extended `beam tracing' using a
`generalized perspective transform.' Some experiments are described to show
their advantages. A lighting model is also developed to calculate the
illuminance for refracted and reflected light.

\R Shinya, Mikio, Takafumi Saito,, and Tokiichiro Takahashi. ``Rendering
Techniques for Transparent Objects.'' \B Graphics Interface '89\}, p. 173-181.
 
\A
Three techniquesare proposed for more realistic image synthesis of transparent
objects. The techniques simulate important phenomena due to refraction and/or
reflection, such as focuses and caustics, a method called \E grid-pencil
tracing\} is proposed, based on the ideas of pencil tracing and backward ray
tracing. An anti-aliasing filter is designed for grid-pencil tracing in
area-source illumination environments. The theory of pencil tracing is also
applied to dispersion simulation. An extension of the theory provides a basis
for dispersive pencil tracing, where both spatial coherency and 'wavelength
coherency' is effectively used for fast image synthesis of dispersive objects.
 
Furthermore, a linear filtering technique is applied to effectively express
extremely bright spots such as sunshine reflection. The technique is based on
an analysis of a special camera filter called a 'cross-screen filter,' which
emphasizes bright spots by producing star-like lines around the spots on the
image.
 
With these techniques, the realism of transparent object images can be much
enhanced in an inexpensive way.

\R Thirion, J. P. ``Interval Arithmetic for High Resolution Ray Tracing.''
Technical Report 90-4, Laboratoire d'Informatique de l'Ecole Normale
Sup\'erieure, Paris, France, February 1990.

\A
We describe in this paper a new technique to accelerate ray tracing for high
resolution pictures. This technique uses the coherence of the rays, for direct
and shadow rays as for reflected and refracted rays. It is not an approximate
calculation, for the result of the process we describe is exactly the same as
conventional ray tracing. The basic idea in this algorithm is that for two rays
that are close together the operations to perform are almost the same.
Therefore, with a techique coming from interval arithmetic, we solve ray
tracing intersections for a cluster of rays, called a beam, instead of a single
ray. This algorithm appears to be between 2 and 3 times faster than
conventional ray tracing with traditional resolution, and this ratio improves
with higher resolution. Our approach is efficient to optimize algorithms where
the same operations occur repeatedly. The primitives we defined for our beam
tracer could be packaged into a module, useful to optimize a wide range of
repetitive algorithms provided that there is coherence between data.

\s Scene-to-Scene (Temporal) Coherence

\R Badt, Sig, Jr. ``Two Algorithms for Taking Advantage of
Temporal Coherence in Ray Tracing.'' \B The Visual Computer\}, Vol. 4, 1988,
p. 123-132.

\A
The basic ray-tracing algorithm is adapted to make ray-tracing faster for the
production of motion pictures. Two algorithms are presented. The image space
temporal coherence algorithm takes advantage of the fact that motion picture
images do not change very much from frame to frame. The reprojection algorithm
uses information about the object space saved from the previous frame to
accelerate the processing of the current frame. The reprojection algorithm
is used when the viewpoint of the current frame is changed by a small amount
from the viewpoint of the previous frame.

\R Glassner, Andrew S. ``Spacetime Ray Tracing for Animation.'' \B IEEE
CG\&A\}, March 1988, p. 60-70.

\A
We are presenting techniques for the efficient ray tracing of animated scenes.
These techniques are based on two central concepts: spacetime ray tracing, and
a hybrid adaptive subdivision/bounding volume technique for generating
efficient, nonoverlapping hierarchies of bounding volumes.

In spacetime ray tracing, instead of rendering dynamically moving objects in
3D space, we render static objects in 4D spacetime. To support spacetime ray
tracing, we use 4-dimensional analogues to familiar 3-dimensional ray-tracing
techniques.

The new bounding volume hierarchy combines elements of adaptive space
subdivision and bounding volume techniques. The quality of the hierarchy and
its nonoverlapping character make it an improvement over previous algorithms,
because both attributes reduce the number of ray/object intersections that
must be computed. These savings are amplified in animation because of the
much higher cost of computing ray/object intersections for motion-blurred
animation.

We show it is possible to ray trace large animations more quickly with
spacetime ray tracing using this hierarchy than with straightforward
frame-by-frame rendering.

\R S\'equin, Carlo H., and Eliot K. Smyrl. ``Parametric Ray Tracing.''
\B SIGGRAPH '89\}, p. 307-314.

\A
The construction and refinement of a computer graphics scene is unacceptably
slow when using ray tracing. We introduce a new technique to speed up the
generation of successive ray traced images when the geometry of the scene
remains constant and only the light source intensities and the surface
properties need to be adjusted. When the scene is first traced, an expression
parameterized in the color of all lights and the surface property coefficients
of all objects is calculated and stored for each pixel. Redisplaying a scene
with a new set of lights and colors then consists of substituting values for
the corresponding parameters and re-evaluating the expressions for the pixels.
This parameter updating and redisplay takes only a few seconds, as compared to
the many minutes or hours required to ray trace the entire scene again, but it
uses much more memory and disk space. With suitable expression sharing,
however, these storage needs can be reduced to an acceptable level.

\S Spatial Subdivision

\s Uniform Subdivision

\R Glassner, Andrew S. ``Space Subdivision for Fast Ray Tracing.'' \B IEEE
CG\&A\}, October 1984, p. 15-22. Also appears in \B Tutorial: Computer
Graphics: Image Synthesis\}, Kenneth I. Joy, Charles W. Grant, Nelson L. Max,
and Lansing Hatfield (eds.), Computer Society Press, Washington, 1988,
p. 159-167.

\A
[No abstract. The following is taken from the Conclusions]

We have seen that the infamous slowness of ray-tracing techniques is caused
primarily by the time required for ray-object intersection calculations. We
have also seen a new way of tracing the ray through small subsets of space at
a speed that reduces the number of ray-object intersections that must be made,
thereby cutting the overall ray-tracing time considerably.

This new algorithm makes possible the ray tracing of complex scenes by
medium- and small-scale computers. It is hoped that this will enable the power
of ray tracing to be embraced by more people, helping them generate pictures
at the leading edge of computer graphics.

\R Fujimoto, Akira, Takayuki Tanaka, and Kansei Iwata. ``ARTS: Accelerated
Ray-Tracing System.'' \B IEEE CG\&A\}, April 1986, p. 16-26. Also appears in
\B Tutorial: Computer Graphics: Image Synthesis\}, Kenneth I. Joy, Charles
W. Grant, Nelson L. Max, and Lansing Hatfield (eds.), Computer Society Press,
Washington, 1988, p. 148-158. Revision of ``Accelerated Ray Tracing'' by Akira
Fujimoto and Kansei Iwata in \B Computer Graphics: Visual Technology and Art,
Proceedings of Computer Graphics Tokyo '85\}, Tosiyasu L. Kunii (ed.), p. 41-65.

\A
In this paper, we propose algorithms that address the two basic problems
encountered in generating continuous-tone images by ray tracing: speed and
aliasing. We examine previous approaches to the problem and propose a scheme
based on the coherency of an auxiliary data structure imposed on the original
object domain. After investigating both simple spatial enumeration and a hybrid
octree approach, we develop the 3DDDA, a 3D line generator, for efficient
traversing of both structures.

3DDDA provides an order of magnitude improvement in processing speed compared
to other known ray-tracing methods. Processing time is found to be virtually
independent of the number of objects involved in the scene. For large numbers
of objects, this method actually becomes faster than scan-line methods. To
remove jags from edges, a scheme for identifying edge orientation and distance
from pixel center to true edge has been implemented. The time required for
antialiasing depends on the total length of the edges encountered, but it is
normally only a fractional addition to the time needed to produce the scene
without antialiasing.

\R Amanatides, John, and Andrew Woo. ``A Fast Voxel Traversal Algorithm for
Ray Tracing.'' \B Proceedings of Eurographics '87\}, Guy Mar\'echal (ed.),
p. 3-10.

\A
This paper discusses a fast and simple voxel traversal algorithm through a
3D space partition. Going from one voxel to its neighbor requires only two
floating point comparisons and one floating point addition. Also, multiple ray
intersections with objects that are in more than one voxel are eliminated.

\R Arvo, James, and David Kirk. ``Fast Ray Tracing by Ray Classification.''
\B SIGGRAPH '87\}, p. 55-64. Also appears in \B Tutorial: Computer Graphics:
Image Synthesis\}, Kenneth I. Joy, Charles W. Grant, Nelson L. Max, and Lansing
Hatfield (eds.), Computer Society Press, Washington, 1988, p. 196-205.

\A
We describe a new approach to ray tracing which drastically reduces the number
of ray-object and ray-bounds intersection calculations by means of
5-dimensional space subdivision. Collections of rays originating from a common
3D rectangular volume and directed through a 2D solid angle are represented as
hypercubes in 5-space. A 5D volume bounding the space of rays is dynamically
subdivided into hypercubes, each linked to a set of objects which are
candidates for intersection. Rays are classified into unique hypercubes and
checked for intersection with the associated candidate object set. We compare
several techniques for object extent testing, including boxes, spheres,
plane-sets, and convex poyhedra. In addition, we examine optimizations made
possible by the directional nature of the algorithm, such as sorting, caching
and backface culling. Results indicate that this algorithm significantly
outperforms previous ray tracing techniques, especially for complex
environments.

\R Cleary, John G., and Geoff Wyvill. ``Analysis of an Algorithm for Fast Ray
Tracing Using Uniform Space Subdivision.'' \B The Visual Computer\}, Vol. 4,
1988, p. 65-83.

\A
Ray tracing is becoming popular as the best method of rendering high quality
images from three dimensional models. Unfortunately, the computational cost
is high. Recently, a number of authors have reported on ways to speed up this
process by means of space subdivision which is used to minimize the number of
intersection calculations. We describe such an algorithm together with an
analysis of the factors which affect its performance. The critical operation of
skipping an empty space subdivision can be done very quickly, using only
integer addition and comparison. A theoretical analysis of the algorithm is
developed. It shows how the space and time requirements vary with the number
of objects in the scene.

\R Jevans, David A. J., and Brian Wyvill. ``Adaptive Voxel Subdivision for
Ray Tracing.'' \B Graphics Interface '89\}, p. 164-172. Revision of research
report 88/332/44, Computer Science Department, University of Calgary, November
1988.

\A
Although regular subdivision has been shown to be efficient at ray tracing
scenes where objects are evenly distributed, such algorithms perform poorly
when objects are concentrated in a small number of voxels. In this paper,
a method is presented where voxels in a regular grid are examined and
recursively subdivided depending on object density. This integration of regular
and adaptive spatial subdivision methods allows images consisting of large
regularly distributed objects and small dense objects to be ray traced
efficiently. The parameters controlling the coarseness of the voxel grid,
depth of adaptive subdivision trees, and maximum number of polygons per voxel
are varied and their effects on execution time, subdivision time, and memory
use are measured.

\R MacDonald, David. \B Space Subdivision Algorithms for Ray Tracing\}.
Masters Thesis, Computer Science Department, University of Waterloo, 1988.
 
\A
Ray tracing provides computer rendering of synthetic images with many
realistic qualities, but is computationally expensive. Ray tracing requires
testing of rays against a scene to see which objects, if any, are intersected.
The high number of such tests required by typical ray tracers contributes
significantly to the computational expense of ray tracing.
 
An efficient method of reducing the computation involved in the intersection
tests is to organize the objects composing the scene into one of several types
of hierarchical data structures.
 
This thesis describes algorithms for the construction, storage, and traversal
of the space subdivision hierarchy. Methods are suggested for decreasing
computational requirements of the data structure with respect to these three
areas.
 
One suggested strategy for improving performance in all three areas
(construction, storage, and traversal) is implemented for the bintree
structure. The performance of these simulations is compared with
implementations of contemporary methods and some efficiency gains are shown.
 
Further work is suggested, including adaptation of some of the ideas presented
within this thesis to more general types of hierarchical structures.
 
\R Murakami, Koichi, Katsuhiko Hirota and Mitsuo Ishii. ``Fast Ray Tracing.''
\B Fujitsu Science and Technology Journal\}, vol. 24, \#2, June 1988,
p. 150-159.
 
\A
Ray tracing produces images of excellent quality, but it requires lengthy
computations that limit its practical use. This paper discusses two approaches
to shortening ray tracing computation time.
 
The first approach involves partitioning the environment with voxels to reduce
the number of ray-object intersections. Proposed here is a new traversal
algorithm that efficiently traverses the voxel data structure.
 
Experimental data demonstrate that the resulting traversal overhead is small.
 
The second approach involves implementing a ray tracing algorithm on CAP
(Cellular Array Processor) parallel processor. The parallelization of ray
tracing takes advantage of the computational independency of individual rays.
The results demonstrate that, when using the proposed load distribution
scheme, performance increases in proportion to the number of cells used.

\R MacDonald, J. David, and Kellogg S. Booth. ``Heuristics for Ray
Tracing Using Space Subdivision.'' \B The Visual Computer\}, Vol. 6, 1990,
p. 153-166. Also appears in \B Graphics Interface '89\}, p. 152-163.

\A
Ray tracing requires testing of many rays to determine intersections with
objects. A way of reducing the computation is to organize objects into
hierarchical data structures. We examine two heuristics for space subdivision
using bintrees: one based on the intuition that surface area is a good
estimate of intersection probability, and one based on the fact that the
optimal splitting plane lies between the spatial median and the object
median planes of a volume. Traversal algorithms using cross links between
nodes are presented as generalizations of ropes in octrees. Simulations of
the surface area heuristic and the cross link scheme are presented. These
results generalize to other hierarchical data structures.

\s Nonuniform Subdivision

\R Nemoto, Keiji, and Takao Omachi. ``An Adaptive Subdivision by
Sliding Boundary Surfaces for Fast Ray Tracing.'' \B Proceedings of Graphics
Interface '86/Vision Interface '86\}, p. 43-48.

\A
This paper presents an adaptive subdivision algorithm for fast ray tracing
implemented on parallel architecture using a three dimensional computer array.
The object space is divided into several subregions and boundary surfaces for
the subregions are adaptively slid to redistribute loads of the computers
uniformly. Since the shape of the subregions is preserved as orthogonal
parallelepiped the redistribution overhead can be kept small. The algorithm is
quite simple but can avoid load concentration to a particular computer.

Simulation results reveal that the adaptive space subdivision algorithm by
sliding boundary surfaces reduces the computing time to 3/4 - 1/5 as much as
that for the conventional space subdivision algorithm with no redistribution,
which reduces the computing time almost proportionally to the number of
computers.

\R Semwal, S. K., and J. M. Moshell. ``Geometric Issues of the
Slicing Extent Technique for Ray Tracing.'' Technical Report CS-TR-86-17,
Department of Computer Science, University of Central Florida, 1986.

\A
We introduce a new technique for image generation using ray tracing. The
``Slicing Extent Technique'' (SET) partitions object space with slicing
planes perpendicular to all three axes. Planes are dividied into two
dimensional rectangular cells, which contain pointers to nearby objects.

Cell size and the space between slices varies, and is determined by objects'
locations and orientations. Unlilke oct-tree and other space partitioning
methods, SET is not primarily concerned with dividing space into mutually
exclusive volume elements (`voxels') and identifying objects within each
voxel. Instead, SET is based on analysis of projections of objects onto
slicing planes.

The analysis of projections onto planes leads to an interesting geometric
problem of ``marking the cells'' on the various planes so that no ray-object
intersection goes undetected. In this paper, we show that our method of
``marking the cells'' for spheres and polyhedras is sufficient in this sense.
The nature of these extents is analyzed.

In comparison to the existing methods for ray tracing, SET avoids tree
traversal. Preprocessing to create slices is inexpensive and produces a finely
tuned filter mechanism which supports rapid ray tracing.

SET resembles other efforts to speed up ray tracing inasmuch as a two step
process is used. First, an approximate ``filter'' technique eliminates most
possible ray/object collisions. Then an accurate computation evaluates the
remaining possible collisions and provides information for the generation of
subsequent rays.

\R Semwal, S. K. \B The Slicing Extent Technique for Fast Ray
Tracing\}, Ph.D. Dissertation, Department of Computer Science, University of
Central Florida, 1987.

\A
A new technique for image generation using ray tracing is introduced. The
``Slicing Extent Technique'' (SET) partitions object space with slicing planes
perpendicular to all three axes. Planes are divided into two dimensional
rectangular cells, which contain pointers to nearby objects.

Cell size and the space slices varies, and is determined by the objects'
locations and orientations. Unlike oct-tree and other space-partitioning
methods, SET is not primarily concerned with dividing space into mutually
exclusive volume elements (`voxels') and identifying objects within each
voxel. Instead, SET is based on analysis of projections of objects onto
slicing planes.

In comparison to the existing space subdivision methods for ray tracing, SET
avoids tree traversal and exhibits no anomalous behavior. There is no
reorganization when new objects arrive. Preprocessing to create slices is
inexpensive and produces a finely tuned filter mechanism which supports rapid
ray tracing.
 
\R Devillers, Olivier. ``The Macro-regions: an Efficient Space Subdivision
Structure for Ray Tracing.'' \B Proceedings of Eurographics '89\}, W. Hansmann,
F. R. A. Hopgood and W. Strasser (eds.), p. 27-38, 541. Revision of Technical
Report 88-13, Laboratoire d'Informatique de l'Ecole Normale Sup\'erieure,
Paris, France, November 1988.
 
\A
Ray tracing is the usual image synthesis technique which allows rendering of
specular effects. The use of space subdivision for ray tracing optimization is
studied. A new method of subdivision is proposed: the macro-regions. This
structure allows a different treatment of the regions with a low density of
information, and the regions with a high density of information. A theoretical
and practical study of space subdivision methods--grid, octree--and the
macro-regions structure is presented.
 
\R Quek, Lee Hian, and D. D. Hearn. ``Efficient Space-Subdivision Methods in
Ray-Tracing Algorithms,'' Report No. UIUCDCS-R-88-1468, Department of Computer
Science, University of Illinois at Urbana-Champaign, November 1988.
 
\A
Ray tracing provides a simple and powerful tool for the generation of highly
realistic displays. However, it is a computationally expensive approach. A
basic ray-tracing algorithm employing no antialiasing may require several
hours to render a scene of moderate complexity. Methods for attaining higher
picture quality, such as supersampling, adaptive sampling, and distributed
sampling, require even longer ray-processing times. One method for improving
the performance of ray-tracing algorithms is to reduce ray-object intersection
calculations by employing spatial subdivision techniques to group objects in a
scene. Here, we consider some improvements that can be made to
space-subdivision ray tracers by reducing ray-traversal calculations and by
implementing the algorithms on parallel vector architectures.

\R Devillers, Olivier. ``Tools to Study the Efficiency of Space
Subdivision Structures for Ray Tracing.'' \B Proceedings of PIXIM '89\},
p. 467-481.

\A
Space Subdivision structures are often used to improve the performance of ray
tracing. The subject of this article is to study theoretically the effects of
the subdivision on the CPU time. The average number of regions crossed by a ray
is calculated in several cases of subdivision.

With a space subdivision scheme, the complexity of ray tracing is due to two
main factors: computation of the intersections within a region, and computation
of the sequence of regions intersected by a given ray. The complexity of these
two points is studied. The distribution of the objects among the regions is
evaluated, and a method to compute the average number of regions crossed by a
ray for a given method of subdivisions is proposed. This method is applied to
some usual space subdivision techniques: octree, bounding boxes, grid, and
macro-regions.

\R Gigante, Michael. ``Accelerated Ray Tracing Using Non-Uniform
Grids.'' \B Proceedings of Ausgraph '90\}, p. 157-163.

\A
A new space-partitioning method for ray tracing complex environments is
described in this paper. Elements of a scene are placed into a collection of
non-hierarchical, variable-sized voxels.

The creation of this structure is the result of a simple pre-processing step.
In a scheme similar to that used by uniform grid methods, the non-uniform grid
can be traversed very efficiently.

Unlike uniform grid methods, this method generates voxels with approximately
uniform density of primitives per voxel. Its performance is less sensitive to
the type of scene and does not fail on scenes with local, high-density clusters
of primitives.

\R Spackman, John. \B Scene Decompositions for Accelerated Ray Tracing\},
Ph.D. Thesis, The University of Bath, UK, 1990. Available as Bath Computer
Science Technical Report 90/33.

\A
Ray tracing has come to the fore in the computer synthesis of realistic images
over the last decade. This algorithm synthesises a particularly high degree of
realism in both the shading and shape of surfaces. Surface shading calculations
incorporate not only local diffuse and specular radiance but also global
shadowing, multiple reflection and refraction of view and light attenuation,
all according to the laws of optical physics. Complex object shapes may be
modelled as boolean constructs from exact specifications of many common
geometries. A wide range of objects may be modelled exactly without resorting
to polyhedral approximation.

Early implementations of ray tracing synthesised some of the most realistic
images up to that date, but imposed an extremely high computational load for
complex scenes. Synthesis times proved to be linear in object count, and
projected times for scenes of a few thousand objects extended into months on
popular mini-computers. This prevented the wide-spread application of ray
tracing on non-specialised hardware. Various methods have been proposed over
the last few years to improve the efficiency of ray tracing for more viable
synthesis times.

This thesis addresses scene decompositions for the acceleration of ray traced
image synthesis. The decomposition of a globally complicated scene into simpler
local regions is shown to reduce the computational load imposed by ray tracing.
Algorithms are presented for the construction and use of various types of scene
decomposition. Their relative merits are compared and the ``octtree''
decomposition is shown to be particularly suitable for accelerating the
synthesis of complex scenes.

\R Subramanian, K. R. ``Adapting Search Structures to Scene Characteristics for
Ray Tracing'', Ph.D. thesis, Department of Computer Sciences, University of
Texas at Austin, December 1990.

\A
Ray tracing is an important and popular rendering technique in computer
graphics for synthesizing photorealistic images. However, ray tracing, if not
carefully done, can be a computationally expensive technique. A great deal of
research has focused on discovering efficient ways to perform ray tracing. An
important approach to controlling the computational expense has been the use of
geometric search structures to prevent needless ray-object intersection
calculations.

Search structures in current use take advantage of scene characteristics in a
variety of ways to enhance ray tracing performance. Constraints in their
construction can cause inefficiencies and consequent degradation in
performance. Performance comparisons between search structures using timing
benchmarks have shown that no single existing search structure performs best on
all scene models. A knowledge of search structure performance prior to
rendering is therefore important to selecting a search structure for a given
scene. A thorough understanding of the ways in which search structures succeed
in enhancing performance on various types of scenes can also be expected to
lead to improvements in existing techniques.

We present new results in adapting search structures to scene characteristics
for improving the performance of ray tracing. A cost model is developed for
evaluating search structures currently being used in ray tracing. The model has
been successfully used to terminate search structure construction, thus making
it unnecessary to set termination parameters in advance. The model has also
been used with limited success to compare the performance of different search
structures for a given scene.

A detailed experimental study of some of the important properties of search
structures has been performed. This has resulted in a new adaptive search
structure that is based on \E k-d\} trees, a multi-dimensional binary search
structure which outperforms existing methods. Its high performance is primarily
due to the fact that it combines the advantages of such structures based on
space partitioning and those based on bounding volumes. The greater flexibility
of this search structure allows it to terminate automatically at a point where
further subdivision would result in no additional benefits.

Finally, this search structure has been used to render volume models from
scientific applications such as medical imaging and molecular modeling. Its
advantages over traditional volume rendering techniques have been demonstrated.

\R Sung, Kelvin. ``A DDA Octree Traversal Algorithm for Ray Tracing.'' \B
Eurographics '91\}, p. ?.

\A
A spatial traversal algorithm for ray tracing that combines the memory
efficiency of an octree and the traversal speed of a uniform voxel space is
described. A new octree representation is proposed and an implementation of the
algorithm based on that representation is presented. Performance of the
implementation and other spatial structure traversal algorithms are examined.

\S Undersampling

\R Amanatides, John, and Alain Fournier. ``Ray Casting Using Divide and Conquer
in Screen Space.'' \B International Conference on Engineering and Computer
Graphics\}, August 1984, p. 290-296.

\A
Ray tracing the light path from the eye position has been used to model
illumination effects in computer rendered scenes with spectacular results.
In Constructive Solid Geometry (CSG), a similar method limited to the first
surface-ray intersection, known as \E ray casting\} or \E ray firing\}, has
been used. Unfortunately, these methods can be very expensive computationally.
The classic algorithm paradigm of divide and conquer has been used to reduce
the computations, by ``boxing'' and/or subdividing the objects to rapidly
eliminate non-intersecting objects.

We introduce here a new algorithm, using divide and conquer in screen space
and ray casting in object space at the same time. Instead of ``firing'' one
ray per pixel, rays (or more exactly cones with the apex at the eye) covering
recursive subdivisions of the screen are fired. Quick inclusion tests in
object space are used to decide if an object is potentially visible for this
ray, and if further subdivisions are necessary.

The main advantage over simple ray casting is that far less intersection
calculations are done, and that antialiasing is easily built into it.

\R Hashimoto, Akihiko, Taka-aki Akimoto, Kenji Mase, and Yasuhito Suenaga.
``Vista Ray-Tracing: High Speed Ray Tracing Using Perspective Projection
Image.'' \B New Advances in Computer Graphics, Proceedings of CG
International '89\}, R. A. Earnshaw and B. Wyvill (eds.), p. 549-561.

\A
This paper presents a new high speed algorithm of ray-tracing named Vista
Ray-tracing. In Vista Ray-tracing, time consuming intensity calculations are
done only for ``active'' pixels which really need precise ray-tracing, while
the intensity of ``moderate'' pixels in calculated by interpolation. The
perspective projection image, or Vista, is generated at the first stage to be
used as a guide map in active pixel selection. In this paper, a new method for
obtaining Vistas for CSG models of quadratic surface objects is presented as a
key technology. A new texture mapping algorithm is also presented. Vista
Ray-tracing is actually 16-75 times faster than standard ray-tracing, and can
be even faster if other acceleration methods are employed. Consequently, Vista
Ray-tracing is very useful for intermediate processes in making various images
for TV animation, movies, high definition television, printing, etc.

\R Akimoto, Taka-aki, Kenji Mase, and Yasuhito Suenaga. ``Pixel Selected Ray
Tracing.'' \B IEEE CG\&A\}, July 1991, p. 14-22. Revision of same paper also
appears in \B Proceedings of Eurographics '89\}, W. Hansmann, F. R. A. Hopgood
and W. Strasser (eds.), p. 39-50, 542.

\A
This paper presents a new ray-tracing acceleration technique called Pixel
Selected Ray-Tracing (PSRT). PSRT uses undersampling based on Iterative
Central Point Selection (ICPS) along with checking for similarities among
trees in neighboring pixels. By using ICPS and trees, the largest danger of
missing object borders can be drastically reduced.

Although the speed increase attributable to PSRT varies with the image
generation environment, according to experiments comparing PSRT with standard
ray-tracing, PSRT is 2.6 to 8.2 times faster than standard ray-tracing for
512 by 512 pixel images, maintaining the same visual image quality.

It is true that images generated by this method may contain very small errors.
However, such errors can be reduced and may be made visually negligible by
using ICPS and the trees of ray-object intersections to check for similarities.

\S Testing and Analysis

\R Fitzhorn, Patrick A. \B Realistic Image Synthesis: A Time Complexity
Analysis of Ray Tracing\}, M.S. Thesis, Colorado State University, 1982.

\A
Ray tracing as an image synthesis algorithm has gained considerable prominence
in the world of graphics and computer-aided-design since its conception by
Goldstein and Appel working separately in the late 1960's. Image of complex
scenes synthesized using this algorithm have approached quality which has not
yet to be matched by any other technique in computer graphics.

The technique called ray tracing is a simulation of a camera-like model, in
which the viewer sits at an arbitrary viewpoint in the imaginary world,
peering out into the simulated environment through a display window made up
of discrete elements called pixels. These pixels take on the colors and hues
of the environment as simulated light rays emanate from the viewer, pass
through a pixel and are projected into the environment to reflect and refract
about until the pixel can be illuminated with an approximation (hopefully
close) of the objects intersected in the light path. Note that this is the
reverse of actual light paths in the real world, where rays emanate from some
source, and are finally perceived by the viewer. The ray tracing technique
reverses this to make the problem tractable.

Unfortunately, although this technique synthesizes pictures with extreme
realism, the computational expense is extremely large. It is the goals of this
paper to examine the technique in a theoretical format, in the hopes of
decreasing execution time requirements by using more efficient algorithms.
Otherwise, point out sound theoretic reasons why this cannot be done.

After an initial overview of ray tracing in general, a formal model is
described, along with the optical properties that must be followed in order to
synthesize realistic images. These models are then converted into algorithms
which are analyzed. These analyzations tend to prove that dramatic execution
speed increases using strict ray tracing is unlikely. Finally, special purpose
hardware for ray tracing is examined, with apparent usefulness in the
reduction of execution time requirements.

\R Kingdon, Stewart. \B Speeding Up Ray-Scene Intersections\}, Masters Thesis,
University of Waterloo, 1986.

\A
Ray tracing produces computer generated images of unparalleled realism. Among
the phenomena rendered are shadows, reflections, refractions, penumbrae, depth
of field and motion blur. Unfortunately, ray tracing is also the most
computationally expensive rendering technique used in computer graphics.

This thesis provides an overview of current techniques used to improve the
performance of ray tracing as well as a more detailed examination of the most
promising of these techniques, scene structuring.

A simulation was performed to compare the performance of three existing scene
structuring algorithms. Their performance, as measured by the number of objects
tested during the intersection of a ray with the scene, was found to be
\$O(N\^x\})\$ with \$x < 1\$, where \$N\$ is the number of objects in the
scene. All of the algorithms offer a considerable advantage over the naive ray
tracing algorithm whose performance is \$O(N)\$.

Finally, some recommendations are made as to which scene structuring algorithm
offers the greatest performance gain.

\R Haines, Eric. ``A Proposal for Standard Graphics Environments.'' \B IEEE
CG\&A\}, November 1987, p. 3-5.

\A
[Describes the Standard Procedural Database and ideas for creating some
graphics benchmark scenes.]

\R Waij, Rudi. \B Acceleration of Ray Tracing\}, Masters Thesis, Delft
University Press, Delft University of Technology, 1988.

[No abstract. Excerpt from Preface]

\A
This thesis explains the principles of ray tracing and constructive solid
geometry (Chapter 1 and 2). Some approaches to acceleration of ray tracing are
described in Chapter 3. Two accelerated ray tracing algorithms have been
selected for implementation. Chapter 4 describes the implementation of a ray
tracing program that uses bounding volumes. The implementation of a ray tracer
that uses space subdivision is explained in chapter 5. In Chapter 6 the two
methods are compared. It contains timings, conclusions, and ideas for further
research.
 
\R Robb, Paul, and Barbara Pawlowski. ``Computer Ray Tracing Speeds.'' \B
Applied Optics\}, Vol. 29, \#13, May 1 1990, p. 1933-1939.
 
\A
The results of measuring the ray trace speed and compilation speed of
thirty-nine computers in fifty-seven configurations, ranging from personal
computers to supercomputers, are described. A correlation of ray trace speed
has been made with the LINPACK benchmark which allows the ray trace speed to
be estimated using LINPACK performance data. The results indicate that the
latest generation of workstations, using CPUs based on RISC (Reduced
Instruction Set Computer) technology, are as fast or faster than mainframe
computers in compute-bound situations.

\S Object Modeling

\s CSG (Constructive Solid Geometry)

\R Bronsvoort, Willem F., Jarke J. van Wijk, and Frederik W. Jansen. ``Two
Methods for Improving the Efficiency of Ray Casting in Solid Modelling.''
\B CAD\}, Vol. 16, \#1, January 1984, p. 51-55.

\A
In solid modelling based on constructive solid geometry and primitive
instancing, ray casting is a very suitable technique for visualization of
models on a raster display. In its present form, it is, however, too
inefficient for interactive use.

Two methods for improving the efficiency are given here. The first uses
scan-line interval enclosures instead of box enclosures, and also bypasses
non-contributing nodes during each traversal of the CSG (constructive solid
geometry) tree. The second refines the image step by step by subdivision,
thereby avoiding explicit computation of the intensities of many pixels of the
image. The second method reduces computing time more than the first, but has
the disadvantage that slivers may occasionally be lost from the image.

\R Cordonnier, E., C. Bouville, J. L. Dubois, and I. Marchal. ``Creating CSG
Modelled Pictures for Ray-Casting Display.'' \B Proceedings of Eurographics
'85\}, Carlo E. Vandoni (ed.), p. 171-182.

\A
3D-picture synthesis systems used for instance in the audio-visual field or
networked services require the implementation of easy-to-use aids to
composition. This particular composition software realizes the sizing and
locating of even complex CSG objects in a simple direct manner.

The ray-casting method is used for display and designation.

\R Jansen, F. W. ``A CSG List Priority Hidden Surface Algorithm.''
\B Proceedings of Eurographics '85\}, Carlo E. Vandoni (ed.), p. 51-62.

\A
Several algorithms exist for visualizing geometric models defined by
constructive solid geometry (CSG). Each of these algorithms is based on
standard hidden surface methods, such as ray tracing, scan-line, and z-buffer
algorithms. In this paper a CSG list priority algorithm is described that is
combined with a ray tracing algoritm in the use of a spatial subdivision
technique and a CSG list structure to exploit CSG coherence. The combined
algorithm is designed for interactive viewing and high quality rendering
of CSG models with faceted primitives.

\R Kunii, Tosiyasu L., and Geoff Wyvill. ``CSG and Ray Tracing Using
Functional Primitives.'' \B Computer-Generated Images: The State of the Art,
Proceedings of Graphics Interface '85\}, N. Magnenat-Thalmann and D. Thalmann
(ed.), p. 137-152.

\A
A simple system is described for computer aided design by constructive
solid geometry (CSG). The system allows the design of engineering components
by combining `basic components' which represent shapes produced by
standard machining operations.

The system has for significant original features:

1. The primitive components are described in an object orieinted fashion, data
plus procedures.

2. A new kind of octree structure is used to render various displays from
descriptions.

3. Certain objects can be directly associated with components of tool paths.
For example, a cylindrical object might represent a drill moving along its
length or a prism might represent the shape of material cut by a milling too
sweeping horizontally. An object built from these basic objects can, in
principle, be cut using combinations of their associated tool paths.

4. The system consists of four conceptual modules with well-defined interfaces.
One module, for example, is the set of primitive objects and their associated
procedures. Another is the octree generator. Because of this design technique,
it is easy to modify or even replace modules. This meta-structure provides a
general, if informal method of describing CSG systems.

\R Wyvill, Geoff, and Tosiyasu L. Kunii. ``A Functional Model for Constructive
Solid Geometry.'' \B The Visual Computer\}, Vol. 1, 1985, p. 3-14.

\A
A system of constructive solid geometry (CSG) enables an engineering designer
to compose three dimensional (3D) shapes by combining simpler ones. Most
existing systems, however, actually represent solid shapes as boundaries of
surfaces patches. At the Kunii Laboratory, University of Tokyo, we have
produced an experimental system in which solids are modelled functionally by
procedures which describe their properties. These ``primitive objects'' are
combined with the aid of a new ``octree'' structure. Careful study of the data
structures in this system reveals some interesting aspects of program
efficiency.

\R Gervautz, Michael. ``Three Improvements of the Ray Tracing Algorithm for
CSG Trees.'' \B Computers \& Graphics\}, Vol. 10, \#4, 1986, p. 333-339.

\A
Ray tracing is one of the most powerful techniques for image synthesis today.
The most beautiful pictures in computer graphics were made by this method.
Unfortunately, the computational expense and the computation time are very
high. For reduction of computational effort in this paper three improvements
for the ray tracing algorithm will be introduced. Two of them are extensions of
existing improvements, the third is a new idea: (1) use of enclosures in the
object tree; (2) bounding the ray length and (3) dynamical temporary object
trees. These improvements are independent and therefore can be used separately
or together. They are for ray tracing objects described in a CSG model. The
improvements can also be used for secondary rays.

\R van Wijk, Jarke J. \B On New Types of Solid Models and Their
Visualization with Ray Tracing\}, Ph.D. Thesis, Delft University Press, Delft
University of Technology, 1986.

\A
[No abstract. The following is taken from the Summary.]

Solid modelling is a technique for the representation of the geometry of
objects in CAD/CAM-systems. A major technique within sold modelling is
Constructive Solid Geometry (CSG). Here an object is defined by applying the
set operations union, difference, and intersection on transformed (translated,
rotated, scaled) instances of a set of primitive objects, such as sphere,
block, and cylinder. The ray tracing technique can be used for generating
shaded images of objects defined with CSG.

The shape domain of current solid modellers based on CSG is often too
restrictive for application in, for instance, industrial design. The subject
of this thesis is the development of techniques to define additional types of
shapes, which can be used as primitive elements in solid modelling systems.
Algorithms for the evaluation of these objects with ray tracing are presented.

The set of discussed shapes includes objects defined by translational and
rotational sweeping, objects that result from sweeping a sphere, blends and
fillets for quadric surfaces, and some types of objects bounded by free-form
surfaces. A procedural modelling language is presented that allows the user to
describe regular structures in geometric models in a compact way.

\R Wyvill, Geoff, Tosiyasu L. Kunii, and Yasuto Shirai. ``Space
Division for Ray Tracing in CSG.'' \B IEEE CG\&A\}, April 1986, p. 28-34.

\A
A system of Constructive Solid Geometry (CSG) enables an engineering designer
to compose three-dimensional shapes by combining simpler ones. Definitions of
such objects are represented by tree structures or direct acyclic graphs.

Most existing systems convert this representation to a more conventional
boundary representation of the solids in order to render pictures from the
model. More recently, a number of systems have been described that render the
pictures directly from the CSG structure. We describe such a system. We render
a scene by ray tracing from a directed acyclic graph. This process is made
efficient for large models by using an adaptive method of space division to
reduce the number of intersection calculations needed.

\R Youssef, Saul. ``A New Algorithm for Object Oriented Ray Tracing.'' \B
Computer Vision, Graphics, and Image Processing\}, Vol. 34, 1986, p. 125-137.

\A
A new algorithm for ray tracing object oriented environments is presented. The
new algorithm promises significant savings in CPU time compared with the
standard Constructive Solid Geometry (CSG) algorithm. In particular, few
ray-surface intersections are calculated, all sorting is eliminated, and there
is no binary tree traversal. The new algorithm is bounded in CPU cost by
\$O(N)\$ for \$N\$ objects compared with \$O(N\^2\})\$ for CSG.

\R Arnaldi, Bruno, Thierry Priol, and Kadi Bouatouch. ``A New Space
Subdivision Method for Ray Tracing CSG Modelled Scenes.'' \B The Visual
Computer\}, Vol. 3, 1987, p. 98-108.

\A
A new algorithm for space tracing with CSG modelled scenes is presented. Space
is divided in an irregular fashion to fit the objects as closely as possible.
For this reason, primitive minimal bounding boxes are computed. Space
subdivision is achieved in two steps: partitioning in projection plane and
depth partitioning. A set of 3D regions named cells are then created. A
Boolean CSG tree is distributed into the cell structure to form in each cell
the minimal boolean CSG tree using the relevant primitives. The searching
process for the ``next cell'' along the ray path is performed by using a local
data structure associated with each cell. The goal of this structure is to
link the cells together. An improvement, named ``mailbox,'' for all space
tracing algorithms is detailed. Results are presented for two scenes to
compare this new algorithm with Roth's algorithm.

\R Bouatouch, Kadi, M. O. Madani, Thierry Priol, and Bruno Arnaldi. ``A New
Algorithm of Space Tracing Using a CSG Model.'' \B Proceedings of
Eurographics '87\}, Guy Mar\'echal (ed.), p. 65-78.

\A
This paper describes a new algorithm of space tracing. Scenes are modeled by a
CSG tree. Space is subdivided regularly into 3D regions called boxes. With
each box is associated a subtree which is the restriction of the whole scene
CSG tree to primitives belonging to this box. A 3D grid is ued to access
boxes.

\R Wyvill, G., and P. Sharp. ``Volume and Surface Properties in CSG.''
\B New Trends in Computer Graphics, Proceedings of CG International '88\},
Nadia Magnenat-Thalmann and Daniel Thalmann (eds.), Springer-Verlag, p. 257-267.

\A
If we use a red drill to make a hole in a blue block, the inside of the hole
will still be blue. To simulate this process in a CSG system, the we subtract
red cylinder from the blue block. The hole's surface belongs to the cylinder
but it takes it color from the block.

We present algorithms for elucidating the correct colors from CSG models
and an application in design for wood turning is described.

\R Getto, Philip. ``Fast Ray Tracing of Unevaluated Constructive Solid
Geometry Models.'' \B New Advances in Computer Graphics, Proceedings of CG
International '89\}, R. A. Earnshaw and B. Wyvill (eds.), p. 563-578.

We present a refinement of the ray tracing, algorithm, for use with unevaluated
constructive solid geometry models. Bounding enclosures around the children of
a part are combined into a tree with nearly optimal minimum expected number of
extent-ray intersections. An approximate evaluation of the expression
represented by the part can be evaluated on the enclosure-ray intersections to
find the subset of children that might be hit by a ray. These candidate
children are then used to evaluate the expression exactly. Several critieria
are suggested which allow early termination of the exact expression evaluation.

\R Morris, D. T., and P. M. Dew. ``Dynamic Dataflow Algorithms for Ray
Tracing CSG Objects.'' \B Parallel Processing for Computer Vision and
Display\}, P. M. Dew, R. A. Earnshaw, and T. R. Heywood (eds.), Addison-Wesley
Publishing Company, Reading, Massachusetts, 1989, p. 452-460.

\A
This paper describes how solid objects may be rendered by use of dynamic
dataflow techniques. Particular emphasis is given to the ray-tracing
algorithm. The objects are described by constructive solid geometry. The
algorithms are designed to be executed on a processor farm coupled with a
data-driven dataflow machine. Many of the limitations of previous approaches,
such as the Kedem-Ellis ray-casting machine are overcome. For example, the
size of the objects that can be drawn directly is increased, the shading
computations are made more efficient and there is better hardware utilization.

\R Salesin, David, and Jorge Stolfi. ``Rendering CSG Models with a ZZ-Buffer.''
\B SIGGRAPH '90\}, p. 67-76.

The ZZ-buffer is a simple acceleration scheme for ray tracing that can be
applied to a wide variety of scenes, including those with small features,
textured and transparent surfaces, shadows and penubrae, and depth-of-field
effects. In this paper, we describe how the ZZ-buffer algorithm can be adapted
to the rendering of scenes defined by constructive solid geometry.

\R Jansen, Frederik W. ``Depth-Order Point Classification Techniques for CSG
Display Algorithms.'' \B ACM TOG\}, Vol. 10, \#1, January 1991, p. 40-70.

\A
Constructive Solid Geometry (CSG) defines objects as Boolean combinations
(CSG trees) of primitive solids. To display such objects, one must classify
points on the surfaces of the primitive solids with respect to the resulting
composite object, to test whether these points lie on the boundary of the
composite object or not. Although the point classification is trivial compared
to the surface classification (i.e.\ the computation of the portion of the
faces of primitive solids that lie on the boundary of the composite object),
for CSG models with a large number of primitive solids (large CSG trees), the
point classification may still consume a considerable fraction of the total
processing time. This paper presents an overview of existing and new
efficiency-improving techniques for classifying points in depth order. The
different techniques are compared through experiments.

\s Objects Defined by Sweeps and Revolutions

\R van Wijk, Jarke J. ``Ray Tracing Objects Defined by Sweeping a Sphere.''
\B Proceedings of Eurographics '84\}, Ketil B\o and Hugh A. Tucker
(ed.), p. 73-82.

\A
The basic calculation underlying ray tracing is that of the intersection of a
line with the surfaces of the object. A method is presented here for performing
this calculation for a new and powerful class of objects, those defined by
sweeping a sphere of varying radius along a 3D trajectory. When polynomials are
used for the parametrization of the center and radius of the sphere, the
intersection problem reduces to the location of the roots of a polynomial. An
implementation is presented, together with sample applications.

\R van Wijk, Jarke J. ``Ray Tracing Objects Defined by Sweeping
Planar Cubic Splines.'' \B ACM TOG\}, Vol. 3, \#3, July 1984, p. 223-237.

\A
The crucial step in a program based on ray tracing is the calculation of the
intersection of a line with an object. In this paper, algorithms are presented
for performing this calculation for objects defined by sweeping a planar
cubic spline through space. Translational, rotational, and conic sweeping are
treated. Besides solutions for the exact calculation, rectangle tests for
improving efficiency are given. Possible extensions and improvements are
discussed.

\R Bronsvoort, Willem F., and Fopke Klok. ``Ray Tracing Generalized
Cylinders.'' \B ACM TOG\}, Vol. 4, \#4, October 1985, p. 291-303. Revision of
``Ray Tracing Generalized Sweep-Defined Objects.'' 84-36, Dept. of Mathematics
and Informatics, Delft U. of Tech., 1984.

\A
\R Bronsvoort, Willem F. Corrigendum to ``Ray Tracing Generalized
Cylinders.'' \B ACM TOG\}, Vol. 6, \#3, July 1987, p. 238-239.

\A
An algorithm is presented for ray tracing generalized cylinders, that is,
objects defined by sweeping a two-dimensional contour along a three-dimensional
trajectory. The contour can be any ``well-behaved'' curve in the sense that it
is continuous, and that the points where the tangent is horizontal or vertical
can be determined; the trajectory can be any spline curve. First a definition
is given of generalized cylinders in terms of the Frenet frame of the
trajectory. Then the main problem in ray tracing these objects, the
computation of the intersection points with a ray, is reduced to the problem of
intersecting two two-dimensional curves. This problem is solved by a subdivision
algorithm. The three-dimensional normal at the intersection point closest to
the eye point, necessary to perform the shading, is obtained by transforming
the two-dimensional normal at the corresponding intersection point of the two
two-dimensional curves. In this way it is possible to obtain highly realistic
images for a very broad class of objects.

\R van Dijk, C. G. C. \B Ray Tracing Profiled Generalized Cylinders\},
Masters Thesis, Delft University Press, Delft University of Technology, 1989.

\A
Ray tracing is a popular method to generate realistic images of
three-dimensional objects. Objects displayed by means of ray tracing are often
constructed out of primitive objects such as blocks and cylinders, combined
with Constructive Solid Geometry operations. Profiled generalized cylinders
constitute another, very flexible class of primitive objects. An algorithm
for ray tracing profiled generalized cylinders already exists, but it is very
slow, and it is not compatible with CSG operations. To accelerate the ray
tracing of profiled generalized cylinders, two new algorithms and several
optimizations are implemented. Also a method is developed that allows the
application of the CSG operations to profiled generalized cylinders.

\R Bronsvoort, Willem F., Peter R. van Nieuwenhuizen, and Frits
H. Post. ``Display of Profiled Sweep Objects.'' \B The Visual Computer\},
Vol. 5, 1989, p. 147-157.

\A
A class of free-form solids called profiled sweep objects is defined by four
parametric curves: a 2D contour (cross-section), a 3D trajectory (spline), and
two profile curves, which control the scaling of the contour as it traves along
the trajectory. Subclasses of this are profiled prisms, which have a linear
trajectory, and profiled generalized cylinders, which have an arbitrary 3D
trajectory.

Details for ray tracing these two subclasses are presented. Example code and
images are also given.

\R Burger, Peter, and Duncan Gillies. ``Rapid Ray Tracing of General
Surfaces of Revolution.'' \B New Advances in Computer Graphics, Proceedings
of CG International '89\}, R. A. Earnshaw and B. Wyvill (eds.), p. 523-532.

\A
Previous ray tracing of general surfaces of revolution involved the solution of
sixth order algebraic equations by iteration. When the spline curve which
generates the surface is expressed in the form: \$r\^2\} = Az\^3\} + Bz\^2\} +
Cz + D\$, the resulting equations become cubic which can be solved directly.
Smooth surfaces can be generated by using any of the well known cubic spline
techniques. Further reduction of processing time can be achieved with a
hierarchical description of the objects and easily tested bounding volumes.
These techniques have been applied to scenes containing a general surface of
revolution for which multiple reflections and shadows can be calculated on a
personal computer.

\R Bidasaria, H. B. ``Ray Tracing Surfaces of Revolution Using a Simplified
Strip-Tree Method.'' \B Proceedings of the 1990 ACM Eighteenth Annual Computer
Science Conference\}, 1990, p. 427. Only abstract appears. *

\A
In ray tracing a surface of revolution, the problem of finding the point of
intersection of an arbitrary ray with the surface of revolution can be reduced
to that of finding a point of intersection between two curves in a plane -- the
so called cut plane. In the cut plane, by using a local coordinate system
\$(x' = x\^2\}, z' = z\^2\})\$ instead of \$(x, z)\$ where \$z\$ is along the
direction parallel to the axis of the surface of revolution, and then further
translating the origin of the coordinate system along the \$x'\$ axis
(depending upon the ray), the curve(s) of intersection of the surface of
revolution with the cut plane are expressed exactly by the square radial curve
defining the surface of revolution itself. We need to find the point(s) of
intersection between this square radial curve of the surface of rotation by a
variation of the usual strip-tree such that the direction of the sides of the
rectangles corresponding to different nodes are parallel to the axes of the
local coordinate system, instead of being in arbitrary directions. The terminal
nodes in the strip-tree contain the segments of the square radial curve divided
approximately equally lengthwise. The method works efficiently for all cases
with a smooth radial curve or a piecewise smooth radial curve.

\R Bronsvoort, Willem F. \B Direct Display Algorithms for Solid Modelling\},
Delft University Press, Delft University of Technology, Ph.D. Thesis, 1990.

\A
[no abstract, the following is taken from Summary]

In this thesis algorithms are discussed for displaying geometric models of
three-dimensional objects. An important use of such algorithms is in
CAD/CAM-systems to give the designer insight in the shape of the design.

Of particular concern here are direct display algorithms for constructive
solid geometry models and generalized cylinders. `Direct' in this context
means that a solid object is displayed without the need to convert its model
into a boundary representation providing the information about faces, edges
and vertices required by the standard display algorithms.

For constructive solid geometry models, the starting point is a collection of
primitive objects, such as cubes, spheres and cylinders, that can be combined
into more complex objects with set operations. The two alternatives for
displaying such models, namely conversion into a boundary representation
followed by display with a standard algorithm, and direct display with an
adapted algorithm, are weighed. An overview of direct display algorithms for
constructive solid geometry models is also given.

An efficient standard algorithm for display of models approximated with planar
faces is the scanline algorithm. This algorithm can be extended to a direct
display algorithm for constructive solid geometry models in a rather
straightforward way. A detailed description is given of such an algorithm.

Next, several methods are described to further increase the efficiency of such
scanline algorithms for constructive sold geometry models. First, a number of
techniques are discussed that reduce the extra time required for processing
constructive solid geometry models. Second, an algorithm for larger areas of
the screen per step than a scanline algorithm does; a version of this
algorithm for producing line drawings is also given. Third, local updating
of an image, in which only those parts are redisplayed that may have changed
since the previous display, is discussed. For all methods, results are given
in the form of images and computing times.

Generalized cylinders are objects defined by an arbitrary two-dimensional
contour, or cross-section, and an arbitrary three-dimensional trajectory along
which to sweep the contour. With profiled generalized cylinders, the contour
can be scaaed along the trajectory in two perpendicular directions according
to two profile curves. An exact definition of such objects is given. Here also
the alternative for display, namely conversion into a boundary representation
followed by display with a standard algorithm, and direct display with a
special algorithm, are compared.

Next, two direct display algorithms for generalized cylinders are described.
The first is a ray tracing algorithm with which high-quality images with
various optical effects can be produced, but that requires much more
computing time. The second is an algorithm that scans the surface of the
object in a way tht generates enough points to produce a smooth image without
gaps; this algorithm is simpler and much more efficient than the ray tracing
algorithm, but the image quality obtainable is lower.

Finally, some conclusions are drawn, and directions for further research on
direct display algorithms for solid models are identified.

\s Explicit Representations

\R Kajiya, James T. ``Ray Tracing Parametric Patches.'' \B SIGGRAPH '82\},
p. 245-254.

\A
This paper describes an algorithm that uses ray tracing techniques to display
bivariate polynomial surface patches. A new intersection algorithm is developed
which uses ideas from algebraic geometry to obtain a numerical procedure for
finding the intersection of a ray and a patch without subdivision. The
algorithm may use complex coordinates for the (\$u\$,\$v\$)-parameters of the
patches. The choice of these coordinates makes the computations more uniform,
so that there are fewer special cases to be considered. In particular, the
appearance and disappearance of silhouette edges can be handled quite
naturally. The uniformity of these techniques may be suitable for
implementation on either a general purpose pipelined machine, or on special
purpose hardware.

\R Steinberg, Herbert A. ``A Smooth Surface Based on Biquadratic Patches.''
\B IEEE CG\&A\}, September 1984, p. 20-23.

\A
[No abstract. Introduction]

The Coons patch description is a widely used procedure for computer
representation of surfaces for graphics. To represent surfaces with normal
that are continuous, or have prescribed discontinuities, we usually specify the
surface by a bicubic polynomial in two variables. That is, the position vector
\B \$P\$\} is defined as a function of abstract variables \$u\$ and \$v\$ in a
patch, defined by \$(0 \< u, v \< 1)\$.

Although this approach is viable for netlike graphics representations, major
problems exist in hidden-line elimination and shaded-image rendering. The basic
algorithm used for the solution to this problem is known as ray tracing. It
determines the points of intersection of a line in space and the surfaces in
question. (The visible surface is given as that surface with the point of
intersection closest to the synthetic image plane or eyepoint.) When bicubic
patches are used, the determination of the point of intersection requires the
solution of a polynomial of a degree as high as 18--a very difficult numerical
problem.

This article describes an alternative approach to the problem that requires
only biquadratic patches. The key to this simplification is the introduction
of extra knots into the system. With the extra knots, the degree of the
ray-tracing polynomial is at most eight.

\R Toth, Daniel L. ``On Ray Tracing Parametric Surfaces.'' \B SIGGRAPH '85\},
p. 171-179.

\A
A new method for ray tracing parametric surfaces is presented. The new
algorithm solves the ray surface intersection directly using multivariate
Newton iteration. This provides enough generality to render surfaces which
could not be ray traced using existing methods. To overcome the problem of
finding a starting point for the Newton algorithm, techniques from Interval
Analysis are employed. The results are presented in terms of solving a general
nonlinear system of equations \$f(x) = 0\$, and thus can be extended to a large
class of problems which arise in computer graphics.

\R Barr, Alan H. ``Ray Tracing Deformed Surfaces.'' \B SIGGRAPH '86\},
p. 287-296.

\A
A collection of new methods for ray tracing differentiable surfaces is
developed. The methods are general, and extend the set of ``ray-traceable''
surfaces suitable for use in geometric modeling. We intersect a ray
\u\$l\$\} = \u\$a\$\}\$t\$ + \u\$b\$\}, \$t > 0\$ with a parametric
surface \u\$x\$\} = \u\$f\$\}\$(u,v)\$, and with implicit surfaces
\$f(x,y,z) = 0\$. A smooth surface is treated as a deformation of a flat sheet;
the intersection problem is converted to a new coordinate system in which the
surfaces are flat, and the rays are bent. We develop methods for providing
good initial estimates of the parametric intersection values, and a
``closeness criterion,'' to reduce computation. These same criteria help
substitute a set of simpler surfaces for the more complex surface. The
parametric method produces the intersection values of \$u, v,\$ and \$t\$. These
are suitable for shading calculations and for mapping textures onto the
surface; they can also produce the local coordinate frame values, suitable for
anisotropic lighting models.

\R Joy, Kenneth I., and Murthy N. Bhetanabhotla. ``Ray Tracing
Parametric Surface Patches Utilizing Numerical Techniques and Ray Coherence.''
\B SIGGRAPH '86\}, p. 279-285.

\A
A new algorithm for ray tracing parametric surface patches is presented. The
method uses quasi-Newton iteration to solve the ray/surface intersection
and utilizes ray-to-ray coherence by using numerical information from
adjoining rays as initial approximations to the quasi-Newton algorithm.
Techniques based upon object space subdivisions are used to insure convergence
to the correct intersection point. Examples are given of the use of the
algorithm in scenes containing B\'ezier surface patches. Results show that
a significant number of ray/surface intersections on these parametric surface
patches can be found using very few iterations, giving a significant
computational savings.

\R Sweeney, Michael A. J., and Richard H. Bartels. ``Ray Tracing Free-Form
B-Spline Surfaces.'' \B IEEE CG\&A\}, February 1986, p. 41-49.

\A
We present a method for using ray tracing to render spline surfaces--one
that is suitable for any object generated from control vertices via
tensor-product B-splines. The method derives from Kajiya's work on ray tracing
procedurally defined surfaces and make use of two preprocessing steps. One
involves the control-vertex refinement recurrences due to Riesenfeld \E et
al\}.\ and the second generates a tree of nested bounding boxes. Intersection
testing involves running Kajiya's algorithm on the tree, followed by two or
three (on the average) iterations of Newton's method.

\R Levner, Geoff, Paolo Tassinari, and Daniele Marini. ``A Simple, General
Method for Ray Tracing Bicubic Surfaces.'' \B Computer Graphics 1987 -
Proceedings of CG International '87\}, Tosiyasu L. Kunii (ed.), Springer-Verlag,
p.285-302. Also appears in \B Theoretical Foundations of Computer Graphics
and CAD\}, NATO ASI Series, Vol. F40, Springer-Verlag, 1988, p. 805-820.

\A
A software package for creating and ray tracing bicubic surfaces is described.
The software supports Beta-splines as well as B\'ezier and Hermite surfaces.
We present a simple algorithm for calculating the intersection of a ray with a
surface, and an interactive modeler is also presented for creating bicubic
surfaces.
 
\R Peterson, John W. ``Ray Tracing Spline Surfaces with Motion Blur.''
Department of Computer Science, University of Utah, 1987.
 
\A
An algorithm for ray tracing B-spline surfaces is described. It is based on
preprocessing the surface with adaptive subdivision to build a polygonal
representation of the surface, and hierarchical bounding volumes around the
polygons. This allows for very efficient ray surface intersections, and avoids
complex numerical methods. The algorithm is extended to allow for motion blur
without sacrificing efficiency. An adaptive anti-aliasing method is also
presented.

\R Yang, Chang-Gui. ``On Speeding Up Ray Tracing of B-Spline Surfaces.''
\B CAD\}, 1987, p. 122-130.

\A
This paper presents an algorithm that has been implemented to speed up the ray
tracing of B-spline surfaces. The method uses bounding-box trees instead of the
traditional bounding volumes, to effectively reduce the number of
time-consuming ray-surface intersection calculations. A bounding-box tree is
an octree obtained by recursively subdividing the bounding box of a B-spline
patch, with each non-empty leaf serving as a container of some points on the
patch. In the ray-surface inersection test, every tree is searched recursively
for intersection with a ray. If the ray hits a nonleaf box, the intersection
tests are made for the `children' of the box. If a ray hits a leaf box, the
intersection of the ray and the patch must be within the box or very close to
it, provided that the size of leaf boxes is not too large. The mean parameter
values of the points contained in the box provide good initial guesses for
the Newton iteration for the calculation of the parameter values of the
intersection point. The coordinates and the normal are then determined from
the parameter values to calculate the intensity at the point. The use of image
coherence, along with some other ways for further improving the speed of the
algorithm, are also discussed. The techniques introduced in this paper also
apply to other kinds of parametric surfaces.

\R Bouatouch, Kadi. ``Theoretical Developments on Polygonal Approximation of
Parametric Surfaces for Ray Tracing.'' \B Computer Graphics Forum\}, Vol. 7,
1988, p. 257-264.
 
\A
Some theoretical extensions are brought of Koparkar and Mudur's method which
deals with a polygonal approximation of parametric surfaces using potential
extrema. The proposed extensions allow the determination of both the
existence and the equation of a curve solution of potential extrema. Solutions
are given to solve the crack problem and to avoid the artifacts due to an
inexact ray-surface intersection point near the silhouette or on the higher
curvature regions. Moreover, two methods of ray tracing surfaces are proposed.

\R Giger, Christine. ``Ray Tracing Polynomial Tensor Product Surfaces.'' \B
Proceedings of Eurographics '89\}, W. Hansmann, F. R. A. Hopgood and W. Strasser
(eds.), p. 125-136, 544.

\A
With regard to ray tracing algorithms for polynomial tensor product surfaces,
the most time-critical step is to find an intersection point of a ray and a
surface. In this case it proves to be very difficult to decide whether
numerical methods will converge to the correct solution. In this paper we
present a new method based on numerical algorithms which is suitable to solve
the intersection problem. We mention how to force correct convergence and give
some information about techniques to speed up the algorithm.

\R Griessmair, Josef, and Werner Purgathofer. ``Deformation of Solids with
Trivariate B-Splines.'' \B Proceedings of Eurographics '89\}, W. Hansmann,
F. R. A. Hopgood and W. Strasser (eds.), p. 137-148, 545.

\A
Solid geometric models can be deformed to free-form solids by the use of
trivariate B-Splines. This paper describes the problems of implementing such
transformations for shaped rendering.

The surfaces are subdivided into triangles adaptively so that the error in
image space is limited. This adaptive triangulation ensures a smooth
appearance of the resulting pictures.

\R Woodward, Charles. ``Ray Tracing Parametric Surfaces by Subdivision in
Viewing Plane.'' \B Theory and Practice of Geometric Modeling\}, Wolfgang
Stra\ber and Hans-Peter Seidel (eds.), Springer-Verlag, 1989, p. 273-287.

\A
This paper presents a new approach for ray tracing parametric surfaces. Instead
of performing the computations in object space, the intersection search is more
efficiently done in the ray's orthogonal viewing coordinate system. Speeding up
ray tracing composite surfaces with adaptive space subdivision is also
discussed.

\R Lischinski, Daniel, and Jokob Gohczarowski. ``Improved Techniques for Ray
Tracing Parametric Surfaces.'' \B The Visual Computer\}, Vol. 6, 1990,
p. 134-152.

\A
Several techniques for acceleration of ray tracing parametric surfaces
are presented. Some of these are entirely new to ray tracing, while others
are improvements of previously known techniques. First a uniform spatial
subdivision scheme is adapted to parametric surfaces. A new space- and
time-efficient algorithm for finding ray-surface intersections is introduced.
It combines numerical and subdivision techniques, thus allowing utilization of
ray coherence and greatly reducing the average ray-surface intersection time.
Non-scan-line sampling orders of the image plane are proposed that facilitate
utilization of coherence. Finally, a method to handle reflected, refracted, and
shadow rays in a more efficient manner is described. Results of timing tests
indicating the efficiency of these techniques for various environments are
presented.

\R Nishita, Tomoyuki, Thomas W. Sederberg, and Masanori Kakimoto. ``Ray
Tracing Trimmed Rational Surface Patches.'' \B SIGGRAPH '90\}, p. 337-345.

This paper presents a new algorithm for computing the points at which a ray
intersects a rational B\'ezier surface patch, and also an algorithm for
determining if an intersection point lies within a region trimmed by piecewise
B\'ezier curves. Both algorithms are based on a recent innovation known as
B\'ezier clipping, described herein. The intersection algorithm is faster than
previous methods for which published performance data allow reliable
comparison. It robustly finds all intersections without requiring special
preprocessing.

\R Vlassopoulos, Vasilis. ``Adaptive Polygonization of Parametric Surfaces.''
\B The Visual Computer\}, Vol. 6, 1990, p. 291-298.

\A
This paper describes an algorithm for dividing a $(u,v)$-parametric surface
into the least possible number of plane triangular elements that closely follow
the surface they approximate. The concept of closeness defined here is based on
a set of three subdivision criteria: unit-normal criterion, chord-distance
criterion, and edge-refinement criterion.

The triangles generated by the subdivision, together with the unit normals at
their vertices, serve as input to the ray-tracing program, which generates a
shaded image of the surface with photogrphic realism.

\R Webber, Robert E. ``Ray Tracing Voxel Data Via Biquadratic Local Surface
Interpolation.'' \B The Visual Computer\}, Vol. 6, 1990, p. 8-15.

\A
Various shaded hidden-surface display techniques have been used to render voxel
data. In this paper, an approach to using general ray tracing for the rendering
of voxel data is presented. Central to this approach is the interpolation of a
surface with respect to its neighbors. Nine columns (of three voxel volumes
each) provide sufficient constraints on the integral of a biquadratic function
over the column's base to solve its specific coefficients. The use of these
locally interpolated surfaces to define a scene to be ray traced is
investigated.

\s Procedurally Defined Objects

\R Kajiya, James T. ``New Techniques for Ray Tracing Procedurally Defined
Objects.'' \B ACM TOG\}, Vol. 2, \#3, July 1983, p. 161-181. Also appears in
\B Tutorial: Computer Graphics: Image Synthesis\}, Kenneth I. Joy, Charles
W. Grant, Nelson L. Max, and Lansing Hatfield (eds.), Computer Society Press,
Washington, 1988, p. 168-188.

\A
We present new algorithms for efficient ray tracing of three procedurally
defined objects: fractal surfaces, prisms, and surfaces of revolution. The
fractal surface algorithm performs recursive subdivision adaptively.
Subsurfaces which cannot intersect a given ray are culled from further
consideration. The prism algorithm transforms the three-dimensional ray-surface
intersection problem into a two-dimensional ray-curve intersection problem,
which is solved by the method of strip trees. The surface-of-revolution
algorithm transforms the three-dimensional ray-surface intersection problem
into a two-dimensional curve-curve intersection problem, which again is solved
by strip trees.

\R Bouville, Christian. ``Bounding Ellipsoids for Ray-Fractal Intersection.''
\B SIGGRAPH '85\}, p. 45-52.

\A
Recently published papers have shown that, with appropriate intersection
algorithms, the rendering of many procedural objects is possible with all the
advantages offered by the ray-tracing techniques. In the case of stochastic
surfaces, the intersection can be computed by a recursive subdivision
technique. The efficiency of this algorithm depends essentially on the 
bounding volume whose size and shape are directly related to the stochastic
characteristics of these surfaces. After a brief review of the rendering of
stochastic surfaces and the bounding volume selection problem, two types of
bounding volumes are studies, describing how their intersection with a ray
can be computed and how their size can be derived from the stochastic
characteristics. The efficiency then, of these bounding volumes is compared.

\R Snyder, John M., and Alan H. Barr. ``Ray Tracing Complex Models Containing
Surface Tessellations.'' \B SIGGRAPH '87\}, p. 119-128.

\A
An approach to ray tracing complex models containing mathematically defined
surfaces is presented. Parametric and implicit surfaces, and boolean
combinations of these, are first tessellated into triangles. The resulting
triangles from many such surfaces are organized into a hierarchy of lists and
3D grids, allowing efficient calculation of ray/model intersections.

The technique has been used to ray trace models containing billions of
triangles and surfaces never before traced. The organizing scheme developed is
also independently useful for efficiently ray tracing any any complex model,
whether or not it contains surfaces tessellations.

\R Hart, John C., Daniel J. Sandin, and Louis H. Kauffman. ``Ray Tracing
Deterministic 3-D Factals.'' \B SIGGRAPH '89\}, p. 289-296.

\A
As shown in 1982, Julia sets of quadratic functions as well as many other
deterministic fractals exist in spaces of higher dimensionality than the
complex plane. Originally a boundary-tracking algorithm was used to view these
structures but required a large amount of storage space to operate. By ray
tracing these objects, the storage facilities of a graphics workstation frame
buffer are sufficient. A short discussion of a specific set of 3-D
deterministic fractals precedes a full description of a ray-tracing algorithm
applied to these objects. A comparision with the boundary-tracing method and
applications to other 3-D deterministic fractals are also included.

\R Hart, John C., and Thomas A. DeFanti. ``Efficient Antialiased Rendering of
3-D Linear Fractals.'' \B SIGGRAPH '91\}, p. 91-100.

\A
Object instancing is the efficient method of representing a hierachical object
with a directed graph instread of a tree. If this graph contains a cycle then
the object it represents is a linear fractal. Linear fractals are difficult to
render for three specific reasons: (1) ray-fractal intersection is not trivial,
(2) surface normals are undefined, and (3) the object aliases at all sampling
resolutions.

Ray-fractal intersections are efficiently approximated to sub-pixel accuracy
using procedural bounding volumes and a careful determination of the size of a
pixel, giving the perception that the surface is infinitely detailed.
Furthermore, a surface normal for these non-differentiable surfaces is defined
and analyzed. Finally, the concept of antialiasing ``covers'' is adapted and
used to solve the problem of sampling fractal surfaces.

An initial bounding volume estimation method is also described, allowing a
linear fractal to be rendered given only its iterated function system. A
parallel implementation of these methods is described and applications of these
results to the rendering of other fractal models are given.

\s Implicit Representations

\R Hanrahan, Pat. ``Ray Tracing Algebraic Surfaces.'' \B SIGGRAPH '83\},
p. 83-90.

\A
Many interesting surfaces can be written as polynomial functions of the spatial
coordinates, often of low degree. We present a method based on a ray casting
algorithm, extended to work in more than three dimensions, to produce pictures
of these surfaces. The method uses a symbolic algebra system to automatically
derive the equation of intersection between the ray and the surface and then
solves this equation using an exact polynomial root finding algorithm.

Included are illustrations of the cusp catastrophe surface, and two unusually
shaped quartic surfaces, Kummer's quadruple and Steiner's surface.

\R Sederberg, Thomas W., and David C. Anderson. ``Ray Tracing
of Steiner Patches.'' \B SIGGRAPH '84\}, p. 159-164.

\A
Steiner patches are triangular surface patches for which the Cartesian
coordinates of points on the patch are defined parametrically by quadratic
polynomial functions of two variables. It has recently been shown that it is
possible to express a Steiner patch in an implicit equation which is a degree
four polynomial in \$x, y, z\$. Furthermore,the parameters of a point known to
be on the surface can be computed as rational polynomial functions of \$x, y,
z\$. These findings lead to a straightforward algorithm for ray tracing Steiner
patches in which the ray intersection equation is a degree four polynomial in
the parameter of the ray. The algorithm presented represents a major
simplification over existing techniques for ray tracing free-form surface
patches.

\R Holmstr\"om, Lasse, Timo Laakko, Martti M\"antyl\"a, and Panu Rekola. ``Ray
Tracing Boundary Models with Implicit Blend Surfaces.'' \B Theory and Practice
of Geometric Modeling\}, Wolfgang Stra\ber and Hans-Peter Seidel (eds.),
Springer-Verlag, 1989, p. 253-271.

\A
We present a method for producing ray traced images of boundary representation
solid models where the faces of the solids are subsets of implicitly defined
algebraic surfaces. Specifically, we consider surfaces which are either natural
tori, or implicit blend surfaces. A point lying on such a surface is classified
as inside or outside a face on the surface either by parameterizing the face
(faces lying on natural quadrics or tori) and transforming the problem to the
parameter plane, or by using set theoretic (CSG) information associated with
the face (blend faces).

\R Kalra, Devendra, and Alan H. Barr. ``Guaranteed Ray Intersections with
Implicit Surfaces.'' \B SIGGRAPH '89\}, p. 297-306.

\A
In this paper, we present a robust and mathematically sound ray-intersection
algorithm for implicit surfaces. The algorithm is guaranteed to numerically
find the nearest intersection of the surface with a ray, and is guaranteed not
to miss fine features of the surface. It does not require fine tuning or human
choice of interactive parameters. Instead, it requires two upper bounds: ``L''
that limits the net rate of change of the implicit surface function \$f(x,y,z)\$
and ``G'' that limits the rate of change of the gradient. An implicit surface
with these rate limits is referred to as an ``LG-implicit surface.''

Existing schemes to intersect a ray with an implicit surface have typically
been guaranteed to work only for a limited set of implicit functions, such as
quadric surfaces or polynomials, or else have been ad-hoc and have not been
guaranteed to work. Our technique significanty extends the ability to
intersect rays with implicit surfaces in a guaranteed fashion.

\R Cychosz, Joseph M. ``Intersecting a Ray with an Elliptical Torus.'' Purdue
CADLAB Technical Report No. JC-07, Purdue University CADLAB, October 29, 1990.

\A
Presented in this paper is the mathematics and computations required for
determining the points of intersection between a ray and a torus. Also
presented is an efficient bounding method for tori.

\R Wyvill, Geoff, and Andrew Trotman. ``Ray-Tracing Soft Objects.'' \B
Proceedings of CG International '90\}, p. 467-476.

\A
Soft objects, also known as metaballs or implicit surfaces, are deformable
free-form shapes represented as a surface of constant value in a scalar field.

We present a simple, robust method for ray tracing soft objects defined by
polynomial field functions. The method is guaranteed to find all intersections
of a ray with a soft object. Thus it is suitable for use in CSG systems where
all intersections may be required.

\s Special Purpose Hardware

\R Pulleyblank, Ron, and John Kapenga. ``The Feasibility of a VLSI Chip for
Ray Tracing Bicubic Patches.'' \B IEEE CG\&A\}, March 1987, p. 33-44. Also
appears in \B Tutorial: Computer Graphics Hardware: Image Generation and
Display\}, Hassan K. Reghbati and Anson Y. C. Lee (eds.), Computer Society
Press, Washington, 1988, p. 328-339. Also appears as ``A VLSI Chip for Ray
Tracing Bicubic Patches'' in \B Advances in Computer Graphics Hardware I\},
W. Stra\ber (ed.), 1987, p. 125-140.

\A
In this article we explore the possibility of a VLSI chip for ray tracing
bicubic patches in B\'ezier form. The purpose of the chip is to calculate the
intersection point of a ray with the bicubic patch to a specified level of
accuracy, returning parameter values \$(u,v)\$ specifing the location of the
intersection on the patch, and a parameter value, \$t\$, which specifies the
location of the intersection on the ray. The intersection is calculated by
successively subdividing the patch and computing the intersection of the ray
with a bounding box of each subpatch until the bounding volume meets the
accuracy requirement. There are two operating modes: one in which only the
nearest intersection is found, and another in which all intersections are
found. This algorithm (and the chip) correctly handle the difficult cases of
the ray tangentially intersecting a planar patch and intersections of the ray
at a silhouette edge of the patch. Estimates indicate that such a chip could
be implemented with 2-micron NMOS (N-type metal oxide semiconductor) and could
compute patch-ray intersections at the rate of one every 15 microseconds for
patches that are prescaled and specified to a 12-bit fixed point for each of
the \$x, y\$, and \$z\$ components. A version capable of handling 24-bit patches
could compute patch-ray intersections at the rate of one every 140
microseconds. Calculations of the normal at the intersection point could be
performed with the addition of Re scalar subtractions and six scalar
multiplies. Images drawn using a software version of the algorithm are
presented and discussed.

\R Schneider, Bengt-Olaf. ``Ray Tracing Rational B-Spline Patches in VLSI.''
\B Advances in Computer Graphics Hardware II\}, A. A. M. Kuijk and
W. Stra\ber (eds.), 1988, p. 45-63.

\A
Rational B-spline surfaces make it possible to merge the concepts of freeform
surfaces described by rational polynomials especially conic sections. For ray
tracing it is crucial to determine the intersection between ray and object.
Therefore an algorithm is developed that is suitable for a VLSI
implementation. Some alternatives for the implementation of this algorithm are
presented and discussed. The paper concludes with a discussion of some
problems and possible further developments.
 
\R Bouatouch, Kadi, Yannick Saouter, and Jean Charles Candela. ``A VLSI Chip for
Ray Tracing Bicubic Patches.'' \B Proceedings of Eurographics '89\},
W. Hansmann, F. R. A. Hopgood and W. Strasser (eds.), p. 107-124.
 
\A
This paper deals with the integration of a VLSI chip dedicated to ray tracing
bicubic patches. A recursive subdivision algorithm is embedded in this chip.
The recursion stops when the termination conditions are met. A software
implementation allowed for the determination of key parameters which
influenced the choice of the proposed chip's architecture. Only some modules
of the chip are, at the present time, simulated and laid out, the rest is
being implemented. A detailed description of the chip's modules is given.

\s Natural Phenomena

\R Max, Nelson L. ``Vectorized Procedural Models for Natural Terrain: Waves
and Islands in the Sunset.'' \B SIGGRAPH '81\}, p. 317-324.

\A
A ray-tracing procedural model is described, in which ocean waves and islands
are rendered by different but related algorithms. The algorithms are based on
analytic formulas involving arithmetic operations, trigonometric functions, and
square roots, and are organized for a vectorizing compiler on a Cray 1, a
``supercomputer'' with a vector pipeline architecture. Height field methods are
used, one vertical scan line at a time, to trace the direct rays to the ocean,
where they are reflected. Approximate methods are then applied to find whether
the reflected rays meet any other objects on their way to the sky. The output,
at eight bits per pixel, gives information for shading, e.g.\ the angle of the
surface normal for rays meeting the islands, or the angle of elevation from the
horizon for rays continuing unobstructed to the sky.

The output is recorded on a magnetic tape for each frame in one cycle of the
wave motion, and plotted offline on a Dicomed D-48 color film recorder. The
eight bits per pixel are interpreted by a color translation table, which is
gradually changed as the wave cycle is repeated to simulate the changing
illumination during sunset.

\R Kajiya, James T., and Brian P. Von Herzen. ``Ray Tracing Volume Densities.''
\B SIGGRAPH '84\}, p. 165-174.

\A
This paper presents new algorithms to trace objects represented by densities
within a volume grid, e.g.\ clouds, fog, flames, dust, particle systems. We
develop light scattering equations, discuss previous methods of solution, and
present a new approximate solution to the full three-dimensional radiative
scattering problem which is suitable for use in computer graphics.
Additionally, we review dynamical models for clouds used to make an animated
movie.

\R Wyvill, Geoff, Andrew Pearce, and Brian Wyvill. ``The Representation of
Water.'' \B Proceedings of Graphics Interface '86/Vision Interface '86\},
p. 217-222.

\A
Water is the commonest of everyday substances and its many forms have provided
subjects for artists for as long as art has existed. But in computer graphics,
there seem to have been few attempts to make pictures of water. The reason for
this is simple. Realistic pictures of water are very hard to produce. Some of
the reasons for this difficulty are examined and some experiments are
reported.

\R Kirk, David B. ``The Simulation of Natural Features Using Cone
Tracing.'' \B The Visual Computer\}, Vol. 3, 1987, p. 63-71. Revision of
same paper in \B Advanced Computer Graphics, Proceedings of Computer Graphics
Tokyo '86\}, Tosiyasu L. Kunii (ed.), Springer-Verlag, p. 129-144.

\A
The method of ray tracing with cones is used to area sample objects for
properly filtered rendering. Methods for generating antialiased reflections
and refractions distorted by normal vector perturbation (bump-mapping) are
developed to simulate the appearance of rippled water surfaces. The sampling
aperture of the cones is distorted to antialias the reflections and
refractions properly. A calculated texture function is used as a diffusion map
for transparent surfaces to simulate the visual effect of diffuse,
soft-shadowed cloud layers.

\R Inakage, Masa. ``An Illumination Model for Atmospheric Environments.'' \B
New Advances in Computer Graphics, Proceedings of CG International '89\},
R. A. Earnshaw and B. Wyvill (eds.), p. 533-548.

\A
Current three dimensional computer graphics assumes a vacuum space. The
inclusion of atmosphere is essential for the modeling and rendering of natural
phenomena. This paper presents an illumination model in the presence of
atmosphere. The model is built within a framework called the atmospheric
cube. The atmospheric cube, or the A-cube, is a finite volume that encloses
the three dimensional scene to be modeled. The atmosphere is defined by
particles of varying radii that are distributed over the cube. The distribution
of particles determines the density of atmosphere. The interaction of light
with the atmosphere is divided into four cases to capture the characteristics
of the atmospheric illumination by particles of different radii: absorption,
Rayleigh scattering, Mie scattering, and geometric optics. The atmospheric
equation is a combination of modeling techniques which cover the four cases. To
render the interaction of light with the atmosphere, discrete points in the
A-cube are volume sampled. Examples of blue sky, sunset, hazy sky, shaft of
light beam, and rainbow are given.
 
\R Musgrave, F. Kenton, Craig E. Kolb, and Robert S. Mace. ``The Synthesis
and Rendering of Eroded Fractal Terrains.'' \B SIGGRAPH '89\}, p. 41-50.
 
\A
In standard fractal terrain models based on fractional Brownian motion the
statistical character of the surface is, by design, the same everywhere. A new
approach to the synthesis of fractal terrain height fields is presented which,
in contrast to previous techniques, features locally independent control of
the frequencies composing the surface, and thus local control of fractal
dimension and other statistical characteristics. The new technique, termed
\E noise synthesis\}, is intermediate in difficulty of implementation, between
simple stochastic subdivision and Fourier filtering or generalized stochastic
subdivision, and does not suffer the drawbacks of creases or periodicity.
Varying the local crossover scale of fractal character or the fractal
dimension with altitude or other functions yields more realistic first
approximations to eroded landscapes. A simple physical erosion model is then
suggested which simulates hydraulic and thermal erosion processes to create
global stream/valley networks and talus slopes. Finally, an efficient ray
tracing algorithm for general height fields, of which most fractal terrains
are a subset, is presented.

\R Perlin, Ken, and Eric M. Hoffert. ``Hypertexture.'' \B SIGGRAPH '89\},
p. 253-262.

\A
We model phenomena intermediate between shape and texture by using
space-filling applicative functions to modulate density. The model is
essentially an extension of procedural solid texture synthesis, but evaluated
throughout a volumetric region instead of only at surfaces.

We have been able to obtain visually realistic representations of such
shape+texture (\E hypertexture\}) phenomena as hair, fur, fire, glass, fluid
flow and erosion effects. We show how this is done, first by describing a set
of base level functions to provide basic texture and control capabilities, then
by combining these to synthesize various phenomena.

Hypertexture exists within an intermediate region between object and
non-object. We introduce a notion of \E generalized boolean shape operators\}
to combine shpaes having such a region.

Rendering is accomplished by \E ray marching\} from the eye point through the
volume to accumulate opacity along each ray. We have implemented our
hypertexture rendering algorithms on a traditional serial computer, a
distributed network of computers and a coarse-grain MIMD computer. Extensions
to the rendering technique incorporating refraction and reflection effects are
discussed.

\R Berger, Marc, Terry Trout, and Nancy Levit. ``Ray Tracing Mirages.''
\B IEEE CG\&A\}, May 1990, p. 36-41.

\A
Ray tracing has been used extensively to produce realistic images. Traditional
algorithms simulate various optical phenomena, including reflections,
refractions, and shadows. With all of these the direction of the ray changes
only when it intersects an object. Atmospheric variations, however, can cause
light rays to bend, thereby changing their direction at any time. Mirages are
just one possible visual effect of these bent rays. We generate mirages by
sending rays through an object with multiple air layers having different
refractive indices. As a ray enters this virtual object, it strikes several
air layers and causes repeated bending of the ray, which results in the mirage
effect.

\R Musgrave, F. Kenton. ``A Note on Ray Tracing Mirages.'' \B IEEE CG\&A\},
November 1990, p. 10-12.

[No abstract. This note describes a problem in the paper by Berger \E et
al\}.\ and points out a correction in handling total internal reflection.]
 
\R Watt, Mark. ``Light-Water Interaction Using Backward Beam Tracing.''
\B SIGGRAPH '90\}, p. 377-385.
 
\A
A new two pass approach is presented based on a variation of backward ray
tracing - backward beam tracing. Advantages include its capability of
rendering complex, hitherto unattainable, specular to diffuse phenomenon and
its easy insertion into standard renderers. The algorithm is applied to
aspects of the interaction of light with water. Within this context a variety
of first generation effects, including shadowing and light scattering, are
both rendered and animated. Results taken from the treatment of caustics
within classical optics are included as they provide valuable insights into
the precise nature of specular to diffuse transfer.

\R Dias, Maria Lurdes. ``Ray Tracing Interference Color.'' \B IEEE CG\&A\},
March 1991, p. 54-60.

\A
[No abstract. Taken from Introduction]

The interaction of light with thin films causes some of the most beautiful
color effects in nature. The multiple reflections of light between two surfaces
of a thin film of transparent material produce a color effect called
interference color. The lovely colors of a soap bubble, oil on water or on a
wet road, thin glass bulbs, cracks in a piece of glass, butterfly and
dragonfly wings, mother of pearl, and peacock's tails offer examples of this
phenomenon in nature.

Because interference color is produced in transparent materials and is view
dependent, ray tracing seems like the best approach to simulate it. I set out
to recreate this phenomenon with a ray-tracing model that takes into account
any kind of film layer in any medium. My method is a generalization of
well-known reflectance models, such as the Cook-Torrance, and Hall and
Greenberg models.

\s Other Phenomena

\R Cook, Robert L., Thomas Porter, and Loren Carpenter. ``Distributed Ray
Tracing.'' \B SIGGRAPH '84\}, p. 137-145.

\A
Ray tracing is one of the most elegant techniques in computer graphics. Many
phenomena that are difficult or impossible with other techniques are simple
with ray tracing, including shadows, reflections, and refracted light. Ray
directions, however, have been determined precisely, and this has limited the
capabilities of ray tracing. By distributing the directions of the rays
according to the analytic function they sample, ray tracing can incorporate
fuzzy phenomena. This provides correct and easy solutions to some previously
unsolved or partially solved problems, including motion blur, depth of field,
penumbras, translucency, and fuzzy reflections. Motion blur and depth of field
calculations can be integrated with the visible surface calculations, avoiding
the problems found in previous methods.

\R Inakage, Masa. ``Caustics and Specular Reflection Models for Spherical
Objects and Lenses.'' \B The Visual Computer\}, Vol. 2, 1986, p. 379-383.

\A
Ray tracing is a most powerful and elegant rendering technique and is able
to render shadows, reflections, and refractions very nicely. However,
reflections and refractions in ray tracing simulate the reflected and refracted
``eye'' ray and not the ``light'' ray. Standard ray tracing techniques
therefore suffer from a lack of specular interreflection and caustics. This
paper proposes an algorithm to render reflected and refracted ``light'' rays
for spherical objects and lenses. Indirect illumination is a result of the
reflection of light rays. Reflected light may be considered an additional light
source; if it is included in the intensity calculation, indirect illumination
can be rendered. The refracted light is noticeable as a focal point for a
convex lens. The dispersed light has low intensity which may be insignificant
for the illumination calculations. In the case of a convex lens, light rays
become extremely directional and light energy increases. The result appears as
caustics. The proposed algorithm is limited to a collimated light ray and does
not account for the case of dispersed light.

\R Thomas, Spencer W. ``Dispersive Refraction in Ray Tracing.''
\B The Visual Computer\}, Vol. 2, 1986, p. 3-8.

\A
Dispersive refraction is the property that gives gemstones their fire, and
that makes prisms produce a spectrum from white light. Modeling dispersion is
a ray tracing environment requires solution of some new problems, but allows
production of more exciting images. The mechanism of dispersive refraction is
discussed, and its implementation is described. Pictures of a prism and of
several diamonds are included. Images generated by this technique are
realistic, but are computationally expensive.

\R Yokoi, Shigeki, Kosuke Kurashige, and Jun-ichiro Toriwaki. ``Rendering Gems
with Asterism or Chatoyancy.'' \B The Visual Computer\}, Vol. 2, 1986,
p. 307-312.

\A
In this paper we describe an algorithm to render the asterism and chatoyancy
effect in gems. This effect is due to light dispersion caused by inclusions
consisting of vast numbers of thin fibrous needles. We develop models for
distribution of the microfacet directions of the inclusions and of the light
dispersion by them. Based on these models, we derive an algorithms to render
gems with the asterism effect. By introducing a ray distribution map, a new
algorithm for tracing dispersed light rays is developed.

\R Heckbert, Paul S. ``Ray Tracing Jell-O Brand Gelatin.'' \B CACM\}, Vol.
31, \#2, February 1988, p. 130-134. Revision of same paper in \B SIGGRAPH
'87\}, p. 73-74.

\A
[No abstract. Introduction]

Ray tracing has established itself in recent years as the most general
image-synthesis algorithm. Researchers have investigated ray-surface
intersection calculations for a number of surface primitives. These have
included checkboards [Whitted 80], chrome balls [Whitted 80], glass balls
[Whitted 80], robot arms [Barr 82], blue abstract things [Hanrahan 82],
more glass balls [Watterberg 83], mandrills [Watterberg 83], more mandrills
[Sweeney 83], green fractal hills [Kajiya 83], more glass balls [SEDIC 83],
aquatic blobby things [Kaw 83], more chrome balls [Heckbert 83], pool balls
[Porter 84], and more glass balls [Kajiya 86].

Unfortunately, \E nobody\} has ray traced any food. So far, the most realistic
foods were Blinn's classic orange and strawberry images, but these were created
with a scan-line algorithm. The \E Dessert Realism Project\} at Pixar is
addressing this problem. This article presents new technology for ray tracing
a restricted class of dessert foods, in particular Jell-O-brand gelatin. We
believe this method may have application to other brands of gelatin and,
perhaps, pudding as well.

This article is divided into three parts: methods for modeling static Jell-O,
simulation of Jell-O motion using impressive mathematics, and ray-Jell-O
intersection calculations.

\R Iizuka, Masa. ``Ray-Traced View and Visual Transparent Quality of Double
Transparent Objects.'' \B New Trends in Computer Graphics, Proceedings of CG
International '88\}, Nadia Magnenat-Thalmann and Daniel Thalmann (eds.),
Springer-Verlag, p. 189-198.

\A
A constructive solid geometry for simulation models is composed of fundamental
primitives in a ray tracing algorithm. Only a ray of light from two components
of specular reflection and refraction is simply traced backwards according to
the value of depth level and threshold of energy attenuation. Ray traced images
of a main transparent object enclosed with another transparent object are
displayed on a color CRT. Complex color rendering view of double transparent
objects is discussed from a viewpoint of the color shift and visual transparent
quality of computer-generated images.

\R Inakage, Masa. ``Particals: An Artistic Approach to Fuzzy Objects.'' \B New
Trends in Computer Graphics, Proceedings of CG International '88\}, Nadia
Magnenat-Thalmann and Daniel Thalmann (eds.), Springer-Verlag, p. 126-134.

\A
An artistic approach for modeling fuzzy objects called Particals is presented.
The method unifies the modeling and rendering process. Particals treat fuzzy
objects as a cluster of miniscule particles. The distribution of particles is
defined by a stochastic function. Particles are generated during the rendering
process by referencing the stochastic function. Ray tracing is used for
rendering so that intersection, reflection, refraction, and shadow calculations
can be incorporated. The algorithm is efficient and it produces impressionistic
images with very intricated textures. However, it suffers from the stobing
effect in animation sequences because the method does not maintain frame to
frame coherence. The particles appear to be equal in size because the size is
fixed to the size of the pixel on the image screen.

\R Musgrave, F. Kenton, Lewis Hitchner, James Murphy. ``A Realistic Model of
Refraction for Computer Graphics.'' \B Proceedings of Modelling and Simulation
on Microcomputers\}, 1988, p. 37-43.

\A
A model which takes into account the relationsip of the frequency of light
to the index of refraction in transparent media, is developed as an extension
of the distributed ray tracing model. A model of atmospheric rainbows is
presented. The problem of representing an approximation of the spectrum of
monchromatic colors on a color graphics monitor is discussed, within the
context of modelling dispersion.
 
\R Musgrave, F. Kenton. ``Grid Tracing: Fast Ray Tracing for Height Fields.''
Research Report YALEU-DCS-RR-639, Yale University, July 1988.
 
A fast algorithm for ray tracing height fields is presented. The algorithm
employs a modified Bresenham DDA to traverse a two dimensional array of height
values. At each cell the altitude of the ray is compared with the heights of
the four corners of the cell; ray/object intersections need only be calculated
when the altitude of the ray is in the range of those heights. The average
number of ray/object intersections performed is about two per ray; the two
objects tested for intersection are located in \$O(\qN-1\})\$ time where \$N\$
is the number of height values in the field.

\R Yokoi, Shigeki, and Jun-ichiro Toriwaki. ``Realistic Expressions
of Solids with Feeling of Material.'' \B Computer Science \& Technologies:
Japan Annual Reviews in Electronics, Computers \& Telecommunications\}, Vol. 18,
1988, p. 273-288.

\A
This article presents a survey of research in Japan on shading techniques,
which are important for producing realistic images of 3D objects with material
feelings. The major contributions of Japanese researchers to this problem are
as follows:

(1) Anisotropic reflectance model: All the former models assumed that the
intensity of reflected light is distributed isotropically around the specular
direction. Two groups developed anisotropic reflectance models.

(2) Improved ray tracing algorithm: The ray tracing algorithm developed by
T. Whitted is a powerful tool for rendering transparent objects, but it
sometimes produces unnatural images. We improve this algorithm by employing
variable reflection and transmittance coefficients based on the Fresnel
reflection law. We also attempted to render jewels by applying this model.

\R Yuan, Ying, Tosiyasu L. Kunii, Naota Inamoto, and Lining Sun.
``GemstoneFire: Adaptive Dispersive Ray Tracing of Polyhedrons.'' \B The
Visual Computer\}, Vol. 4, 1988, p. 259-270.

\A
Synthesizing realistic images of gemstones requires techniques beyond the scope
of normal ray tracing. The `fire' of such highly refractive objects is what
makes gemstones attractive, and also imposes very high computational overhead
to perform time consuming dispersive ray tracing. Gemstones are usually cut in
polyhedrons as for example, a brilliant cut. After detailed analysis of the
nature of dispersive ray tracing of polyhedral objects, a new method of using
three simple rays adaptively is proposed to model the ray spreading caused by
dispersive refraction. It is shown that the proposed method reduces the
computational complexity to an order close to that of normal ray tracing.

\R Musgrave, F. Kenton. ``Prisms and Rainbows: a Dispersion Model for Computer
Graphics.'' \B Proceedings of Graphics Interface '89 - Vision Interface '89\},
p. 227-234.

\A
\E Dispersion\} is the spreading of refracted light into its component colors
or spectrum. A model of refraction including dispersion is developed using the
techniques of distributed ray tracing. Two models of the rainbow, one empirical
or impressionistic, the other purely physical, are developed using the results
of the dispersion model. The problem of representing the spectrum of
monochromatic colors using the rgb primaries of the graphics color monitor is
addressed.

\R Takagi, Atsushi, Hitoshi Takaoko, Tetsuya Oshima, and Yoshinori
Ogata. ``Accurate Rendering Techique Based on Colorimetric Conception.'' \B
SIGGRAPH '90\}, p. 263-272.

\A
We have developed a rendering technique to generate realistic images meeting
designers' requirements by strictly analyzing various physical phenomena
relevant to the appearance of actual objects.

We have numerically compared the results of the calculations using this
technique with colorimetry values. As a result, both values were virtually
equal, so we have been able to confirm the effectiveness of the established
technique.

Applications of this technique to car design, which has not been realized
to a large extent because of severe requests for realism, will make it possible
to evaluate styles and colors on a graphics display before making a clay model.

\R Muraki, Shigeru. ``Volumetric Shape Description of Range Data Using `Blobby
Model'.'' \B SIGGRAPH '91\}, p. 227-235.

\A
Recently in the field of computer vision, there have been many attempts to
obtain a symbolic shape description of an object by fitting simple primitives
to the range data of the object. In this paper, we introduce the \E ``Blobby
Model''\} for automatically generating a shape description from range data.
This model can express a 3D surface as an isosurface of a scalar field which
is produced by a number of field generating primitives. The fields from many
primitives are blended with each other and can form a very complicated shape.
To determine the number and distribution of primitives required to adequately
represent a complex 3D surface, an energy function is minimized which measures
the shape difference between the range data and the \E ``Blobby Model''\}. We
start with a single primitive and introduce more primitives by splitting each
primitive into two further primitives so as to reduce the energy value. In this
manner, the shape of the 3D object is slowly recovered as the isosurface
produced by many primitives. We have successfully applied this method to human
face range data and typical results are shown. The method herein does not
require any prior range segmentation.

\s Volume Data

\R Garrity, Michael P. "Raytracing Irregular Volume Data." \B Proceedings of
the San Diego Workshop on Volume Visualization\}, 1990, p. 35-40, 110.

An efficient technique is described for rendering volume data which is not
organized as a regular, three-dimensional grid. The algorithm works on
collections of convex cells with shared faces. Datasets of this form are quite
common in such applications as Computation Fluid Dynamics (CFD) and Finite
Element Modeling (FEM)..

\R Levoy, Marc. ``A Hybrid Ray Tracer for Rendering Polygon and Volume
Data.'' \B IEEE CG\&A\}, March 1990, p. 33-40.

\A
Volume rendering is a technique for visualizing sampled functions of three
spatial dimensions by comuting 2D projections of a colored semitransparent
volume. In this article I address the problem of extending volume rendering to
handle polygonally defined objects. The solution I propose is a hybrid
ray-tracing algorithm. Rays are simultaneously cast through a set of polygons
and a volume data array. Samples of each are drawn at equally spaced intervals
along the rays, and the resulting colors and opacities are composited together
in depth-sorted order. To avoid aliasing of polygonal edges at modest
computational expense, I use a form of selective supersampling. To avoid errors
in visibility at polygon-volume intersections, I give special treatment to
volume samples lying immediately in front of and behind polygons. I will
evaluate the cost, image quality, and versatility of the algorithm using data
from 3D medical imaging applications.

\R Levoy, Marc. ``Volume Rendering by Adaptive Refinement.''
\B The Visual Computer\}, Vol. 6, 1990, p. 2-7.

\A
\E Volume rendering\} is a technique for visualizing sampled scalar functions
of three spatial dimensions by computing 2D projections of a colored
semi-transparent gel. This paper presents a volume-rendering algorithm, in which
imge quality is adaptively refined over time. An initial image is generated by
casting a small number of rays into the data, less than one ray per pixel, and
interpolating between the resulting colors. Subsequent images are generated by
alternately casting more rays and interpolating. The usefulness of these rays
is maximized by distributing them according to measures of loal image
complexity. Examples from two applications are given: molecular graphics and
medical imaging.

\R Levoy, Marc. ``Efficient Ray Tracing of Volume Data.''
\B ACM TOG\}, Vol. 9, \# 3, July 1990, p. 245-261.

\A
\E Volume Rendering\} is a technique for visualizing sampled scalar or vector
fields of three spatial dimensions without fitting geometric primitives to the
data. A subset of these techniques generates images by computing 2-D
projections of a colored semitransparent volume, where the color and opacity
at each point are derived from the data using local operators. Since all
voxels participate in the generation of each image, rendering time grows
linearly with the size of the dataset. This paper presents a front-to-back
image-order volume-rendering algorithm and discusses two techniques for
improving its performance. The first technique employs a pyramid of binary
volumes to encode spatial coherence present in the data, and the second
technique uses an opacity threshold to adaptively terminate ray tracing.
Although the actual time saved depends on the data, speedups of an order of
magnitude have been observed for datasets of useful size and complexity.
Examples from two applications are given: medical imaging and molecular
graphics.

\R Montani, C., and R. Scopigno. "Rendering Volumetric Data Using the STICKS
Representation Scheme." \B Proceedings of the San Diego Workshop on Volume
Visualization\}, 1990, p. 87-93, 112.

\A
An increasing need to efficiently represent and render 3D volumetric data is
being experienced in many application fields ranging from scientific and
medical visualization to CAD. A technique of representing this kind of data,
the Sticks representation scheme, is proposed here with the aim of allowing an
efficient representation and rendering of voxel data on low-capability
workstations. This data model is based on a 3D extension of the well-known
run-length encoding methods. It requires \$O(kn\^2\})\$ memory cells to
represent \$O(n\^3\})\$ volumetric data and produces a degree of data
compression greater than that of the octree model. Rendering a frontal
orthographic projection of a Sticks-represented volume is a very simple task
and requires only a partial scan of the data. A ray tracing algorithm is
presented for the synthesis of gradient-shaded parallel projections; the
proposed algorithm exploits the data compression to drastically reduce the
complexity of rendering.

\R Novins, Kevin L., Francois X. Sillion, and Donald P. Greenberg. "An Efficient
Method for Volume Rendering Using Perspective Projection." \B Proceedings of
the San Diego Workshop on Volume Visualization\}, 1990, p. 95-102.

\A
Use of the perspective projection adds important perceptual cues for image
comprehension. However, it has not been widely used in volume rendering because
of the lack of efficient computational algorithms and concern over the
nonuniform sampling rate imposed by perspective ray divergence. This paper
introduces two new techniques to help make perspective projection more feasible
in rendering volume data. First, a method is presented for efficient
slice-by-slice processing of volume data, allowing high resolution data sets by
eliminating typical memory constraints. Second, an adaptive ``ray splitting''
approach is described which ensures that the entire volume is sampled within
user-specified limits. Additionally, we present results using distributed ray
tracing to achieve depth of field effects.

\S Applications

\s Acousistics

\R Stettner, Adam, and Donald Greenberg. ``Computer Graphics Visualization
for Acoustic Simulation'' \B SIGGRAPH '89\}, p. 195-206.

\A
Computer simulations can be used to generate the spatial and temporal data
describing the acoustical behavior of performance halls, but typically the
analytical results are difficult to assimilate and compare. By using computer
graphics to display the multi-dimensional data, substantially greater amounts
of information than that conveyed by standard techniques can be communicated to
the designer. This allows designs of different acoustical spaces to be tested,
evaluated, and compared.

An example comparing the acoustical behavior of three different concert halls
demonstrates these techniques and allows for the simultaneous assimilation of
much of the information necessary to evaluate the acoustical nature of a space.
The use of three-dimensional images, color, animation and abstract
representation allows for the comprehension of the complex results of a
scientific simulation. Specifically, the simultaneous display of particular
icons familiar to the discipline enabled the simultaneous presentation of up to
twelve parameters.

From a more general point of view, the procedures demonstrate how computer
graphics can be utilized for the portrayal of multi-dimensional time dependent
data. The visualization techniques are potentially useful for the display of
three-dimensional vector fields in many scientific and design applications.

\s Lighting Design

\R Lang, Laura. ``Lighting Design.'' \B Computer Graphics World\}, October
1988, p. 109-114.

\A
[No abstract. This is not a technical paper. It describes how ray tracing and
radiosity are used to aid in the task of lighting design.]

\s Medical Imaging

\R Trousset, Yves, and Francis Schmitt. ``Active-Ray Tracing for 3D Medical
Imaging.'' \B Proceedings of Eurographics '87\}, Guy Mar\'echal (ed.),
p. 139-150.

\A
Large quantities of three-dimensional (3D) information are produced by 3D
medical imaging techniques such as CT and MRI, in the form of digital volumes
(DV). We propose a new approach to help a human observer to visualize these
volumes. This approach is based on the idea that, in order to achieve true
user-interaction, segmentation and visualization should not be treated
separately. This is achieved by introducing active ray tracing, a method
inspired by ray tracing but working directly on unsegmented digital volumes.
Segmentation takes place as the active rays penetrate through the volume.

\s Molecular Modeling

\R Palmer, Thomas C, Frederick H. Hausheer, and Jeffrey D. Saxe.
``Applications of Ray Tracing in Molecular Graphics.'' \B Journal of
Molecular Graphics\}, Vol. 7, September 1989, p. 157, 160-164.

\A
Ray tracing is an elegant and powerful technique for creating computer
generated images. The wide variety of geometric primitives and realistic
effects such as reflections, transparency, and shadows make it one of the most
popular rendering methods in use today. We present a brief introduction to ray
tracing and discuss some of the computational issues involved. Examples are
given showing ray tracing to be an effective technique for producing high
quality visualizations of molecular structures.

\s Relativity

\R Hsiung, Ping-Kang, and Robert H. P. Dunn. ``Visualizing Relativistic
Effects in Spacetime.'' \B Proceedings of Supercomputing '89 Conference\},
p. 597-606.

\A
We have developed an innovative ray-tracing algorithm to describe
\E R\}elativistic \E E\}ffects in \E S\}pace\E T\}ime (``REST''). Our
algorithm, called \E REST-frame\}, simulates the generalized world in
spacetime and gives the fine details implicit in the Special Theory of
Relativity that have not yet been made apparent. These novel simulations
disclose the non-intuitive realm of Special Relativity and, by visualization
means, advance beyond the findings of past revelations concerning relativistic
effects.

Through application of state-of-the-art computation technology and simulation
techniques to earlier quests in physics, REST-frame offers a flexible
visualization tool to study some of the most exciting aspects of the natural
world; particularly, the rich visual properties associated with the finite
speed of light.

\R Hsiung, Ping-Kang, Robert H. Thibadeau, Christopher B. Cox, and Robert H. P.
Dunn. ``Doppler Color Shift in Relativistic Image Synthesis.'' \B Proceedings
of an International Conference organized by IPSJ to Commemorate the 30th
Anniversary\}, 1990, p. 369-377.

\A
We have developed an algorithm to visualize the 4-dimensional spacetime model
of the universe. The algorithm, called \E REST-frame\}, builds on conventional
graphical technique of ray-tracing, but encompasses finite light-speed and
special relativity physics. As such, it simulates the relativistic effects of
length contraction, time dilation and optical distortion due to light transit
time differences.

In this paper, we report our extentions of REST-frame to include the Doppler
color shift. Objects in motion are shown to undergo shape distortion as well as
color change--blue shift for approaching objects and red shift for receding
objects. Simultaneous blue and red shifts also occur, and a second order effect
due to inter-reflection among objects in relative motion is evident.

Our exploration reveals the surprising visual properties and complexities of
the Doppler color shift, which exist in relation with other manifestations of
special relativity. From the interplay of the photonic imag\E ing\} process and
the imag\E ed\} physical events in producing the final images, there elicits
the rich details of physical reality which the mathematical language of the
Special Theory does not directly provide.

\R Hsiung, Ping-Kang, Robert H. Thibadeau, and Robert H. P. Dunn.
``Ray-Tracing Relativity.'' \B Pixel\}, January/February 1990, p. 10-18.

\A
[No abstract. Introduction]

What would the world look like if you were traveling at 99 percent of the
speed of light? The physical principles and mathematical methods needed to
answer this question have been understood for the better part of a century,
ever since Einstein formulated the special theory of relativity in 1905. Only
recently, however, has it become possible to create realistic images of a
world seen at relativistic speeds. Some of these images reveal effects that
defy intuition and that would have been very difficult to predict without the
techniques of computer visualization.

At Carnegie Mellon University, we have been investigating the appearance of the
relativistic world with the aid of an algorithm called REST-frame (``REST''
is an acronym for ``relativistic effects in spacetime.'') The algorithm relies
on the long-established technique of ray-tracing to simulate a scene, but
there is one crucial addition to the ray-tracing procedure: We take into
account the finite speed of light and keep track of time of as a ray's path is
traced through space. From this one change the diverse effects of special
relativity follow automatically.

\R Hsiung, Ping-Kang, and Robert H. Thibadeau. ``Spacetime Visualization of
Relativistic Effects.'' \B Proceedings of the 1990 ACM Eighteenth Annual
Computer Science Conference\}, 1990, p. 236-243.

\A
We have developed an innovative ray-tracing algorithm to describe
\E R\}elativistic \E E\}ffects in \E S\}pace\E T\}ime (``REST''). Our
algorithm, called \E REST-frame\}, models light rays that have assumed
infinite speed in conventional ray-tracing to have a \E finite\} speed \$c\$
in spacetime, and uses general Lorentz Transformation, which connects the
spacetime description of a single event in two inertial coordinate systems
(\E frames\}) that differ by a constant velocity, to prform the relativistic
translation and aberration of light rays.

In this paper, we report the extension of our previous work for visualizing
relativistic motion in spacetime to include relativistic Doppler color shift
and the simulation of complx kinematic systems in which objects of different
relavistic velocities coexist. Our simulations have produced non-intuitive
images showing anisotropic deformation (\E warping\}) of space and intensity
concentration/spreading of light sources in spacetime. Images of objects
undergoing relativistic Doppler shift are also generated

By applying state-of-the-art computation technology and simulation techniques
to the earlier quests in Physics that were conducted mainly by \E thought
experiment\}, we demonstrate, through our new revelations, that \E REST-frame\}
offers a powerful \E experimentation tool\} to study and explore some of the
most exciting aspects of the natural world; particularly, the rich physical
properties associated with the finite speed of light.

\R Hsiung, Ping-Kang, Robert H. Thibadeau, and Michael Wu. ``T-Buffer: Fast
Visualization of Relativistic Effects in Spacetime.'' \B Proceedings of the
1990 Symposium on Interactive 3D Graphics\}, p. 83-88, 263.

\A
[Not much about ray tracing, but compares results to previous paper.]

We have developed an innovative ray-tracing simulation algorithm to describe
\E R\}elativistic \E E\}ffects in \E S\}pace\E T\}ime (``REST''). Our
algorithm, called \E REST-frame\}, models light rays that have assumed
infinite speed in conventional ray-tracing to have a \E finite\} speed in
spacetimme, and uses the non-Newtonian Lorentz Transformation to relate
measurements of a single event of a single event in different inertial
coordinate systems (\E inertial frames\}). Our earlier work explored the power
of \E REST-frame\} as an \E experimentation tool\} to study the rich visual
properties in natural world modeled by Special Relativity. Non-intuitive
images of the anisotropic deformation (``warping'') of spce, the intensity
concentration/spreading of light sources in spacetime, and the relativistic
Doppler shift were visualized from the simulations.

\E REST-frame\} simulations are computationally expensive. Several hours of
CPU time may be needed to generate one intricate image on a relatively
powerful DECStation 3100. This high simulation cost of \E REST-frame\}
precludes its application in interactive, real-time graphics environments.

In this paper, we report a scanline based \E REST-frame\} rendering method
that provides a faster alternative to the original ray-tracing based
\E REST-frame\} implementation. This new method operates in the spirit of the
classical Z-buffer in computer graphics and the inter-inertial frames
point-mapping method investigated in physics in the early 1960's, and
determines the visibility of points in spacetime by their spatial \E and\}
temporal visibility. Specifically, all spacetime event points that are \E 
potentially\} visible from the viewpoint at the imaging time are geometrically
projected in three dimensional (3D) space to the image plane pixel buffer.
Multiple points with a same pixel affiliation are sorted by their \E time
distance\} from the imaging time, and the most recent spacetime points is
displayed.

This method, which we call \E ``Time-Buffer'' or ``T-Buffer''\}, offers a
significant speed improvement over the original \E REST-frame\} in software,
and permits a dedicated Z-buffer-type hardware implementation that promises
interactive, real-time relativistic effects in simulations on a contemporary
graphic workstation.

Motion blur in real world images caused by the noRfinitesimal exposure time
of image-taking can be simulated by \E ``Stochastic T-Buffer''\}, which
perturbs the \E time component\} of the scan-converted spacetime events that
are potentially visible. The classical A-Buffer technique that models
translucency also can be adapted easily in T-Buffer. The limitation of
T-Buffer is its inability to model specular reflection and refraction in
optics, which our original \E REST-frame\} implementation simulates
completely.

\R Hsiung, Ping-Kang, Robert H. Thibadeau, Christopher B. Cox, and Robert H. P.
Dunn. ``Time Dilation Visualization in Relativity.'' \B Supercomputing '90\},
p. 835-844.

\A
This work extends our previous effort in visualizing the spatial aspect of
relativistic effects, and treats the phenomenon of time dilation; an inherent
temporal effect of special relativity.

Here, we demonstrate through still-frame images and live animations that in
\E observing\} the viewing independent time dilation, the finite light transit
time involved in performing the observation makes the \E observed\} time
dilation also depend on the viewing condition.

As we introduce the physics of special relativity into ray-tracing and make
time to pass as a ray travels through space, we are able to link the spatial
and temporal dimensions in a fundamental and consistent way in our simulations,
and generate images that reveal the spatial \E and\} temporal properties of the
4D geometry of \E spacetime\}.

Our exploration highlights the interplay of the imag\E ing\} process and the
imag\E ed\} physical events in producing the final images. It reveals a richly
detailed physical reality which the mathematical language of \E thought
experiment\} in relativity does not directly provide.

\R Hsiung, Ping-Kang, Robert H. Thibadeau, Christopher B. Cox, Robert H. P.
Dunn, Michael Wu, and Paul Andrew Olbrich. ``Wide-band Relativistic Doppler
Effect Visualization.'' \B Visualization '90\}, p. 83-92.

One of the most visible aspects of special relativity is the relativistic
Doppler effect--the dependence of observed radiation wavelengths upon the
velocity of the source and the viewing conditions.

In this paper, we present a flexible and efficient method to simulate the
Doppler shift. This new method has the following features:

- Surface properties and light composition are represented by splines as
functions of wavelength. The entire electromagnetic (EM) spectrum can therefore
be represented efficiently.

- Doppler shift and shading operations are performed through the manipulation
of spline coefficients. The \E evaluation\} of the spline functions is carried
out at the end of each shading loop to generate the display R, G, B values.

This method simplifies the management of the shift and reduces the calculations
necessary to maintain a spectral description of lights and surfaces.

The study of astrophysical phenomena, which are being color-shifted by
individual recession velocity and by the expansion of the universe, requires
the use of knowledge about the Doppler effect. Our simulations may contribute
visual insight and understanding that enhances such knowledge.

\R Peterson, Ivars. ``Space-Time Odyssey.'' \B Science News\}, Vol. 137, \#15,
April 14, 1990, p. 232-237.

\A
[Review of the work of Hsiung, \E et al\}.]

\S Machines for Ray Tracing

\R Plunkett, David J., Joseph M. Cychosz, and Michael J. Bailey. ``The
Vectorization of a Ray Tracing Program for Image Generation.'' \B Proceedings
of Cyber 200 Applications Seminar\}, NASA Conference Publication 2295, October
1983, p. 315-323.

\A
Ray tracing is a widely used method for producing realistic computer-generated
images. Ray tracing involves firing an imaginary ray from a view point,
through a point on an image plane, into a three dimensional scene. The
intersection of the ray with the objects in the scene determines what is
visible at that point on the image plane. This process must be repeated many
times, once for each point (commonly called a pixel) in the image plane. A
typical image contains more than a million pixels makeing this process
computationally expensive. A traditional ray tracing program processes one ray
at a time. In such a serial approach, as much as Rety percent of the
execution time is spent computing the intersection of a ray with the surfaces
in the scene. With the CYBER 205, many rays can be intersected with all the
bodies in the scene with a single series of vector operations. Vectorization
of this intersection process results in large decreases in computation time.

The CADLAB's interest in ray tracing stems from the need to produce realistic
images of mechanical parts. A high quality image of a part during the design
process can increase the productivity of the designer by helping him visualize
the results of his work. To be useful in the design process, these images must
be produced in a reasonable amount of time. This discussion will explain how
the ray tracing process was vectorized and gives examples of the images
obtained.

\R Kedem, Gershon, and John L. Ellis. ``The Raycasting Machine.'' \B
Proceedings of the IEEE International Conference on Computer Design\}, 1984,
p. 533-538. Also appears in \B Tutorial: Computer Graphics Hardware: Image
Generation and Display\}, Hassan K. Reghbati and Anson Y. C. Lee (eds.),
Computer Society Press, Washington, 1988, p. 285-290. Also appears in
\B Parallel Processing for Computer Vision and Display\}, P. M. Dew,
R. A. Earnshaw, and T. R. Heywood (eds.), Addison-Wesley Publishing Company,
Reading, Massachusetts, 1989, p. 378-401.

\A
Geometric modeling is important in CAD/CAM, robotics, computer vision, and
other fields. Ray casting is a computational utility central to many
applications of geometric modeling. Ray casting is used for calculating shaded
displays and mass properties of solids. It could also be used for collision
detection, null object or same object detection and so forth.

Ray casting algorithms are dependent on the means used to represent solids.
In this work we focus on solids represented by Constructive Solid Geometry. We
develop a special computer structure that will alow ray casting to be done
10X - 1000X faster than in conventional computers. Two types of modules are
needed: domain dependent line primitive classifiers, and domain independent
classification combiners.

The ray casting machine described here is a parallel, pipelined bit serial
machine that classifies a regular lattice of parallel lines. We describe the
design of two-bit serial building clocks, the Classification Combine processor
(CC) and the incremental, bit serial, pipelined Primitive Classifer (PC). These
building blocks were designed from the outset for custom VLSI implementation.
We describe how to use these building blocks to construct a highly parallel
synchronous machine for ray casting. The building blocks are arranged in chips
as machine slice units. By adding more slices, larger and larger machines can be
built.

\R Plunkett, David J. \B A Vectorized Ray Tracing Algorithm\}, M.S.M.E. Thesis,
Purdue University, August 1984. *

\A
Ray Tracing algorithms are widely used for computer synthesis of realistic
images. It is generally accepted that ray tracing yields the most realistic
images of any of the current rendering methods. The technique finds use in the
computer-aided-design field because of the need for realistic images in the
design process. Its use in this and other fields is limited only by the
enormous amounts of computing time associated with these algorithms. This
thesis presents a ray tracing algorithm which dramatically reduces the
computational time. Instead of tracing one ray at a time, as in a traditional
ray tracing program, many rays are traced simultaneously. This allows the
algorithm to take advantage of vector processors found in today's
supercomputers.

\R Plunkett, David J., and Michael J. Bailey. ``The Vectorization of a
Ray-Tracing Algorithm for Improved Execution Speed.'' \B IEEE CG\&A\}, August
1985, p. 52-60.

\A
Ray tracing is, without a doubt, the most versatile and dramatic approach to
realistic rendering. But its practical use has been severely restricted by the massive computing times required. Research described in the literature
indicates that this is largely due to the rays with the surfaces in the scene.
The work presented here uses a vectorized computer architecture to speed the
ray-tracing process. When a ray needs to be fired, that request is placed on a
\E ray queue\}. When the queue becomes full, the vector processor fires all
those rays at once. The program then goes back and uses the intersection
results where they were originally requested. Significant speed increases
result from this retooling of the algorithm.

\R Leray, Pascal. ``Towards a Z-Buffer and Ray-Tracing Multimode
System Based on Parallel Architecture and VLSI Chips.'' \B Advances in
Computer Graphics Hardware I\}, W. Stra\ber (ed.), Springer-Verlag, 1987,
p. 141-145.

\A
[No abstract. Introduction]

After the hidden surfaces algorithms for 3D raster graphics, hardware design
is the main problem, for many applications, such as audiovisual animations,
CAD-CAM, and simulation.

After a short description of our CUBI 7 system (a 3D real-time Z-buffer system),
and its CRISTAL module which increases ray-tracing computations, we present our
hardware project based on:

-- Parallel architecture for ray-tracing and special effects; this module
is also useful for preprocessing the image (rotations, clipping, perspective
transformation).

-- A- or Z-buffer which will be designed on VLSI chips. Polygon filling
will be also designed with pipelined chips.

\R Youssef, Saul. ``Vectorized Simulation and Ray Tracing.'' Technical report
FSU-SCI-87-63, Supercomputer Computations Research Institute, October, 1987.

\A
The severe problem of the speed of Monte Carlo simulation of particle
interaction in High Energy Physics experiments is pointed out once again.
Efforts to solve this problem using vector supercomputers are discussed. One of
these efforts, described in detail, uses general geometry ray tracer to process
all particles in a single vector. Timing numbers are given for simple
benchmarks characteristic of High Energy Physics applications. Using such a
benchmark, the ray tracer is found to be a factor of 140 faster than the
geometric routines of the standard GEANT3 package with both programs running a
two pipeline Cyber 205. A factor of 20 of this increase is due to
vectorization. With the same benchmark and the same code on a four processor
ETA\$\^10\}\$, the vectorized ray tracer is faster by an additional factor of
8.8. In standard units, the vectorized ray tracer on the ETA\$\^10\}\$ is as
fast as the scalar GEANT3 geometry routines running on approximately 12,000 VAX
11/780s. A project to combine this vectorized ray tracer with a vectorized
version of the EGS electromagnetic shower simulation code is described.
Possible applications include ray tracing for Computer Graphics and future
versions of GEANT simulation code.

\S Parallel Machines for Ray Tracing

\s SIMD Architectures

\R Moshell, J. M., and T. J. Cullip. ``An Array Processor for Ray Tracing.''
University of Central Florida, November 1985.

\A
An array processor for ray tracing display generation is described. Working
with a standard sequential host computer, the processor rapidly computes ray
collisions with polyhedral objects. Timing communications issues within the
array are described. The processor is realizable with current CMOS technology.

\R Dorband, John E. ``Ray Tracing on the MPP.'' \B Frontiers of
Massively Parallel Scientific Computation, Proceedings of 1st Symposium at
Goddard Space Flight Center\}, NASA Conference Publication 2478, 1986, p.
211-215, 316.

\A
Generating graphics to faithfully represent information can be a
computationally intensive task. We will present a way of using the MPP to
generate images by ray tracing. This technique uses sort computation, a method
of performing generalized routing interspersed with computation on a
single-instruction-multiple-data (SIMD) computer.

\R Williams, Nicholas S., B. F. Buxton, and H. Buxton. ``Distributed Ray
Tracing Using an SIMD Processor Array.'' \B Theoretical Foundations of
Computer Graphics and CAD\}, NATO ASI Series, Vol. F40, Springer-Verlag, 1988,
p. 703-725.

\A
Recent work on distributed ray tracing algorithms using the Distributed Array
Processor (DAP) will be described. It is shown that ray tracing algorithms are
ideally suited to SIMD processor arrays because, once a set of rays has been
cast from the viewpoint through the pixels in the image plane, the origin and
direction vectors which parameterize each ray after successive reflections can
be mapped uniformly to the DAP processor array. Assigning one ray per
processing element in this manner allows 64 x 64 = 4096 rays to be traced
simultaneously. No local neighborhood operations within the processor array
are required because each ray can be traced independently. Thus, arbitrarily
large images can easily be generated by repeatedly casting 64 x 64 bundles of
rays with the appropriate origin and direction vectors.

Objects in the scene are modeled using quadric primitives which are combined
using the regularized set operations of constructive solid geometry (CSG).
Quadrics were chosen because they are straightforward to describe
mathematically and facilitate calculation of the ray-surface intersections and
also surface normals required for shading calculations. Each of the twelve
canonical quadric forms is represented by a 4 x 4 matrix which can be rotated,
scaled and translated as desired. Although in the current version each
transformation is carried out using parallel matrix multiplication, the small
size of the transformation matrices means that inefficient use is made of the
processor array. Therefore, an improved method is suggested whereby all
quadric primitives can be transformed in parallel.

Using the 1:1 mapping of ray parameters to processing elements as suggested,
the IN-OUT classification resulting from ray intersections with any quadric
primitive or combine operation node in the binary CSG tree an be evaluated in
parallel for an entire ray bundle. Thus, although the binary CSG tree must be
serially traversed, the operations required at each node may be performed in
parallel for a given ray bundle. This approach can therefore be regarded as
`primitive-serial, ray-parallel.'

Using an SIMD processor array in conjunction with the parallel algorithms
suggested here, highly realistic graphics images can be produced in very short
run-times.
 
\R Lin, Tony T. Y., and Mel Slater. ``Stochastic Ray Tracing Using SIMD
Processor Arrays.'' \B The Visual Computer\}, Vol. 7, July 1991, p. 187-199.
 
\A
Stochastic ray tracing is one of the most elegant methods for anti-aliasing
and for generating such phenomena as soft shadows, fuzzy reflections, depth of
field, and motion blur, which are difficult to accomplish with the
conventional ray-tracing algorithm. Unfortunately, it makes use of stochastic
sampling, which requires more than one sample for each pixel. One possible
way to speed up ray tracing is to explore the inherent parallelism of the
algorithm. In the past few years, the major focus of parallel ray-tracing
research has been on the use of MIMD architectures. Although SIMD
architectures may be ideal for ray tracing simple scenes, they have been
thought unsuitable for ray tracing complex scenes. However, by using scene
coherence, we have found that stochastic ray tracing using SIMD processor
arrays can be efficient as most of the existing MIMD ray-tracing algorithms
and more cost effective.

\s MIMD Architectures

\R Nishimura, Hitoshi, Hiroshi Ohno, Toru Kawata, Isao Shirakawa, and Koichi
Omura. ``LINKS-1: A Parallel Pipelined Multimicrocomputer System for Image
Creation.'' \B Proceedings of the 10th Annual International Symposium on
Computer Architecture\}, 1983, p. 387-394. Also appears in \B Tutorial:
Computer Graphics Hardware: Image Generation and Display\}, Hassan K. Reghbati
and Anson Y. C. Lee (eds.), Computer Society Press, Washington, 1988,
p. 320-327.

\A
A multimicrocomputer system is described, stressing mainly software and
hardware architectures, which have been constructed mainly for image creation.
This system is distinctive mainly in that (i) 64 unit computers are
interconnected with a root computer, each of equal performance, such that a
number of unit computers constitute a pipeline computer and such pipelined
computers work in parallel, all controlled by the root computer, and (ii) an
intercomputer memory swapping unit is introduced, which is to be linked with a
pair of unit computers to transfer a great amount of data at a time from one to
the other through the use of a bus exchange switch.

\R Ullner, Michael Karl. \B Parallel Machines for Computer Graphics\}.
Ph.D. Dissertation, California Institute of Technology, 1983.

\A
Computer graphics provides some ideal applications for the kind of highly
parallel implementations made possible by advances in integrated circuit
technology. Specifically, hidden line and hidden surface surface algorithms,
while easily defined and simple in concept, entail a substantial amount of
computation. This requirement fits the characteristics of integrated circuit
technology, where modular designs involving regular communication between
many concurrent operations are rewarded with high performance as an acceptable
cost.

Ray tracing is a very flexible technique that can be used to produce some of
the most realistic of all computer generated images by simulating the
interactions of light rays with surfaces in a modeled scene. Because light
rays are mutually independent, many may be processed simultaneously, and the
potential for concurrency is great. One architecture for expediting a ray
tracing algorithm consists of a conventional computer equipped with a special
purpose peripheral device for locating the intersections of rays and surfaces.
This intersection computation is the most time consuming aspect of ray
tracing. Although the attched processor configuration can produce images more
quickly than an unaided computer, its performance is limited. Alternatively,
a pipeline of surface processors can replace the peripheral device. Each
processor computes the intersections of its stored surface with rays that flow
through the pipe. Such a machine can be quite fast, and its performance can be
increased by lengthening he pipeline, but the component processors are not
very effectively utilized. A third approach combines the advantages of the
prior two machines by using an array of processors, each simulating a distinct
subvolume of the modeled world by treating light rays traveling through space
as message flowing between processors. Local communication is sufficient
because light rays travel continuously through space.

In real time computer graphics, successive images must be produced in times
that are imperceptible to a viewer. Although the ray tracing machines fall
short of this performance, it is possible to compromise image quality in order
to produce a highly parallel machine capable of real time operation. The
processors in such a machine are organized to form a binary tree. Leaf
processors scan-convert surfaces, producing a sequence of segments, where a
segment is the portion of a surface that appears on a single scan line of the
display. Processors toward the root of the tree accept two such segment
sequences and produce a third in which all segments overlap has been resolved.
The final image is available at the root of the tree. The communication
bottleneck that would otherwise occur at the root can be eliminated by
breaking out parallel roots, and the resulting tree may be extended to scenes
of almost arbitrary complexity merely by increasing the supply of available
processors.

Massive paralleism can also be applied to the problem of removing hidden edges
from line drawings. A suitable architecture takes the form of a pipeline in
which each processor is dedicated to the handling of a single polygon edge.
These processors successively clip line segments passing through the pipeline
to eliminate portions hidden behind surfaces. Each edge processor can be
constructed out of little more than three serial multipliers.

The machines described here are varied in organization, and each functions
differently, but their treatment of sorting in one ingredient common to all.
Sorting is a key component of hidden surface algorithms running on
conventional computers, but its extensive communication requirements make it
costly for use in a highly integrated design. Consequently, the highly
parallel machines described here operate largely without sorting. Instead,
they maintain information in sorted order or make use of already sorted
information to limit communication requirements.

\R Deguchi, Hiroshi, Hitoshi Nishimura, Hiroshi Yoshimura, Toru Kawata, Isao
Shirakawa, and Koichi Omura. ``A Parallel Processing Scheme for
Three-Dimensional Image Generation.'' \B International Symposium on Circuits
and Systems '84\}, Vol. 3, p. 1285-1288.

\A
A parallel processing scheme for three-dimensional image generation is
described, which operates on a multimicrocomputer system LINKS-1 composed of
65 unit computers. In this scheme, a frame of image is generated by means of
the ray tracing approach such that the light intensity calculation for the
whole pixels of a frame is allocated evenly to all unit computers, one working
in parallel with the others. A number of experimental results are also shown,
which reveal how effectively this scheme is implemented with the use of a
variety of hardware and software facilities.

\R Dipp\'e, Mark, and John Swensen. ``An Adaptive Subdivision Algorithm and
Parallel Architecture for Realistic Image Synthesis.'' \B SIGGRAPH '84\},
p. 149-158. Also appears in \B Tutorial: Computer Graphics Hardware: Image
Generation and Display\}, Hassan K. Reghbati and Anson Y. C. Lee (eds.),
Computer Society Press, Washington, 1988, p. 310-319.

\A
An algorithm for computing ray traced pictures is presented, which adaptively
subdivides scenes into \$S\$ subregions, each with roughly uniform load. It can
yield speedups of \$O(S\^2/3\})\$ over the standard algorithm.

This algorithm can be mapped onto a parallel architecture consisting of a
three dimensional array of computers which operate autonomously. The algorithm
and architecture are well matched, so that communication overhead is small with
respect to the computation, for sufficiently complex scenes. This allows close
to linear improvements in performance, even with thousands of computers, in
addition to the improvement due to subdivision.

The algorithm and architecture provide mechanisms to gracefully degrade in
response to excessive load. The architecture also tolerates failures of
computers without errors in the in the computation.

\R Cleary, John G., Brian Wyvill, Graham M. Birtwistle, and Reddy Vatti.
``Multiprocessor Ray Tracing.'' \B Computer Graphics Forum\}, Vol. 5, 1986,
p. 3-12. Revision of technical report 83/128/17, Computer Science Department,
University of Calgary, October 1983.

\A
A multiprocessor algorithm for ray tracing is described. The performance of
the algorithm is analyzed for a cubic and square array of processors with only
local communication between near neighbors. Theoretical expressions for the
speedup of the system as a function of the number of processors are derived.
These analytic results are supported by simulations of ray tracing on a number
of simple scenes with polygonal surfaces. It is found that a square network
of processors generally performs better than a cubic network. Some comments
are made on the construction of such a system using current (1985)
microprocessor technology.

\R Deguchi, Hiroshi, Isao Shirakawa, Koichi Omura, Masato Nishida, Hitoshi
Nishimura, and Toru Kawata. ``A Tree-Structured Parallel Processing System for
Image Generation by Ray Tracing.'' \B Systems and Computers in Japan\},
Vol. 17, \#12, 1986, p. 51-62. Translated from \B Denshi Tsushin Gakkai
Ronbunshi\}, Vol. 69-D, \#2, Feb. 1986, p. 170-179.

\A
An image generation system by ray tracing was implemented on a distributed
parallel processing system composed of loosely coupled multimicrocomputers. An
improvement was made by extending the architecture from the star structure to
the hierarchical tree structure. This improvement makes it possible for an
animated image to be generated at high speed with shading which can represent
the shape and texture of three-dimensional objects with high quality. This
paper outlines the hierarchical tree-structured image generation system,
discussing the parallel processing mechanisms of the system, such as data
transfer and hierarchical load distribution schemes. Experiments were made to
evaluate the performance. Problems in the tree-structured system are pointed
out, and remedies are proposed (area redistribution, and area subdivision).
Experiments are made to evaluate the effectiveness of these methods. Thus,
it is demonstrated that the tree-structured system is useful in the image
generation using ray tracing.

\R Defend, Daniel Evan. ``Parallel Ray Tracing in a Vector--Multiprocessing
Environment.'' CSRD Rpt. No. 677, Center for Supercomputing Research and
Development, University of Illinois, September, 1987.

\A
Various techniques which introduce scalar and vector parallelism into the ray
tracing environment are explored. Several scalar and vector parallel
implementations are presented which drastically decrease execution times of
experimental ray tracers run on a vector multiprocessor. Issues which govern
how and where to exploit both types of parallelism are discussed, and then
modifications needed to incorporate the parallelism into an existing algorithm
are given.

Certain algorithmic enhancements make the ray tracing process more efficient,
i.e. yield faster execution times. Additionally, these enhancements may make
certain types of scalar and vector parallelism more effective. The motivation
for several enhancements of this nature is presented, and then modifications
to traditional ray tracing approaches are developed to provide for these
algorithm changes. With these algorithm modifications, an attempt is made to
enhance the amount of parallelism achieved through parallel implementation.

\R Kobayashi, Hiroaki, Tadao Nakamura, and Yoshiharu Shigei. ``Parallel
Processing of an Object Space for Image Synthesis Using Ray Tracing.'' \B The
Visual Computer\}, Vol. 3, 1987, p. 13-22.

\A
This paper presents a novel parallel processing system for image synthesis
using ray tracing. An object space is divided into parts (subspaces), each of
which is allocated to a processor. The processor detects, simultaneously the
intersections of the surfaces of each object and a fixed number of rays over
the whole space, and calculates the local intensity on an object in each
subspace. The global intensities of pixels on a screen are calculated by the
other kind of processors simultaneously. We also present the optimal data
structure, based on an adaptive division algorithm, for parallel processing of
the object space.

\R Caubet, R., Y. Duthen, and V. Gaildrat. ``VOXAR: A Tridimensional
Architecture for Fast Realistic Image Synthesis.'' \B New Trends in Computer
Graphics, Proceedings of CG International '88\}, Nadia Magnenat-Thalmann and
Daniel Thalmann (eds.), Springer-Verlag, p. 135-149.

\A
The ray-tracing algorithm was up to now the origin of the most beautiful
synthesized images. Yet, it was penalized by the great number of intersection
computations required, due to the non-exploitation of the spatial coherency.

In order to decrease the cost of image production, architectures were
proposed, based on the ray-tracing algorithm parallelism.

We propose a volumic architecture model traced over reality, using the
parallelism due to the scene coherency.

This architecture is based on the object decomposition into voxels and on the
incremental integer logic. This allows the suppression of the intersection
computations at the rendering step.

During the object decomposition into voxels, the texture is included into the
material features. Thus, the objects are not created plain but textured just
as if they were sculptured into the material.

The object decomposition into voxels allows the generation of composite scenes
where the objects modelled by different methods will be rendered by the same
technique.

\R Crow, Franklin C. ``Parallelism in Rendering Algorithms.'' \B Graphics
Interface '88\}, p. 87-96.

\A
The need for increased computing power for rendering computer imagery is
motivated and the sources from which it might be derived surveyed. Increased
power can come from parallelism, as well as faster technology, implying new
machine architectures and new algorithms. Surveys sketch early attempts at
using available parallel architectures and look at the limitations and
strengths of some existing architectures. Finally, potential parallel
algorithms for the rendering process are sketched including rough analyses
of potential performance bottlenecks.

\R Gaudet, Severin, Richard Hobson, Pradeep Chilka, and Thomas Calvert.
``Multiprocessor Experiments for High-Speed Ray Tracing.'' \B ACM TOG\},
Vol. 7, \#3, July 1988, p. 151-179.

\A
New single- and multiprocessor models for ray tracing are presented. Important
features are (1) the use of custom VLSI building blocks, (2) the use of a
modified hierarchical data-structure-based ray tracing algorithm with three
disjoint data sets, and (3) scene access through adaptive information
broadcasting. A modular design is presented that permits incremental
performance enhancement up to two orders of magnitude over conventional
minicomputers or workstations. Ray tracing is a surprisingly good application
for a shared bus architecture because of the computational complexity of
intersecting light rays with graphics objects.

\R Kobayashi, Hiroaki, Satoshi Nishimura, Hideyuki Kubota,
Tadao Nakamura, and Yoshiharu Shigei. ``Load Balancing Strategies for a
Parallel Ray-Tracing System Based on Constant Subdivision.'' \B The Visual
Computer\}, Vol. 4, 1988, p. 197-209.

\A
Static and dynamic load balancing strategies for a multiprocessor system for
a ray tracing algorithm based on constant subdivision are presented. An
object space is divided into regular cubes (subspaces), whose boundary planes
are perpendicular to the coordinate axes, and these are allocated to the
processors in the system. Here, load balancing among the processors is the most
important problem. Firstly, in a category of static load balancing, strategies
for mapping the subspaces into the processors are evaluated by simulation.
Moreover, a hierarchical multiprocessor system is proposed in order to realize
dynamic load balancing with the static one. Its architecture can overcome
the limitation of the static load balancing in a large scale multiprocessor
system.

\R Marsh, Stephen C. ``Fine Grain Parallel Architectures and the Creation of
High-Quality Images.'' \B Theoretical Foundations of Computer Graphics and
CAD\}, NATO ASI Series, Vol. F40, Springer-Verlag, 1988, p. 727-754.

\A
This paper presents a preliminary study of fine-grain parallel architectures
for the generation of high quality computer graphics in a significantly
reduced period of time than is presently possible. Two architectures are
considered, both of which consist of message passing networks of processing
elements which can be implemented as VLSI circuitry. Each architecture is
designed for one particular three-dimensional object representation. The
first architecture uses octrees to generate images in a top-down hierarchical
manner, whilst the other uses Constructive Solid Geometry in a bottom-up
hierarchical approach.

\R Scherson, Isaac D., and Elisha Caspary. ``Multiprocessing for Ray
Tracing: A Hierarchical Self-Balancing Approach.'' \B The Visual Computer\},
Vol. 4, 1988, p. 188-196.

\A
A novel parallel processing algorithm for image synthesis using ray tracing is
presented. The scene is first organized in a hierarchical data structure which
is then cut at some level. The object descriptions along with their bounding
volumes are distributed accordingly among the processors of an MIMD system.
There are two independent processes in each processor: one is demand driven and
used for bounding volumes calculations while the second is data driven and used
for intersection calculations. This scheme, where the first process can be
executed by any processor, suggested an algorithm with an embedded load
balancing mechanism. It has almost linear speedup and its storage requirements
are small. Simulation results are presented to illustrate these features.

\R Stepoway, Stephen L., and Michael Christiansen. ``Parallel
Rendering of Fractal Surfaces.'' \B International Journal of Parallel
Programming\}, Vol. 17, \#1, 1988, p. 43-58.

\A
Fractal surfaces are a useful modeling technique for terrain in computer
graphics. Although an algorithm exists for ray tracing (Mandelbrot) fractal
surfaces, the technique is computationally very expensive. The large degree of
parallelism inherent in the problem suggests the use of parallel architectures
for generating these images. A parallel rendering algorithm is described for
shared memory MIMD machines which takes advantage of image coherence to reduce
computation. This algorithm has, on a Sequent Balance 21000 with 20 processors,
demonstrated a near-linear speedup. The possible synchronization bottlenecks
are examined by statically assigning different numbers of CPUs to sections of
the screen.

\R Bu, Jichun, and Ed F. Deprettere. ``A VLSI System Architecture for
High-Speed Radiative Transfer 3D Image Synthesis.'' \B The Visual Computer\},
Vol. 5, 1989, p. 121-133. Revision of same paper in \B Proceedings of
Eurographics '87\}, Guy Mar\'echal (ed.), p. 221-234.

\A
In this paper we describe a VLSI system architecture for high-speed synthesis
of 3D images composed of diffsely reflective surfaces. The system consists of
two loosely coupled sub-systems. The first sub-system computes the form-factor
matrix \$F\$. The form-factors are computed by an efficient ray-tracing
algorithm. The second sub-system, a multiprocessor Gauss-Seidel iterative system
solver, solves the sparse system of radiosity equations \$(I - \L F)b = e\$.

\R Caspary, Elisha, and Isaac D. Scherson. ``A Self-Balanced
Parallel Ray-Tracing Algorithm.'' \B Parallel Processing for Computer Vision
and Display\}, P. M. Dew, R. A. Earnshaw, and T. R. Heywood (eds.),
Addison-Wesley Publishing Company, Reading, Massachusetts, 1989, p. 408-419.

\A
A novel parallel processing algorithm for image synthesis using ray tracing is
presented. The scene is first organized in a hierarchical data structure which
is cut at some level, and the object descriptions along with their bounding
volumes are distributed accordingly among the processors of an MIMD system.
There are two independent processes in each processor: the first one is demand
driven and used for bounding volumes calculations,while the second one is data
driven and used for intersection calculations. This scheme, where the first
process can be executed by any processor, suggests an algorithm with an
embedded load-balancing mechanism. It has an almost linear speedup and its
storage requirements are small. Simulation results are presented to
illustrate these features.

\R Chalmers, M. ``On the Design and Implementation of a Multiprocessor Ray
Tracer.'' \B Parallel Processing for Computer Vision and Display\}, P. M. Dew,
R. A. Earnshaw, and T. R. Heywood (eds.), Addison-Wesley Publishing Company,
Reading, Massachusetts, 1989, p. 420-430.

\A
A ray tracer has been developed on a multiprocessor machine at the University
of East Anglia, as a vehicle for research into realistic image synthesis.
Various components of the tracer are distributed across processing elements.
The development of the tracer was hampered by a lack of flexibility of
configuration, and a low level of data abstraction.

Consideration of these problems led to the construction of an Occam
programming style on object-oriented and actor languages. The specification
and implementation of processes are described, along with the inheritance of
functionality, the communication infrastructure, pseudo-dynamic process
creation and facilities for monitoring and debugging.

\R Green, Stuart A., Derek J. Paddon, and E. Lewis. ``A Parallel
Algorithm and Tree-Based Computer Architecture for Ray-Traced Computer
Graphics.'' \B Parallel Processing for Computer Vision and Display\}, P. M.
Dew, R. A. Earnshaw, and T. R. Heywood (eds.), Addison-Wesley Publishing
Company, Reading, Massachusetts, 1989, p. 431-442.

\A
The ray-tracing algorithm is well known for its high computational complexity
and this has motivated research into exploiting the inherent parallelism of
the algorithm by using multiprocessor systems. However, an object model to
describe a scene of realistic complexity requires a very large database, which
restricts the scope for designing an effective concurrent architecture. In
this paper, we describe and evaluate research which has led to a multiprocessor
system that supports a database of arbitrary size. The results of the system
show an optimal speedup for small databases while still maintaining a good
performance for larger problems.

\R Green, Stuart A., and Derek J. Paddon. ``Exploiting Coherence for
Multiprocessor Ray Tracing.'' \B IEEE CG\&A\}, November 1989, p. 12-26.

\A
The ray-tracing algorithm is widely used for realistic image synthesis. The
scalability and cost effectiveness of general-purpose distributed-memory
multiprocessor systems makes them particularly suitable for ray-tracing
applications. However, the limited memory available to each processor in such a
system requires schemes to distribute the model database among the processes.
This article identifies a form of coherence in the ray-tracing algorithm that
can be exploited to develop optimum schemes for data distribution in a
multiprocessor system. This in turn gives rise to high processor efficiency
for systems with limited distributed memory.

\R Kobayashi, Hiroaki, Hideyuki Kubota, Susumu Horiguchi, and Tadao
Nakamura. ``Effective Parallel Processing for Synthesizing Continuous Images.''
\B New Advances in Computer Graphics, Proceedings of CG International '89\},
R. A. Earnshaw and B. Wyvill (eds.), p.343-352.

\A
One of the biggest problems in computer animation is the enormous amount of
computations necessary to synthesize an animation sequence. In this paper,
effective parallel processing for synthesizing continuous images is presented.
Our parallel architecture is based on object-oriented parallel processing a
ray-tracing algorithm. A task allocation using \E load coherence of each
subspace\} between continuous images is proposed for balancing computational
loads among processing elements. For the performance evaluation of our
parallel architecture, the effect of load balancing is examined, in detail,
by computer simulation.

\R Jensen, David, and Daniel Reed. ``Ray Tracing on Distributed Memory Parallel
Systems.'' Report No. UIUCDCS-R-89-1551, Department of Computer Science,
University of Illinois at Urbana-Champaign, October 1989.

\A
Among the many techniques in computer graphics, ray tracing is prized because
it can render realistic images, albeit at great computational expense. Ray
tracing's large computation requirements, coupled with its inherently parallel
nature, make ray tracing algorithms attractive candidates for parallel
implementation. In this paper we explore the performance of several approaches
to ray tracing on a distributed memory parallel system. These algorithm
variations introduce parallelism based on both ray and object partitions. Ray
partitioning schemes distribute image generation across multiple processors but
require rendundant storage of the scene data. In contrast, object partitioning
distributes the scene data, allowing the processing of more complex scenes, but
with increased interprocessor communication. The choice of an appropriate
techique depends on the balance of parallel computation and interprocessor
communication. To explore this balance, we conducted a series of parametric
performance experiments. The performance \E effects\} of different algorithm
choices were determined through traditional timing analysis. The \E cause\} of
these performance differences were identified via a set of performance
instrumentation tools and their associated visualization software.

\R Jevans, David A. J. ``Optimistic Multi-Processor Ray Tracing.''
\B New Advances in Computer Graphics, Proceedings of CG International '89\},
R. A. Earnshaw and B. Wyvill (eds.), p. 507-522.

\A
An optimistic method for ray tracing on multi-processors which communicate by
message passing is presented. This method exploits more parallelism than
previously published algorithms, and makes multi-processor ray tracing of
complex scenes practical. An implementation which uses the Time Warp
synchronization method is discussed. A second more efficient implementation
which makes use of the Virtual Time concept and the Time Warp implementation of
cancellation is presented as a more practical solution to the problem of
efficient multi-processor ray tracing and load balancing. The algorithm is
compared to previous algorithms for message passing multi-processors and shared
memory multi-computers.

\R Potmesil, Michael, Leonard McMillan, Eric M. Hoffert, Jennifer F. Inman,
Robert L. Farah, and Marc Howard. ``A Parallel Image Computer with a Distributed
Frame Buffer: System Architecture and Programming.'' \B Proceedings of
Eurographics '89\}, W. Hansmann, F. R. A. Hopgood and W. Strasser (eds.),
p. 197-208, 549.

\A
We describe the system architecture and the programming environment of the
Pixel Machine - a parallel image computer for 2D and 3D image synthesis and
analysis. The architecture of the computer is based on an array of asynchronous
MIMD nodes with a parallel access to a large frame buffer. The system consists
of a pipeline of \E pipe nodes\} which execute sequential algorithms and an
array of \$m \x n\$ pixel nodes which execute parallel algorithms. A \E pixel
node\} accesses every \$m\$-th pixel on every \$n\$-th scan line of a
distributed frame buffer. Each processing node is based on a high-speed,
floating-point programmable processor.

The programmability of the computer allows all algorithms to be implemented in
software. A set of mapping functions transfers image algorithms written for
conventional single-processor computers to algorithms which execute in the
pixel nodes and access the distributed frame buffer. The ability to use
floating-point computations in pixel operations, such as antialiasing, ray
tracing, and filtering, allows high-quality image generation and processing.
The image computer provides up to 820 megaflops of peak processing power and 48
megabytes of memory for data-visualization applications.
 
\R Quek, Lee Hian. \B Ray Tracing with Space Subdivision on a
Vector-Multiprocessor System\}, Masters Thesis, Report No. UIUCDCS-R-89-1491,
Department of Computer Science, University of Illinois at Urbana-Champaign,
February 1989.
 
\A
The development of a parallel ray tracer with space subdivision enhancement is
presented. Parallel optimizations included both concurrency and vectorization.
Space subdivision was performed by subdividing the object space into
three-dimensional volumes called voxels. The voxels are subdivided recursively
until each one is associated with only a small number of primitives. This
method reduces the number of unnecessary ray-primitive intersection
calculations during the ray tracing process.
 
Test runs with various data sets were conducted to measure the speedups
resulting from the optimized ray tracer. Results showed that the optimized ray
tracer can achieve linear performance; i.e., the tracing time only increases
linearly with increasing number of primitives.

\R Badouel, Didier, Kadi Bouatouch, and Thierry Priol. ``Ray Tracing on
Distributed Memory Parallel Computers: Strategies for Distributing Computations
and Data.'' \B SIGGRAPH '90 Parallel Algorithms and Architecture for 3D Image
Generation Course Notes\}.

The ray tracing algorithm produces high quality images, but it requires a lot
of computations which makes it extremely time-consuming. Several attempts have
been made to reduce the synthesis time by using high speed parallel computers.
For example, distributed memory parallel computers, such as hypercubes or
\E transputer\}-based machines, offer an interesting performance/cost ratio.
Several studies have used paralle computers to speed up the ray tracing
algorithm so as to render complex scenes with several thousand objects. However
few of them have lead to real implementation due to the complexity of the
solution proposed by the authors. This paper introduces a new approach
emulating a read-only shared memory on a distributed memory parallel computer.
Results are given and are compared to a previous parallel ray tracing algorithm
that we have implemented on an iPSC/2.

\R Barrett, Martin L. ``A Load Balancing Experiment for Parallel Ray
Tracing.'' \B Proceedings of Ausgraph '90\}, p. 145-155.

\A
Ray tracing has the possibility for parallelism, due to the independence of the
light rays being traced. This paper investigates parallel algorithms for ray
tracing based on task scheduling. Subtasks involved in tracing a ray are
identified, and processors are assigned to subtasks rather than assigning rays
to processors. Three types of assignment schemes were tested: static
scheduling, where the assignment of processors to subtasks does not change, and
two types of dynamic scheduling, which attempt to balance the load among
available processors. The results of these methods are compared against a more
straightforward parallel scheme, image space subdivision. The space subdivision
method was found to be superior to the scheduling methods; among the scheduling
schemes, event-driven balancing performed the best. As in many parallel
algorithms, overhead due to interprocess communication may limit the usefulness
of the scheduling methods.

\R Green, Stuart A., and Derek J. Paddon. ``A Highly Flexible Multiprocessor
Solution for Ray Tracing.'' \B The Visual Computer\}, Vol. 6, 1990 p. 62-73.

\A
The ray tracing algorithm continues to attract much research and development to
improve the quality of the images that are generated, and to reduce the time
taken to produce them. By identifying the key requirements of a development
system from the user's point of view, we describe a general-purpose
multiprocessor solution for ray tracing which may be used to reduce execution
time without restricting development of the ray tracing code. The solution is
based upon a distributed memory multiprocessor system in which each processor
addresses a small amount of memory relative to the size of the model database.
Methods for exploiting the coherence of references to entries in the database
are described which use a combination of dynamic and static caching techniques.
This scheme allows databases of arbitrary size to be supported on
multiprocessors with limited distributed memory.

\R H\'ebert, M.-P., M. D. J. McNeill, B. Shah, R. L. Grimsdale, and
P. F. Lister. ``MARTI--A Multiprocessor Architecture for Ray Tracing Images.''

\A
Multiprocessor systems are well suited to ray tracing, since each ray can be
traced independently. However, the large databases required to model complex
scenes create problems of data access. In this paper we propose a
multiprocessor architecture for ray tracing which removes the need for
duplication of the database at processor level. The database is held on a group
processor basis, and resides in shared memory. Many of these groups,
or \E clusters\}, can be replicated to form a highly parallel multiprocessing
system. Results of a software simulation of the architecture are promising,
indicating that a large number of processors per cluster is possible.

\s Hypercube Implementations

\R Goldsmith, Jeffrey, and John Salmon. ``A Ray Tracing System
for the Hypercube.'' Caltech Concurrent Computing Memorandum HM-154, 1985.

\A
Ray tracing for computer graphics is one of the most CPU intensive algorithms
in use today. We discuss ray tracing and the design of a ``state-of-the-art''
ray tracing renderer for the Caltech Hypercube. Since rays do not interact,
the communication overhead in a parallel decomposition can be very small. Load
imbalance is the largest source of inefficiency, and it can be reduced by
various means, including a scattered decomposition or adaptive run time
decomposition. Data base decomposition is also feasible for very complex
images. With the Mark III hypercube we will have the computing power to
investigate new techniques such as the modeling of chromatic aberration and
distributed light sources.

\R Bouatouch, K., and T. Priol. ``Parallel Space Tracing: An Experience on an
iPSC Hypercube.'' \B New Trends in Computer Graphics, Proceedings of CG
International '88\}, Nadia Magnenat-Thalmann and Daniel Thalmann (eds.),
Springer-Verlag, p. 170-188. Also apppears as ``Experimenting with a Parallel
Ray-Tracing Algorithm on a Hypercube Machine'' in \B Proceedings of
Eurographics '88\}, David A. Duce and Pierre Jancene (eds.), p. 243-259. Each
paper contains a few details that the other does not.

\A
A parallel space tracing algorithm is presented. It subdivides the scene into
regions. These latter are distributed among the processors of a 2D array
architecture which is mapped onto an iPSC hypercube machine designed by Intel
company. Each processor subdivides its own region into cells to accelerate the
ray tracing algorithm. Processors communicate by means of messages. The
pyramidal shape of the regions allows the deletion the primary ray messages.
An efficient termination algorithm is described. A method of performing a
roughly uniform load distribution is proposed.

\R Delany, Hubert C. ``Ray Tracing on a Connection Machine.'' Technical Report
\#VZ88-3, Thinking Machines, April 1988.

\A
A new ray-tracing algorithm designed specifically for massively parallel
hypercube connected processors is introduced. World space is subdivided
according to a fixed size 3-D orthogonal grid. Rays are traced using ray-points
which move along the rays, referencing the voxels intersected. One processor
is assigned per ray, as well as one processor per object fragment.

A pointerless data structure called an induced octree is used. This structure
exists only as an ordering of the data in processor-address space, yet with it,
all processors can determine the jump-distance to the nearest non-empty voxel
in parallel to within a power of two. Ray-points move by large jumps whenever
possible, and ray-object intersection proceeds in log time in the average ray
length. Sorting via the network is the parallel analogue to octree-traversal.

A code-scheduling mechanism is introduced which improves processor usage for
SIMD architectures.

Preliminary results are presented for an implementation using a CM-1 CPU
equipped with 16K processors.

\R Kobayashi, H., T. Nakamura, and Y. Shigei. ``A Strategy for Mapping Parallel
Ray-Tracing into a Hypercube Multiprocessor System.'' \B New Trends in Computer
Graphics, Proceedings of CG International '88\}, Nadia Magnenat-Thalmann and
Daniel Thalmann (eds.), Springer-Verlag, p. 160-169.

\A
We present a systematic and efficient strategy for mapping an
adaptively/regularly subdivided object space (a set of subspaces) into the
nodes of the hypercube. The property of this mapping is that the distance
between the neighboring subspaces on the hypercube is proportional to the
difference between the sizes of these subspaces. Especially, if neighboring
subspaces are of equal size, these subspaces are allocated to the neighboring
processors. As a result, we can realize a communication-effective
implementation of parallel ray-tracing on the hypercube multiprocessor system.
The mapping is derived from the byproduct of octree encoding of an object space.

\R Orcutt, David Edward. ``Implementation of Ray Tracing on the
Hypercube.'' \B Third Conference on Hypercube Concurrent Computers and
Applications\}, Geoffrey Fox (ed.), Vol. 2, 1988, p. 1207-1210.

\A
This prelimary report presents one implementation of a ray tracing system. The
ray tracing system was divided and distributed onto the hypercube based on
data to be processed. The implementation which includes a dynamic load
balancing scheme will be shown to be very efficient for large scenes.

\R Salmon, John, and Jeff Goldsmith. ``A Hypercube Ray-tracer.''
\B Third Conference on Hypercube Concurrent Computers and Applications\},
Geoffrey Fox (ed.), Vol. 2, 1988, p. 1194-1206.

\A
We describe a hypercube ray-tracing program for rendering computer graphics.
For small models, which fit in the memory of a single processor, the
ray-tracer uses a scattered decomposition of pixels to balance the load, and
achieves a very high efficiency. The more interesting case of large models,
which cannot be stored in a single processor, requires a decomposition of the
model data as well as the pixels. We present algorithms for constructing a
decomposition based upon information about the frequency with which different
elements of the model are accessed. The resulting decomposition is
approximately optimized to minimize communication and achieve load balance.

\R Priol, Thierry, and Kadi Bouatouch. ``Static Load Balancing
for a Parallel Ray Tracing on a MIMD Hypercube.'' \B The Visual Computer\},
Vol. 5, 1989, p. 109-119.

\A
A parallel ray tracing algorithm is presented. It subdivides the scene into 3D
regions, the adjacency of which is modelled by a connectivity graph of regions.
Since with each region is associated a ray tracing process, this graph becomes a
graph of processes, the edges of which represent the communications between
processes. This graph of processes is suitably mapped onto a hypercube topology
so as to minimize the communiction cost. Static load balancing is performed and
solutions are brought to the problems of network congestion and termination.
 
\R Badouel, Didier, and Thierry Priol. ``An Efficient Parallel Ray Tracing
Scheme for Highly Parallel Architectures.'' \B Fifth Eurographics Workshop on
Graphics Hardware\}, 1990, p. ?.
 
\A
The production of a realistic image generated by computer requires a huge
amount of computation and a large memory capacity. The use of highly parallel
computers allows this process to be performed faster. Distributed memory
parallel computers (DMPCs), such as hypercubes or \E transputer\}-based
machines, offer an attractive performance/cost ratio when the load balancing
has been balanced and the partition of the data domain has been performed.
This paper presents a parallel ray tracing algorithm for DMPC usin a Shared
Virtual Memory (SVM) which solves these two classical problems. This algorithm
has been implemented on a hypercube iPSC/2 and results are given.
 
\R Carter, Michael, and Keith Teague. ``Distributed Object Database Ray Tracing
on the Intel iPSC/2 Hypercube.'' \B Proceedings of the 5th Distributed Memory
Computing Conference\}, IEEE Society Press, 1990, p. 217-222.
 
\A
A medium-grained, distributed-memory parallel computer is used as a platform
from which to research a specific issue in accelerating the ray-tracing
process. The work presented here deals specifically with the problem of
distributing large object databases over the computing nodes of the Intel
iPSC/2. An efficient object database decomposition method is presented which
behaves like a fully-associative cache. Ramifications of the distributed
object database forced the development of an interruptible ray-tracing loop, a
ray scheduler, and a dynamic viewplane decomposition. Performance metrics,
such as object database hit ratio, load-balance, and efficiency are presented.

\s Transputer Implementations
 
\R Aktkin, Phil, Steve Ghee and Jamie Packer. ``Transputer Architectures for Ray
Tracing.'' \B Proceedings of Computer Graphics '87\}, Online Publications,
1987, p. 157-172.
 
\A
This paper will describe the application of a network of Inmos transputers to
a complex task such as ray tracing. Examples will be given for breaking such a
task down into concurrent processes, which can be distributed across a
processing network.

\R Packer, Jamie. ``Exploiting Concurrency: A Ray Tracing Example.''
Inmos Technical Note 7, Inmos Limited, October 1987.

\A
[No abstract or (informative) introduction. This paper describes the INMOS
transputer IMS T414 and how ray tracing can be implemented on a linear array
of transputers.]

\R Ransen, Owen F. ``The Art of Ray Tracing.'' \B Byte\}, February 1990,
p. 238-242.

\A
[No abstract. Semi-technical paper about ray tracing on transputers.]

\S Other Related Synthesis Methods

\s The Rendering Equation

\R Kajiya, James T. ''The Rendering Equation.'' \B SIGGRAPH '86\}, p.
143-150.

\A
We present an integral equation which generalizes a variety of known
rendering algorithms. In the course of discussing a Monte Carlo solution a new
form of variance reduction is presented, called hierarchical sampling, and a
number of elaborations are given that show that it may be an efficient new
technique for a wide variety of Monte Carlo procedures. The resulting
rendering algorithm extends the range of optical phenomena which can be
effectively simulated.

\s Radiosity

\R Wallace, John R., Michael F. Cohen, and Donald P. Greenberg.
``A Two-Pass Solution to the Rendering Equation: A Synthesis of Ray Tracing
and Radiosity Methods.'' \B SIGGRAPH '87\}, p. 311-320.

\A
View-independent and view-dependent image synthesis techniques, represented by
radiosity and ray tracing, respectively, are discussed. View-dependent
techniques are found to have disadvantages for calculating the specular
component of illumination and view-independent techniques for the diffuse
component. Based on these observations a methodology is presented for
simulating global illumination within complex enviroments using a two-pass
approach. The first pass is view-independent and is based on the hemi-cube
radiosity algorithm, with extensions to include the diffuse reflection and
transmission. The second pass is view-dependent and is based on an alternative
to distributed ray tracing in which a z-buffer algorithm is used to sample
intensities contributing to the specularly reflected or transmitted intensity.

\R Ward, Gregory J., Francis M. Rubinstein, and Robert D. Clear.
``A Ray Tracing Solution for Diffuse Interreflection.'' \B SIGGRAPH '88\},
p. 85-92.

\A
An efficient ray tracing method is present for calculating interreflections
between surfaces with both diffuse and specular components. A Monte Carlo
technique computes the indirect contributions to illuminance at locations
chosen by the rendering process. The indirect illuminance values are averaged
over surfaces and used in place of a constant ``ambient'' term. Illuminance
calculations are made only for those areas participating in the selected view,
and the results are stored so that subsequent views can reuse common values.
The density of the calculation is adjusted to maintain a constant accuracy,
permitting less populated portions of the scene to be computed quickly.
Successive reflections use proportionally fewer samples, which speeds the
process and provides a natural limit to recursion. The technique can also
diffuse transmission and illumination from large area sources, such as the sky.

\R Sillion, Francois, and Claude Pucch. ``A General Two-Pass
Method for Integrating Specular and Diffuse Reflection.'' \B SIGGRAPH
'89\}, p. 335-344.

\A
We analyze some recent approaches to the global illumination problem by
introducing the corresponding \E reflection operators\}, and we demonstrate
the advantages of a two-pass method. A generalization of this system introduced
by Wallace \E et al\}.\ at Siggraph '87 to integrate diffuse as well as
specular reflection is presented. It is based on the calculation of \E
extended form-factors\}, which allows arbitrary geometries to be used in the
scene description, as well as refraction effects. We also present a new
sampling method for the calculation of form-factors, which is an alternative to
the \E hemi-cube\} technique introduced by Cohen and Greenberg for radiosity
calculations. This method is particularly well suited to the extended
form-factors calculation. The problem of interactive display of the picture
being created is also addressed by using hardware-assisted projections and image
composition to recreate a complete specular view of the scene.

\R Wallace, John R., Kells A. Elmquist, and Eric A. Haines. ``A
Ray Tracing Algorithm for Progressive Radiosity.'' \B SIGGRAPH '89\}, p.
315-324.

\A
A new method for computing form-factors within a progressive radiosity approach
is presented. Previously, the progressive radiosity approach has depended on
the use of the hemi-cube algorithm to determine form-factors. However, sampling
problems inherent in the hemi-cube algorithm limit its usefulness for complex
images. A more robust approach is described in which ray tracing is used to
perform the numerical integration of the form-factor equation. The approach is
tailored to provide good, approximate results for a low number of rays, while
still providing a smooth continuum of increasing accuracy for higher number of
rays. Quantitative comparisons between analytically derived form-factors and
ray traced form-factors are presented.

\R Arvo, James, and David Kirk. ``Particle Transport and Image
Synthesis.'' \B SIGGRAPH '90\}, p. 63-66.

\A
The rendering equation is similar to the linear Boltzmann equation which has
been widely studied in physics and nuclear engineering. Consequently, many of
the powerful techniques which have been developed in these fields can be
applied to problems in image synthesis. In this paper we adapt several
statistical techniques commonly used in neutron transport to stachistic ray
tracing and, more generally, to Monte Carlo solution of the rendering equation.
First, we describe a technique known as \E Russian roulette\} which can be
used to terminate the recursive tracing of rays without introducing statistical
bias. We also examine the practice of creating ray trees in classical ray
tracing in the light of a well-known technique in particle transport known as
\E splitting\}. We show that neither ray trees nor paths as described in
[Kaj86] constitute an optimal sampling plan in themselves and that a hybrid
may be more efficient.

\R Heckbert, Paul S. ``Adaptive Radiosity Textures for Bidirectional Ray
Tracing.'' \B SIGGRAPH '90\}, p. 145-154.

\A
We present a rendering method designed to provide accurate, general simulation
of global illumination for realistic image synthesis. Separating surface
interaction into diffuse plus specular, we compute the specular component on
the fly, as in ray tracing, and store the diffuse component (the radiosity)
for later-reuse, similar to a radiosity algorithm. Radiosities are stored in
\E adaptive radiosity textures (rexes)\} that record the pattern of light and
shadow on every diffuse surface in the scene. They adaptively subdivide
themselves to the appropriate level of detail for the picture being made,
resolving sharp shadow edges automatically.

We use a three-pass, bidirectional ray tracing algorithm that traces rays from
both the lights and the eye. The ``size pass'' records visibility information
on diffuse surfaces; the ``light pass'' progressively traces rays from lights
and bright surfaces to deposit photons on diffuse surfaces to construct the
radiosity textures; and the ``eye pass'' traces rays from the eye, collecting
light from diffuse surfaces to make a picture.
 
\R Hermitage, Shirley A., Terrance L. Huntsberger, and Beverly A. Huntsberger.
``Hypercube Algorithm for Radiosity in a Ray Tracing Environment.'' \B
Proceedings of the 5th Distributed Memory Computing Conference\}, IEEE Society
Press, 1990, p. 206-211.
 
\A
Two different approaches to realistic image synthesis are ray tracing and
radiosity. Each method falls short in their attempts to model global
illumination present in most environments. A more general model includes
the specular and diffuse reflection of both these methods but the combination
requires prohibitive computation.
 
The algorithm presented here extends the standard ray tracing algorithm by
adding diffuse rays, while eliminating unnecessary radiosity calculations. The
data separation used here is based on the heuristic that light rays, as well
as shadow rays intersect objects which are nearby more often than those that
are more distant. Although that heuristic seems sound, its accuracy is being
tested by monitoring the results of processing large number of different
scenes of various complexity.

\R Rushmeier, Holly E., and Kenneth E. Torrance. ``Extending the
Radiosity Method to Include Specularly Reflecting and Translucent Materials.''
\B ACM TOG\}, Vol. 9, \# 1, January 1990, p. 1-27.

\A
An extension to the radiosity method is presented that rigorously accounts for
the presence of a small number of specularly reflecting surfaces in an
otherwise diffuse scene, and for the presence of a small number of specular or
ideal diffuse transmitter. The relationship between the extended method and
earlier radiosity and ray-tracing methods is outlined. It is shown that all
three methods are based on the same general equation of radiative transfer. A
simple superposition of the earlier radiosity and ray-tracing methods in order
to account for specular behavior is shown to be physically inconsistent, as
the methods are based on different assumptions. Specular behavior is correctly
included in the present method. The extended radiosity method and example
images are presented.

\R Le Saec, Betrand, and Christophe Schlick. ``A Progressive Ray-Tracing-Based
Radiosity with General Reflectance Functions.'' Technical Report \#90-17,
Laboratoire Bordelais de Recherche en Informatique, Universit\'e de Bordeaux I.
Also appears in Proceedings Eurographics Workshop on Photosimulation, Realism
and Physics in Computer Graphics, June 1990, p. 103-116.

\A
In this paper, we present a progressive and interactive rendering method able
to solve the global illumination problem. Our method, currently under
implementation at LaBRI, in Bordeaux (France), can be considered as an
extension of Wallace's recent paper at the SIGGRAPH '89 conference about a
Progressive Ray-Tracing-based Radiosity. The method is intended to remove the
purely diffuse phenomena limitations that exists in Wallace's paper and allow
the use of general reflectance functions.

\R Shirley, Peter. ``A Ray Tracing Method for Illumination Calculation in
Diffuse-Specular Scenes.'' \B Proceedings of Graphics Interface '90\},
p. 205-212.
 
\A
Several ways of improving the realism of the results of traditional ray
tracing are presented. The essential physical quantities of spectral radiant
power and spectral radiance and their use in lighting calculations are
discussed. Global illumination terms are derived by employing illumination
ray tracing for calculation of quickly changing indirect lighting components,
and radiosity ray tracing for slowly changing indirect lighting components.
Direct lighting is calculated during the viewing phase allowing the use of
bump maps. Finally, a method is introduced that reduces the total number of
shadow rays to no more than the total number of viewing rays for a given
picture.

\R Chen, Shenchang Eric, Holly E. Rushmeier, Gavin Miller, and Douglass Turner.
``A Progressive Multi-Pass Method for Global Illumination.'' \B SIGGRAPH '91\},
p. 165-174.

\A
A new progressive global illumination method is presented which produces
approximate images quickly, and then continues to systematically produce more
accurate images. The method combines the existing methods of progressive
refinement radiosity, Monte Carlo path tracing and light ray tracing. The
method does not place any limitation on surface properties such as ideal
Lambertian or mirror-like. To increase efficiency and accuracy, the new
concepts of light source reclassification, caustics reconstruction, Monte Carlo
path tracing with a radiosity preprocess and an interruptible radiosity
solution are introduced. The method presents the user with most useful
information about the scene as early as possible by reorganizing the method
into a radiosity pass, a high frequency refinement pass and a low frequency
refinement pass. The implementation of the method is demonstrated, and sample
images are presented.

\R Haines, Eric A., and John R. Wallace. ``Shaft Culling for Efficient
Ray-Traced Radiosity.'' \B Second Eurographics Workshop on Rendering\}, May
1991, p. ?.

\A
In radiosity algorithms, much time is spent computing visibility between two
surfaces. One approach to approximating this visibility is to use ray cating
methods. A new algorithm is presented which takes advantage of object
coherency when using ray casting for radiosity. An efficient method is
presented to form a volume between the emitter and receiver, and then
generate a candidate lst of items partially or wholly within the volume. Using
this list, ray casting is performed to determine the amount of visibility
between surfaces. Statistics are presented showing the decrease in overall
computation time compared to a traditional ray casting technique.

\R Hanrahan, Pat, Larry Aupperle, and David Salzman. ``A Rapid Hierarchical
Radiosity Algorithm.'' \B SIGGRAPH '91\}, p. 197-206.

\A
This paper presents a rapid hierarchical radiosity algorithm for illuminating
scenes containing large polygonal patches. The algorithm constructs a
hierarchical representation of the form factor matrix by adaptively subdividing
patches into subpatches according to a user-supplied error bound. The algorithm
guarantees that all form factors are calculated to the same precision, removing
many common image artifacts due to in accurate form factors. More importantly,
the algorithm decomposes the form factor matrix into at most \$O(n)\$ blocks
(where n is the number of elements). Previous radiosity algorithms represented
the element-to-element transport interactions with $n\^2\}$ form factors.
Visibility algorithms are given that work well with this approach. Standard
techniques for shooting and gathering can be used with the hierarchical
representation to solve for equilibrium radiosities, but we also discuss using
a brightness-weighted error criteria, in conjuction with multigridding, to even
more rapidly progressively refine the image.

\R Pueyo, Xavier. ``Diffuse Interreflections. Techniques for Form-Factor
Computation: A Survey.'' \B The Visual Computer\}, Vol. 7, July 1991,
p. 200-209.
 
\A
The purpose of this survey paper is to present a characterization of the
techniques proposed up to now to model different interreflections. Basic
approaches are presented as well as the evolution of implementation
strategies. In the conclusions, open problems are enumerated.

\s Wave Theory

\R Moravec, Hans P. ``3D Graphics and the Wave Theory.'' \B SIGGRAPH '81\},
p. 289-296.

\A
A continuing trend in computer representation of three dimensional synthetic
scenes is the ever more accurate modelling of complex illumination effects.
Such effects provide cues necessary for a convincing illusion of reality. The
best current methods simulate multiple specular reflections and refractions,
but handle at most one scattering bounce per light ray. They cannot accurately
simulate diffuse light sources, nor indirect lighting via scattering media,
without prohibitive increases in the already very large computing costs.

Conventional methods depend implicitly on a \E particle\} model; light
propagates in straight and conceptually infinitely thin rays. This paper
argues that a \E wave\} model has important computational advantages for the
complex situations. In this approach, light is represented by wave fronts
which are stored as two dimensional arrays of complex numbers.

The propagation of such a front can be simulated by a linear transform.
Several advantages accrue. Propagations in a direction orthogonal to the plane
of a front are convolutions which can be done by FFT in \$O(n \l n)\$ time
rather than the \$n\^2\}\$ time for a similar operation using rays. A typical
speedup is about 10,000. The wavelength of the illumination sets a resolution
limit which prevents unnecessary computation of elements smaller than will be
visible. The generated wavefronts contain multiplicities of views of the
scene, which can be individually extracted by passing them through different
simulated lenses. Lastly the wavefront calculations are ideally suited for
implementation on available array processors, which provide more cost
effective calculation for this task than general purpose computers.

The wave method eliminates the aliasing problem; the wavefronts are inherently
spatially filtered, but substitutes diffraction effects and depth of focus
limitations in its stead.

\R Wolff, Lawrence B., and David J. Kurlander. ``Ray Tracing with Polarization
Parameters.'' \B IEEE CG\&A\}, Novemer 1990, p. 44-55.

\A
We demonstrate that incorporating polarization parameters into the lighting
model can enhance the physical realism of images rendered with a ray tracer.
Polarization effects can be importantin certain scenes, and the difference in
rendering even simple scenes with and without proper treatment of polarization
can be rather striking. All light waves possess a state of polarization, which
changes almost every time light reflects off a material surface. A single
reflection partially polarizes and may even completely polarize previously
unpolarized light. Polarization influences the rendering of a scene because the
reflected radiant intensity depends largely on the incident light wave's
polarization state.

We have incorporated Emil Wolf's coherence matrix formalism for polarization
into the Torrance-Sparrow reflectance model. This combination enables elegant
quantitative derivations of the altered polarization state of light upon
reflection in a ray tracer. Comparisons of identicala scenes rendered with a
conventional ray tracer and our ray tracer. Incorporating a polarization model
show that our method renders specular interobject reflections more accurately
with respect to reflected radiance and color.

\S Yet-To-Be-Classified Papers

\R Chattopadhyay, Sudeb, and Akira Fujimoto. ``Bi-Directional Ray
Tracing.'' \B Computer Graphics 1987 - Proceedings of CG International '87\},
Tosiyasu L. Kunii (ed.), Springer Verlag, p. 335-343.

\A
Ray tracing is one of the most powerful techniques used in computer graphics.
Although ray tracing techniques can take into account the effects of
reflection from neighboring surfaces, it has hitherto been impossible to
completely account for the ambient or global illumination arising out of
complex interreflections in an environment because of limitations of the
number of rays that could be fired to render the scene in a span of time
reasonable from the point of view of practical use. In this paper, a fast
method based on positive and conventional (reverse) ray tracing techniques to
take into account the complex interreflections in a scene is proposed. While
the directionality of the illumination intensity from the secondary sources
are not taken into account the description is viewer independent. Unlike the
radiosity approach the present method can treat open systems since no
limitations due to conservation of energy is imposed. The method is more
efficient and computationally inexpensive.

\R Wyvill, Geoff, Alistair Ward, and Tim Brown. ``Sketches by Ray Tracing.''
\B Computer Graphics 1987 - Proceedings of CG International '87\}, Tosiyasu
L. Kunii (ed.), Springer-Verlag, p. 315-333.

\A
Ray Tracing can show shadows and the effects of reflection and refraction. For
this reason it is superior to other methods of rendering. It also enables us
to make pictures directly from CSG models in a very general way which avoids
the complication of finding intersections between primitive objects.

For many applications, we do not need the realism of the ray tracer, but we
still value its generality. By using a sparse grid of rays and by following
edges in the picture plane, most of the information can be extracted from the
model at greatly reduced cost.

\R Youssef, Saul. ``Generalized Ray Tracing and Point Location.'' Technical
Report FSU-SCI-88-72, Supercomputer Computations Research Institute, 1988.

\A
The ray tracing and point location problems are considered for continuous rays
in \$d\$-dimensional euclidean space. Geometric situations in \$\r\^d\}\$ are
defined by combining any of a wide variety of primitive volumes, including
primitive volumes defined by other ray tracing algorithms. Primitive volumes
may be combined in a style similar to solid modeling with constructive solid
geometry. An algorithm for ray tracing is found and proven correct. The
algorithm is particularly well suited to situations where many similar volumes
need to be represented. The same algorithm solves the point location problem as
a special case. Implementation details are given.

\R Amanatides, John, and Don P. Mitchell. ``Some Regularization Problems in
Ray Tracing.'' \B Proceedings of Graphics Interface '90\}, p. 221-228.

\A
Ray tracers that render CSG models should consider issues of regularization and
numerical accuracy. The special case of rays originating on surfaces (shadow
probes, reflections, and refractions) present a regularization problem that is
significant--even in ray tracers which are not explicitly based on the CSG
scheme. An analysis of this problem yields a better solution than the epsilon
tests incorporated in most ray tracers.

\R Lamparter, Bernd, Heinrich M\"uller, J\"org Winckler. ``The Ray-z-Buffer--An
Approach for Ray Tracing Arbitrarily Large Scenes.'' Universit\"at Freiburg
Institut f\"ur Informatik, April 1990.

\A
This paper presents the ray-z-buffer as part of an alternative strategy of ray
tracing called breadth first ray tracing. Breadth first ray tracing differs
from usual pixel-wise rendering in tracing whole generations of rays together.
This means that first all rays of view are treated, next the set of reflecting
and refracting rays, then the reflecting and refracting rays caused by them,
and so on. The calculation of intersections for a generation of rays uses the
the ray-z-buffer algorithm. The ray-z-buffer algorithm generalizes the
well-known z-buffer algorithm. Like the z-buffer algorithm the ray-z-buffer
algorithm allows rendering of scenes with an unbounded number of primitives.
An implementation based on nested adaptive quadtrees is presented. Analysis and
measuring show the rendering time increases sublinearly in the resolution of the
image, and increasing linearly in the number of primitives. The main memory
required only depends on the resolution of the image, in about linear manner.

\R Hofmann, Georg Rainer. ``Who Invented Ray Tracing?'' \B The Visual
Computer\}, Vol. 6, 1990, p. 120-124.

\A
We provide some remarks on the very early developments of the
visualization technique conducted during the European Renaissance. It is shown
that the basic principle of ray tracing was already presented by Albrecht
D\"urer (1471-1528) in 1525. This article is intended to be of common
interest; it is not a scientific report.

\R \.I\,sler, Veysi, Cevdet Aykanat, and B\"ulent \"Ozg\"u\,c. ``Subdivision
of 3D Space Based on the Graph Partitioning for Parallel Ray Tracing.''
\B Second Eurographics Workshop on Rendering\}, May 1991, p. ?.

\A
An approach for parallel ray tracing is to subdivide the 3D space into
rectangular volumes and assign the computations and the object descriptions in
each volume to a different processor. The subdivision process is thus critical
in reducing the interprocessor communication overhead, and maintaining the load
balance among processors of a multicomputer. In this paper, after a brief
overview of parallel ray tracing, a heuristic algorithm is propsed to subdivide
the 3D space by converting the problem into a graph partitioning problem for
parallel ray tracing on multicomputers. The proposed algorithm tries to
minimize the communication cost while maintaining a load balance among
processors.

\R Lange, Brigitta. ``The Simulation of Radiant Light Transfer with Stochastic
Ray-Tracing.'' \B Second Eurographics Workshop on Rendering\}, May 1991, p. ?.

\A
In the following, an enhanced stochastic ray-tracing method will be presented,
that models the radiant light transfer in order to generate photorealistic
images. The approach is based on the ``rendering equation'', an alternative
approximation to the Maxwell equations. By invoking a probabilistic model of
the radiation exchange process and applying Monte Carlo sampling techniques to
sole the rendering equation, it is possible to utilize an already existing
ray-tracer by modifying it. A view-dependent solution is presented that can
handle diffuse and specular reflections and that can also model the
illumination from area sources of circular shape. Moreover, a weighting factor
for the sampled intensities has been developed that provides not only a correct
treatment of the intensity variations of illumination in dependence of the
distance, but can also be used to accelerate the image generation process by
controlling the number of paths to be traced for each pixel individually as
required by the particular lighting situation for the corresponding point in
the scene, without producing a loss in accuracy.

\R Schlick, Christophe. ``An Adaptive Sampling Technique for Multidimensional
Integration by Ray-Tracing.'' \B Second Eurographics Workshop on Rendering\},
May 1991, p. ?.

\A
[No abstract. The following is taken from Introduction]

Creating pictures with photorealistic effects (diffuse and specular
interreflection, shadow and penumbra, depth of field, motion blur...) implies
to solve multidimensional integral equations -- so-called \E rendering
equations\}. Ray-tracing is a well-known powerful and flexible tool that has
been successfully for solving these rendering equations, either in an
image-oriented process (distributed ray-tracing, path tracing) or in a
scene-oriented one (deterministic radiosity, stochastic radiosity).

Unfortunately, ray-tracing is a point sampling technique and thus is prone to
aliasing artifacts. Moreover, because the signal to sample is generally not
bounded in the frequency domain, aliasing cannot be totally eliminated but
only reduced. Antialiasing methods that have been proposed for ray-tracing
usually combine an increase of the sampling rate and a strategy for samples
selection. But the most powerful of them remain expensive because of the great
number of rays needed; thus some improvements have to be found to reduce that
number.

A classical technique -- adaptive sampling -- consists in sending more or less
rays, according to the way the signal varies. The drawback of the existing
adaptive sampling methods for multidimensional integration by ray-tracing
(MIRT) is that they \E don't have all the wanted characteristics\} irregular
and importance sampling, uncorrelation between the dimensions to sample,
complete stratification at each refinement level, efficient reconstruction).
In this paper, an adaptive sampling technique is presented, that fulfills all
these conditions and can be totally implemented with look-up tables for
efficiency considerations.
 
\R Coquillart, Sabine, and Michel Gangnet. ``Shaded Display of Digital Maps.''
\B IEEE CG\&A\}, July 1984, p. 35-42.
 
\A
The computer graphics display of shaded images of terrain can take advantage
of the geometric properties of the data. Altitudes given on regular
rectangular grids are readily available from digital maps. Several authors
have addressed the task of displaying such data. Line-drawing methods are
well-known, and there have been two new contributions in the recent
literature.
 
Two problems arise in displaying the perspective view of a terrain. The first
is to choose an interpolation surface; the second is to eliminate hidden
surfaces.

\R Chin, J. H., T. D. Panczak, and L. Fried. ``Finite Element and Raytracing in
Coupled Thermal Problems.'' ???, p. 683-701.

\A 
[Taken from Summary.]
 
Thermal analysis for complex systems, such as spacecraft, where thermal
radiation plays a significant part, traditionally uses radiation exchange
factors based on \E isothermal\} regions of finite extent. A procedure is
described which removes this restriction, and improves the analytical results,
by combining a Monte Carlo raytracing procedure with a finite element 
approach. This permits the solution of the thermal analytical problem in a
consistent manner, wherein the generally nonisothermal character of a system
is modeled more closely than in the traditional procedures. The algorithm
computes the emitting ray energy from an emitter element, allows for multiple
reflections and absorptions, and distributes the hitting ray energy in a
manner \E consistent\} with the finite element approach. Radiation exchange
factors between \E nodal points\}, rather than \E elements\}, are obtained;
this permits more accurate computation of the radiative energy exchange
between the various nonisothermal surfaces than can be obtained by the
isothermal elemental surface assumption. The derivation of the algorithm is
described. Simple numerical examples are given to demonstrate the usefulness
of this consistent modeling approach. A simple engineering model is then used
to illustrate a finite-element raytracing analysis of coupled thermal
problems.

\t

\iAKI91\} Akimoto, Taka-aki, Kenji Mase, and Yasuhito Suenaga. ``Pixel Selected
Ray Tracing.'' \B IEEE CG\&A\}, July 1991, p. 14-22. Revision of same paper in
\B Proceedings of Eurographics '89\}, W. Hansmann, F. R. A. Hopgood and
W. Strasser (eds.), p. 39-50, 542. [Undersampling]

\iAKT87\} Aktkin, Phil, Steve Ghee, and Jamie Packer. ``Transputer Architectures
for Ray Tracing.'' \B Proceedings of Computer Graphics '87\}, Online
Publications, 1987, p. 157-172. [Transputer Implementations]

\iAMA84a\} Amanatides, John. ``Ray Tracing with Cones.'' \B SIGGRAPH '84\},
p. 129-135. A summary of the same paper appears in \B Proceedings of Graphics
Interface '84\}, p. 97-98. [Antialiasing]

\iAMA84b\} Amanatides, John, and Alain Fournier. ``Ray Casting Using Divide and
Conquer in Screen Space.'' \B International Conference on Engineering and
Computer Graphics\}, August 1984, p. 290-296. [Undersampling]

\iAMA87b\} Amanatides, John, and Andrew Woo. ``A Fast Voxel Traversal Algorithm
for Ray Tracing.'' \B Proceedings of Eurographics '87\}, Guy Mar\'echal (ed.),
p. 3-10. [Uniform Subdivision]

\iAMA87a\} Amanatides, John. ``Realism in Computer Graphics: A Survey.''
\B IEEE CG\&A\}, January 1987, p. 44-56. [The Ray Tracing Technique]

\iAMA90\} Amanatides, John, and Don P. Mitchell. ``Some Regularization
Problems in Ray Tracing.'' \B Proceedings of Graphics Interface '90\},
p. 221-228.
 
\iAPP68\} Appel, Arthur. ``Some Techniques for Shading Machine Renderings
of Solids.'' \B AFIPS Spring Joint Computer Conference\}, 1968, p. 37-45.
[The Ray Tracing Technique]

\iARG88\} Argence, J. ``Antialiasing for Ray Tracing Using CSG Modeling.'' \B
New Trends in Computer Graphics, Proceedings of CG International '88\}, Nadia
Magnenat-Thalmann and Daniel Thalmann (eds.), Springer-Verlag, p. 199-208.
[Antialiasing]

\iARN87\} Arnaldi, Bruno, Thierry Priol, and Kadi Bouatouch. ``A New Space
Subdivision Method for Ray Tracing CSG Modelled Scenes.'' \B The Visual
Computer\}, Vol. 3, 1987, p. 98-108. [CSG]
 
\iARV87\} Arvo, James, and David Kirk. ``Fast Ray Tracing by Ray
Classification.'' \B SIGGRAPH '87\}, p. 55-64. Also appears in \B Tutorial:
Computer Graphics: Image Synthesis\}, Kenneth I. Joy, Charles W. Grant, Nelson
L. Max, and Lansing Hatfield (eds.), Computer Society Press, Washington, 1988,
p. 196-205. [Uniform Subdivision]

\iARV90\} Arvo, James, and David Kirk. ``Particle Transport and Image
Synthesis.'' \B SIGGRAPH '90\}, p. 63-66. [Radiosity]

\iBAD90a\} Badouel, Didier, and Thierry Priol. ``An Efficient Parallel Ray
Tracing Scheme for Highly Parallel Architectures.'' \B Fifth Eurographics
Workshop on Graphics Hardware\}, 1990, p. ?. [Hypercube Implementations]

\iBAD90b\} Badouel, Didier, Kadi Bouatouch, and Thierry Priol. ``Ray Tracing on
Distributed Memory Parallel Computers: Strategies for Distributing Computations
and Data.'' \B SIGGRAPH '90 Parallel Algorithms and Architecture for 3D Image
Generation Course Notes\}. [MIMD Architectures]
 
\iBAD88\} Badt, Sig, Jr. ``Two Algorithms for Taking Advantage of Temporal
Coherence in Ray Tracing.'' \B The Visual Computer\}, Vol. 4, 1988, p. 123-132.
[Temporal Coherence]
 
\iBAR86\} Barr, Alan H. ``Ray Tracing Deformed Surfaces.'' \B SIGGRAPH '86\},
p. 287-296. [Explicit Representations]
 
\iBAR90\} Barrett, Martin L. ``A Load Balancing Experiment for Parallel Ray
Tracing.'' \B Proceedings of Ausgraph '90\}, p. 145-155. [MIMD Architectures]

\iBAR89\} Barton, E. ``Data Concurrency on the Meiko Computing Surface.''
\B Parallel Processing for Computer Vision and Display\}, P. M. Dew,
R. A. Earnshaw, and T. R. Heywood (eds.), Addison-Wesley Publishing Company,
Reading, Massachusetts, 1989, p. 402-407. [MIMD Architectures]
 
\iBER90\} Berger, Marc, Terry Trout, and Nancy Levit. ``Ray Tracing Mirages.''
\B IEEE CG\&A\}, May 1990, p. 36-41. [Natural Phenomena]

\iBID90\} Bidasaria, H. B. ``Ray Tracing Surfaces of Revolution Using a
Simplified Strip-Tree Method.'' \B Proceedings of the 1990 ACM Eighteenth
Annual Computer Science Conference\}, 1990, p. 427. Only abstract appears.
[Objects Defined by Sweeps and Revolutions] *

\iBOUA87\} Bouatouch, Kadi, M. O. Madani, Thierry Priol, and Bruno Arnaldi. ``A
New Algorithm of Space Tracing Using a CSG Model.'' \B Proceedings of
Eurographics '87\}, Guy Mar\'echal (ed.), p. 65-78. [CSG]

\iBOUA88a\} Bouatouch, K., and T. Priol. ``Parallel Space Tracing: An
Experience on an iPSC Hypercube.'' \B New Trends in Computer Graphics,
Proceedings of CG International '88\}, Nadia Magnenat-Thalmann and Daniel
Thalmann (eds.), Springer-Verlag, p. 170-188. Also appears as ``Experimenting
with a Parallel Ray-Tracing Algorithm on a Hypercube Machine'' in \B
Proceedings of Eurographics '88\}, David A. Duce and Pierre Jancene (eds.),
p. 243-259. Each paper contains a few details that the other does not.
[Hypercube Implementations]

\iBOUA88b\} Bouatouch, Kadi. ``Theoretical Developments on Polygonal
Approximation of Parametric Surfaces for Ray Tracing.'' \B Computer Graphics
Forum\}, Vol. 7, 1988, p. 257-264. [Explicit Representations]

\iBOUA89\} Bouatouch, Kadi, Yannick Saouter, and Jean Charles Candela. ``A
VLSI Chip for Ray Tracing Bicubic Patches.'' \B Proceedings of Eurographics
'89\}, W. Hansmann, F. R. A. Hopgood and W. Strasser (eds.), p. 107-124.
[Special Purpose Hardware]
 
\iBOUV85a\} Bouville, Christian. ``Bounding Ellipsoids for Ray-Fractal
Intersection.'' \B SIGGRAPH '85\}, p. 45-52. [Procedurally Defined Objects]

\iBOUV85b\} Bouville, Christian, R. Brusq, J. L. Dubois, and I. Marchal.
``Generating High Quality Pictures by Ray-Tracing.'' \B Computer Graphics
Forum\}, 4 (1985), p. 87-99. Also appears in \B Proceedings of Eurographics
'84\}, Ketil B\o and Hugh A. Tucker (eds.), p. 161-177. [Basic Ray Tracing]

\iBOU85c\} Bouville, Christian. ``Image Synthesis Through Ray Tracing.''
\B Banc-Titre\}, March 1985, p. 50-51. [The Ray Tracing Technique]

\iBOUV??\} Bouville, Christian, Jean-Luc Dubois, and Isabelle Marchal. ``A
Space Tracing Method Applied to Polygonal Models.'' Centre Commun d'Etudes de
T\'el\'ediffusion et T\'el\'ecommunications. [Bounding Volumes, Data
Structures, and Object Hierarchies]

\iBOUV88\} Bouville, Christian, J. L. Dubois, I. Marchal, and M. L. Viaud.
``Monte-Carlo Integration Applied to an Illumination Model.'' \B Proceedings of
Eurographics '88\}, p. 483-498. [Lighting Models]

\iBOUV90\} Bouville, Christian, Kadi Bouatouch, Pierre Tellier, and Xavier
Pueyo. ``A Theoretical Analysis of Global Illumination Models.'' \B
Eurographics Workshop on Photosimulation\}, 1990, p. ?. [Lighting Models]

\iBRO84\} Bronsvoort, Willem F., Jarke J. van Wijk, and Frederik W. Jansen.
``Two Methods for Improving the Efficiency of Ray Casting in Solid Modelling.''
\B CAD\}, Vol. 16, \#1, January 1984, p. 51-55. [CSG]
 
\iBRO85\} Bronsvoort, Willem F., and Fopke Klok. ``Ray Tracing Generalized
Cylinders.'' \B ACM TOG\}, Vol. 4, \#4, October 1985, p. 291-303. Revision of
``Ray Tracing Generalized Sweep-Defined Objects,'' 84-36, Deptartment of
Mathematics and Informatics, Delft University of Technology, 1984. [Objects
Defined by Sweeps and Revolutions]

\iBRO87\} Bronsvoort, Willem F. Corrigendum to ``Ray Tracing Generalized
Cylinders.'' \B ACM TOG\}, Vol. 6, \#3, July 1987, p. 238-239. [Objects Defined
by Sweeps and Revolutions]
 
\iBRO89\} Bronsvoort, Willem F., Peter R. van Nieuwenhuizen, and Frits H. Post.
``Display of Profiled Sweep Objects.'' \B The Visual Computer\}, Vol. 5, 1989,
p. 147-157. [Objects Defined by Sweeps and Revolutions]
 
\iBRO90\} Bronsvoort, Willem F. \B Direct Display Algorithms for Solid
Modelling\}, Delft University Press, Delft University of Technology, Ph.D.
Thesis, 1990. [Objects Defined by Sweeps and Revolutions]

\iBRO91\} Brown, William Todd. ``Filtering and Adaptive Supersampling for Ray
Traced Rendering,'' Report No. UIUCDCS-R-91-1657, Department of Computer
Science, University of Illinois at Urbana-Champaign, January 1991.
[Antialiasing]

\iBU89\} Bu, Jichun, and Ed F. Deprettere. ``A VLSI System Architecture for
High-Speed Radiative Transfer 3D Image Synthesis.'' \B The Visual Computer\},
Vol. 5, 1989, p. 121-133. Revision of same paper in \B Proceedings of
Eurographics '87\}, Guy Mar\'echal (ed.), p. 221-234. [MIMD Architectures]

\iBUR89a\} Burger, Peter, and Duncan Gillies. \B Interactive Computer Graphics:
Functional, Procedural, and Device-Level Methods\}. Addison-Wesley Publishing
Company, Reading, Massachusetts, 1989. [Textbooks and Other Sources]
 
\iBUR89b\} Burger, Peter, and Duncan Gilles. ``Rapid Ray Tracing of General
Surfaces of Revolution.'' \B New Advances in Computer Graphics, Proceedings of
CG International '89\}, R. A. Earnshaw and B. Wyvill (eds.), p. 523-532.
[Objects Defined by Sweeps and Revolutions]

\iCAR90\} Carter, Michael, and Keith Teague. ``Distributed Object Database Ray
Tracing on the Intel iPSC/2 Hypercube.'' \B Proceedings of the 5th Distributed
Memory Computing Conference\}, IEEE Society Press, 1990, p. 217-222. [Hypercube
Implementations]

\iCAS89\} Caspary, Elisha, and Isaac D. Scherson. ``A Self-Balanced Parallel
Ray-Tracing Algorithm.'' \B Parallel Processing for Computer Vision and
Display\}, P. M. Dew, R. A. Earnshaw, and T. R. Heywood (eds.), Addison-Wesley
Publishing Company, Reading, Massachusetts, 1989, p. 408-419. [MIMD
Architectures]

\iCAU88\} Caubet, R., Y. Duthen, and V. Gaildrat. ``VOXAR: A Tridimensional
Architecture for Fast Realistic Image Synthesis.'' \B New Trends in Computer
Graphics, Proceedings of CG International '88\}, Nadia Magnenat-Thalmann and
Daniel Thalmann (eds.), Springer-Verlag, p. 135-149. [MIMD Architectures]

\iCHA89\} Chalmers, M. ``On the Design and Implementation of a Multiprocessor
Ray Tracer.'' \B Parallel Processing for Computer Vision and Display\},
P. M. Dew, R. A. Earnshaw, and T. R. Heywood (eds.), Addison-Wesley Publishing
Company, Reading, Massachusetts, 1989, p. 420-430. [MIMD Architectures]

\iCHA90\} Charney, Mark J., and Isaac D. Scherson. ``Efficient Traversal of
Well-Behaved Hierarchicial Trees of Extents for Ray-Tracing Complex Scenes.''
\B The Visual Computer\}, Vol. 6, 1990, p. 167-178. [Bounding Volumes, Data
Structures, and Object Hierarchies]

\iCHA87\} Chattopadhyay, Sudeb, and Akira Fujimoto. ``Bi-Directional Ray
Tracing.'' \B Computer Graphics 1987 - Proceedings of CG International '87\},
Tosiyasu L. Kunii (ed.), Springer Verlag, p. 335-343.

\iCHE91\} Chen, Shenchang Eric, Holly E. Rushmeier, Gavin Miller, and Douglass
Turner. ``A Progressive Multi-Pass Method for Global Illumination.'' \B
SIGGRAPH '91\}, p. 165-174. [Radiosity]

\iCHI??\} Chin, J. H., T. D. Panczak, and L. Fried. ``Finite Element and
Raytracing in Coupled Thermal Problems.'' ???, p. 683-701.
[Yet-To-Be-Classified]
 
\iCLE86\} Cleary, John G., Brian Wyvill, Graham M. Birtwistle, and Reddy Vatti.
``Multiprocessor Ray Tracing.'' \B Computer Graphics Forum\}, Vol. 5, 1986,
p. 3-12. Revision of the technical report 83/128/17, Computer Science
Department, University of Calgary, October 1983. [MIMD Architectures]

\iCLE??\} Cleary, John G., Brian Wyvill, Geoff Wyvill. ``Ray Tracing in
Calgary and Otago.'' Research Report No. ??/???/??, Computer Science
Department, University of Calgary. [Image Synthesis Systems]
 
\iCLE88\} Cleary, John G., and Geoff Wyvill. ``Analysis of an Algorithm for
Fast Ray Tracing Using Uniform Space Subdivision.'' \B The Visual Computer\},
Vol. 4, 1988, p. 65-83. [Uniform Subdivision]
 
\iCOO84\} Cook, Robert L., Thomas Porter, and Loren Carpenter. ``Distributed
Ray Tracing.'' \B SIGGRAPH '84\}, p. 137-145. Also appears in \B Tutorial:
Computer Graphics: Image Synthesis\}, Kenneth I. Joy, Charles W. Grant, Nelson
L. Max, and Lansing Hatfield (eds.), Computer Society Press, Washington, 1988,
p. 139-147. [Other Phenomena]
 
\iCOO88\} Cook, Robert L. ``Stochastic Sampling in Computer Graphics.''
\B Tutorial: Computer Graphics: Image Synthesis\}, Kenneth I. Joy, Charles W.
Grant, Nelson L. Max, and Lansing Hatfield (eds.), Computer Society Press,
Washington, 1988, p. 283-304. Also appears in \B ACM TOG\}, Vol. 5, \#1,
January 1986, p. 51-72. [Antialiasing]
 
\iCOQ84\} Coquillart, Sabine, and Michel Gangnet. ``Shaded Display of Digital
Maps.'' \B IEEE CG\&A\}, July 1984, p. 35-42. [Yet-To-Be-Classified]

\iCOQ85\} Coquillart, Sabine. ``An Improvement of the Ray-Tracing Algorithm.''
\B Proceedings of Eurographics '85\}, Carlo E. Vandoni (ed.), p. 77-88.
[Bounding Volumes, Data Structures, and Object Hierarchies]

\iCOR85\} Cordonnier, E., C. Bouville, J. L. Dubois, and I. Marchal. ``Creating
CSG Modelled Pictures for Ray-Casting Display.'' \B Proceedings of Eurographics
'85\}, Carlo E. Vandoni (ed.), p. 171-182. [CSG]

\iCRO88a\} Crow, Franklin C. ``Parallelism in Rendering Algorithms.'' \B
Graphics Interface '88\}, p. 87-96. [MIMD Architectures]

\iCRO88b\} Crow, F. C., G. Demos, J. Hardy, J. McLaughlin, and K. Sims. ``3D
Image Synthesis on the Connection Machine.'' \B Parallel Processing for
Computer Vision and Display\}, P. M. Dew, R. A. Earnshaw, and T. R. Heywood
(eds.), Addison-Wesley Publishing Company, Reading, Massachusetts, 1989,
p. 254-269. [MIMD Architectures]

\iCYC89\} Cychosz, Joseph M. ``Efficient Generation of Sampling Jitter
Using Look-up Tables.'' Purdue CADLAB Technical Report No. JC-05, Purdue
University, 1989. [Antialiasing]

\iCYC90\} Cychosz, Joseph M. ``Intersecting a Ray with an Elliptical Torus.''
Purdue CADLAB Technical Report No. JC-07, Purdue University CADLAB, October 29,
1990. [Implicit Representations]
 
\iDAD85\} Dadoun, N., D. G. Kirkpatrick, and J. P. Walsh. ``The Geometry of
Beam Tracing.'' \B ACM Symposium on Computational Geometry\}, 1985, p. 55-61.
[Spatial Coherence]

\iDAV82\} Davis, Jonathan Earl. \B Recursive Ray Tracing for the Realistic
Display of Solid Models\}, M.S.M.E. Thesis, Purdue University, May 1982.
[The Ray Tracing Technique]
 
\iDEF87\} Defend, Daniel Evan. ``Parallel Ray Tracing in a
Vector--Multiprocessing Environment.'' CSRD Rpt. No. 677, Center for
Supercomputing Research and Development, University of Illinois, September,
1987. [MIMD Architectures]

\iDEG84\} Deguchi, Hiroshi, Hitoshi Nishimura, Hiroshi Yoshimura, Toru Kawata,
Isao Shirakawa, and Koichi Omura. ``A Parallel Processing Scheme for
Three-Dimensional Image Generation.'' \B International Symposium on Circuits
and Systems '84\}, Vol. 3, p. 1285-1288. [MIMD Architectures]

\iDEG86\} Deguchi, Hiroshi, Isao Shirakawa, Koichi Omura, Masato Nishida,
Hitoshi Nishimura, Toru Kawata. ``A Tree-Structured Parallel Processing System
for Image Generation by Ray Tracing.'' \B Systems and Computers in Japan\},
Vol. 17, \#12, 1986, p. 51-62. Translated from \B Denshi Tsushin Gakkai
Ronbunshi\}, Vol. 69-D, \#2, Feb. 1986, p. 170-179. [MIMD Architectures]

\iDEL88\} Delany, Hubert C. ``Ray Tracing on a Connection Machine.'' Technical
Report \#VZ88-3, Thinking Machines, April 1988. [Hypercube Implementations]

\iDEV89a\} Devillers, Olivier. ``The Macro-regions: an Efficient Space
Subdivision Structure for Ray Tracing.'' \B Proceedings of Eurographics '89\},
W. Hansmann, F. R. A. Hopgood and W. Strasser (eds.), p. 27-39, 541. Revision
of Technical Report 88-13, Laboratoire d'Informatique de l'Ecole Normale
Sup\'erieure, Paris, France, November 1988. [Nonuniform Subdivision]

\iDEV89b\} Devillers, Olivier. ``Tools to Study the Efficiency of Space
Subdivision Structures for Ray Tracing.'' \B Proceedings of PIXIM '89\},
p. 467-481. [Nonuniform Subdivision]

\iDIA91\} Dias, Maria Lurdes. ``Ray Tracing Interference Color.'' \B IEEE
CG\&A\}, March 1991, p. 54-60. [Natural Phenomena]

\iDIJ89\} van Dijk, C. G. C. \B Ray Tracing Profiled Generalized Cylinders\},
Masters Thesis, Delft University Press, Delft University of Technology, 1989.
[Objects Defined by Sweeps and Revolutions]
 
\iDIP84\} Dipp\'e, Mark, and John Swensen. ``An Adaptive Subdivision Algorithm
and Parallel Architecture for Realistic Image Synthesis.'' \B SIGGRAPH '84\},
p. 149-158. Also appears in \B Tutorial: Computer Graphics Hardware: Image
Generation and Display\}, Hassan K. Reghbati and Anson Y. C. Lee (eds.),
Computer Society Press, Washington, 1988, p. 310-319. [MIMD Architectures]
 
\iDIP85\} Dipp\'e, Mark A., and Erling Henry Wold. ``Antialiasing Through
Stochastic Sampling.'' \B SIGGRAPH '85\}, p. 69-78. [Antialiasing]

\iDOR86\} Dorband, John E. ``Ray Tracing on the MPP.'' \B Frontiers of
Massively Parallel Scientific Computation, Proceedings of the 1st Symposium at
Goddard Space Flight Center\}, NASA Conference Publication 2478, 1986,
p. 211-215, 316. [SIMD Architectures]
 
\iEO89\} Eo, K. S., and C. M. Kyung. ``Hybrid Shadow Testing Scheme for Ray
Tracing.'' \B CAD\}, Vol. 21, \#1, January/February 1989, p. 38-48. [Shadow
Testing]
 
\iFIT82\} Fitzhorn, Patrick A. \B Realistic Image Synthesis: A Time
Complexity Analysis of Ray Tracing\}, M.S. Thesis, Colorado State University,
1982. [Testing and Analysis]

\iFIU89\} Fiume, Eugene L. \B The Mathematical Structure of Raster Graphics\},
Academic Press, San Diego, 1989. [Textbooks and Other Sources]
 
\iFOL84\} Foley, J. D., and A. Van Dam. \B Fundamentals of Interactive Computer
Graphics\}. Addison-Wesley Publishing Company, Reading, Massachusetts, 1984.
[Textbooks and Other Sources]
 
\iFUJ86\} Fujimoto, Akira, Takayuki Tanaka, and Kansei Iwata. ``ARTS: 
Accelerated Ray-Tracing System.'' \B IEEE CG\&A\}, April 1986, p. 16-26. Also
appears in \B Tutorial: Computer Graphics: Image Synthesis\}, Kenneth I. Joy,
Charles W. Grant, Nelson L. Max, and Lansing Hatfield (eds.), Computer Society
Press, Washington, 1988, p. 148-158. Revision of ``Accelerated Ray Tracing'' by
Akira Fujimoto and Kansei Iwata in \B Computer Graphics: Visual Technology and
Art, Proceedings of Computer Graphics Tokyo '85\}, Tosiyasu L. Kunii (ed.),
p. 41-65. [Uniform Subdivision]

\iGAR90\} Garrity, Michael P. "Raytracing Irregular Volume Data." \B
Proceedings of the San Diego Workshop on Volume Visualization\}, 1990,
p. 35-40, 110. [Volume Data]
 
\iGAU88\} Gaudet, Severin, Richard Hobson, Pradeep Chilka, and Thomas Calvert.
``Multiprocessor Experiments for High-Speed Ray Tracing.'' \B ACM TOG\},
Vol. 7, \#3, July 1988, p. 151-179. [MIMD Architectures]

\iGER86\} Gervautz, Michael. ``Three Improvements of the Ray Tracing Algorithm
for CSG Trees.'' \B Computers \& Graphics\}, Vol. 10, \#4, 1986, p. 333-339.
[CSG]
 
\iGET89\} Getto, Philip. ``Fast Ray Tracing of Unevaluated Constructive Solid
Geometry Models.'' \B New Advances in Computer Graphics, Proceedings of CG
International '89\}, R. A. Earnshaw and B. Wyvill (eds.), p. 563-578. [CSG]

\iGIG90\} Gigante, Michael. ``Accelerated Ray Tracing Using Non-Uniform
Grids.'' \B Proceedings of Ausgraph '90\}, p. 157-163. [Nonuniform Subdivision]

\iGIG89\} Giger, Christine. ``Ray Tracing Polynomial Tensor Product Surfaces.''
\B Proceedings of Eurographics '89\}, W. Hansmann, F. R. A. Hopgood and
W. Strasser (eds.), p. 125-136, 544. [Explicit Representations]
 
\iGLA84\} Glassner, Andrew S. ``Space Subdivision for Fast Ray Tracing.'' \B
IEEE CG\&A\}, October 1984, p. 15-22. Also appears in \B Tutorial: Computer
Graphics: Image Synthesis\}, Kenneth I. Joy, Charles W. Grant, Nelson L. Max,
and Lansing Hatfield (eds.), Computer Society Press, Washington, 1988,
p. 159-167. [Uniform Subdivision]
 
\iGLA88\} Glassner, Andrew S. ``Spacetime Ray Tracing for Animation.'' \B IEEE
CG\&A\}, March 1988, p. 60-70. [Temporal Coherence]
 
\iGLA89\} Glassner, Andrew S., James Arvo, Robert L. Cook, Eric Haines, Pat
Hanrahan, Paul Heckbert, and David B. Kirk. \B An Introduction to Ray Tracing\}.
Academic Press, San Diego, 1989. [The Ray Tracing Technique]

\iGLA90a\} Glassner, Andrew S. ``Ray Tracing for Realism.'' \B Byte\}, December
1990, p. 263-271. [The Ray Tracing Technique]

\iGLA90b\} Glassner, Andrew S. (ed.). \B Graphics Gems\}, Academic Press, Inc.,
San Diego, 1990. [Textbooks and Other Sources]
 
\iGOL85\} Goldsmith, Jeffrey, and John Salmon. ``A Ray Tracing System for the
Hypercube.'' Caltech Concurrent Computing Memorandum HM-154, 1985. [Hypercube
Implementations]
 
\iGOL87\} Goldsmith, Jeffrey, and John Salmon. ``Automatic Creation of Object
Hierarchies for Ray Tracing.'' \B IEEE CG\&A\}, May 1987, p. 14-20. [Bounding
Volumes, Data Structures, and Object Hierarchies]
 
\iGOL71\} Goldstein, Robert A., and Roger Nagel. ``3-D Visual Simulation.'' \B
Simulation\}, January 1971, p. 25-31. [The Ray Tracing Technique]
 
\iGRE89a\} Green, Stuart A., Derek J. Paddon, and E. Lewis. ``A Parallel
Algorithm and Tree-Based Computer Architecture for Ray-Traced Computer
Graphics.'' \B Parallel Processing for Computer Vision and Display\},
P. M. Dew, R. A. Earnshaw, and T. R. Heywood (eds.), Addison-Wesley Publishing
Company, Reading, Massachusetts, 1989, p. 431-442. [MIMD Architectures]
 
\iGRE89b\} Green, Stuart A., and Derek J. Paddon. ``Exploiting Coherence for
Multiprocessor Ray Tracing.'' \B IEEE CG\&A\}, November 1989, p. 12-26. [MIMD
Architectures]

\iGRE90\} Green, Stuart A., and Derek J. Paddon. ``A Highly Flexible
Multiprocessor Solution for Ray Tracing.'' \B The Visual Computer\}, Vol. 6,
1990, p. 62-73. [MIMD Architectures]

\iGRI89\} Griessmair, Josef, and Werner Purgathofer. ``Deformation of Solids
with Trivariate B-Splines.'' \B Proceedings of Eurographics '89\}, W. Hansmann,
F. R. A. Hopgood and W. Strasser (eds.), p. 137-148, 545. [Explicit
Representations]
 
\iHAI86\} Haines, Eric A., and Donald P. Greenberg. ``The Light Buffer: A
Shadow-Testing Accelerator.'' \B IEEE CG\&A\}, September 1986, p. 6-16.
Contains main points of: \B The Light Buffer: A Ray Tracer Shadow Testing
Accelerator\} by Eric A. Haines, Master's Thesis, Program of Computer Graphics,
1986. [Shadow Testing]

\iHAI87\} Haines, Eric. ``A Proposal for Standard Graphics Environments.'' \B
IEEE CG\&A\}, November 1987, p. 3-5. [Testing and Analysis]

\iHAI88\} Haines, Eric, n\E et al\}. \B Ray Tracing News\}. Electronic
newsletter, 1988-1990, available from erich@eye.com. [Textbooks and Other
Sources]

\iHAI91\} Haines, Eric A., and John R. Wallace. ``Shaft Culling for Efficient
Ray-Traced Radiosity.'' \B Second Eurographics Workshop on Rendering\}, May
1991. [Radiosity]
 
\iHAL83\} Hall, Roy A., and Donald P. Greenberg. ``A Testbed for Realistic
Image Synthesis.'' \B IEEE CG\&A\}, November 1983, p. 10-20. [Image Synthesis
Systems]

\iHAL87\} Hall, Roy A. ``Color Reproduction and Illumination Models.''
\B Techniques for Computer Graphics\}, David F. Rogers and Rae A. Earnshaw
(eds.), Springer-Verlag, 1987, p. 194-238. [Lighting Models]
 
\iHAL89\} Hall, Roy. \B Illumination and Color in Computer Generated
Imagery\}, Springer-Verlag, 1989. [Textbooks and Other Sources]
 
\iHAN83\} Hanrahan, Pat. ``Ray Tracing Algebraic Surfaces.'' \B SIGGRAPH '83\},
p. 83-90. [Implicit Representations]
 
\iHAN86\} Hanrahan, Pat. ``Using Caching and Breadth-First Search to Speed Up
Ray Tracing.'' \B Proceedings of Graphics Interface '86/Vision Interface '86\},
1986, p. 56-61. [Spatial Coherence]

\iHAN91\} Hanrahan, Pat, Larry Aupperle, and David Salzman. ``A Rapid
Hierarchical Radiosity Algorithm.'' \B SIGGRAPH '91\}, p. 197-206. [Radiosity]
 
\iHAR89\} Hart, John C., Daniel J. Sandin, and Louis H. Kauffman. ``Ray Tracing
Deterministic 3-D Fractals.'' \B SIGGRAPH '89\}, p. 289-296. [Procedurally
Defined Objects]

\iHAR91\} Hart, John C., and Thomas A. DeFanti. ``Efficient Antialiased
Rendering of 3-D Linear Fractals.'' \B SIGGRAPH '91\}, p. 91-100. [Procedurally
Defined Objects]
 
\iHAS89\} Hashimoto, Akihiko, Taka-aki Akimoto, Kenji Mase, and Yasuhito
Suenaga. ``Vista Ray-Tracing: High Speed Ray Tracing Using Perspective
Projection Image.'' \B New Advances in Computer Graphics, Proceedings of CG
International '89\}, R. A. Earnshaw and B. Wyvill (eds.), p. 549-561.
[Undersampling]

\iHEB??\} H\'ebert, M.-P., M. D. J. McNeill, B. Shah, R. L. Grimsdale, and
P. F. Lister. ``MARTI--A Multiprocessor Architecture for Ray Tracing Images.''
[MIMD Architectures]
 
\iHEC84\} Heckbert, Paul S., and Pat Hanrahan. ``Beam Tracing Polygonal
Objects.'' \B SIGGRAPH '84\}, p. 119-127. [Spatial Coherence]
 
\iHEC88\} Heckbert, Paul S. ``Ray Tracing Jell-O Brand Gelatin.'' \B CACM\},
Vol. 31, \#2, February 1988, p. 130-134. Revision of same paper in \B SIGGRAPH
'87\}, p. 73-74. [Other Phenomena]

\iHEC90\} Heckbert, Paul S. ``Adaptive Radiosity Textures for Bidirectional Ray
Tracing.'' \B SIGGRAPH '90\}, p. 145-154. [Radiosity]

\iHER90\} Hermitage, Shirley A., Terrance L. Huntsberger, and Beverly
A. Huntsberger. ``Hypercube Algorithm for Radiosity in a Ray Tracing
Environment.'' \B Proceedings of the 5th Distributed Memory Computing
Conference\}, IEEE Society Press, 1990, p. 206-211. [Radiosity]

\iHIL90\} Hill, Francis S., Jr. \B Computer Graphics\}. MacMillian Publishing
Company, New York, 1990. [Textbooks and Other Sources]
 
\iHOF90\} Hofmann, Georg Rainer. ``Who Invented Ray Tracing?'' \B The Visual
Computer\}, Vol. 6, 1990, p. 120-124. [Yet-To-Be-Classified]

\iHOL89\} Holmstr\"om, Lasse, Timo Laakko, Martti M\"antyl\"a, and Panu Rekola.
``Ray Tracing Boundary Models with Implicit Blend Surfaces.'' \B Theory and
Practice of Geometric Modeling\}, Wolfgang Stra\ber and Hans-Peter Seidel
(eds.), Springer-Verlag, 1989, p. 253-271. [Implicit Representations]
 
\iHSI89\} Hsiung, Ping-Kang, and Robert H. P. Dunn. ``Visualizing Relativistic
Effects in Spacetime.'' \B Proceedings of Supercomputing '89 Conference\},
p. 597-606. [Relativity]

\iHSI90a\} Hsiung, Ping-Kang, Robert H. Thibadeau, Christopher B. Cox, and
Robert H. P. Dunn. ``Doppler Color Shift in Relativistic Image Synthesis.'' \B
Proceedings of an International Conference organized by IPSJ to Commemorate the
30th Anniversary\}, 1990, p. 369-377. [Relativity]
 
\iHSI90b\} Hsiung, Ping-Kang, Robert H. Thibadeau, and Robert H. P. Dunn.
``Ray-Tracing Relativity.'' \B Pixel\}, January/February 1990, p. 10-18.
[Relativity]

\iHSI90c\} Hsiung, Ping-Kang, and Robert H. Thibadeau. ``Spacetime Visualization
of Relativistic Effects.'' \B Proceedings of the 1990 ACM Eighteenth Annual
Computer Science Conference\}, 1990, p. 236-243. [Relativity]
 
\iHSI90d\} Hsiung, Ping-Kang, Robert H. Thibadeau, and Michael Wu. ``T-Buffer:
Fast Visualization of Relativistic Effects in Spacetime.'' \B Proceedings of
the 1990 Symposium on Interactive 3D Graphics\}, p. 83-88, 263. [Relativity]

\iHSI90e\} Hsiung, Ping-Kang, Robert H. Thibadeau, Christopher B. Cox, and
Robert H. P. Dunn. ``Time Dilation Visualization in Relativity.'' \B
Supercomputing '90\}, p. 835-844. [Relativity]

\iHSI90f\} Hsiung, Ping-Kang, Robert H. Thibadeau, Christopher B. Cox, Robert
H. P. Dunn, Michael Wu, and Paul Andrew Olbrich. ``Wide-band Relativistic
Doppler Effect Visualization.'' \B Visualization '90\}, p. 83-92. [Relativity]

\iIIZ88\} Iizuka, M. ``Ray-Traced View and Visual Transparent Quality of Double
Transparent Objects.'' \B New Trends in Computer Graphics, Proceedings of CG
International '88\}, Nadia Magnenat-Thalmann and Daniel Thalmann (eds.),
Springer-Verlag, p. 189-198. [Other Phenomena]

\iINA86\} Inakage, Masa. ``Caustics and Specular Reflection Models for Spherical
Objects and Lenses.'' \B The Visual Computer\}, Vol. 2, 1986, p. 379-383.
[Other Phenomena]

\iINA88\} Inakage, Masa. ``Particals: An Artistic Approach to Fuzzy Objects.''
\B New Trends in Computer Graphics, Proceedings of CG International '88\},
Nadia Magnenat-Thalmann and Daniel Thalmann (eds.),Springer-Verlag, p. 126-134.
[Other Phenomena]
 
\iINA89\} Inakage, Masa. ``An Illumination Model for Atmospheric
Environments.'' \B New Advances in Computer Graphics, Proceedings of CG
International '89\}, R. A. Earnshaw and B. Wyvill (eds.), p. 533-548. [Natural
Phenomena]

\iISL91\} \.I\,sler, Veysi, Cevdet Aykanat, and B\"ulent \"Ozg\"u\,c.
``Subdivision of 3D Space Based on the Graph Partitioning for Parallel Ray
Tracing.'' \B Second Eurographics Workshop on Rendering\}, May 1991, p. ?.
[Yet-To-Be-Classified]
 
\iJAN85a\} Jansen, Frederik W. ``A CSG List Priority Hidden Surface
Algorithm.'' \B Proceedings of Eurographics '85\}, Carlo E. Vandoni (ed.),
p. 51-62. [CSG]

\iJAN85b\} Jansen, Frederik W. ``Data Structures for Ray Tracing.'' \B Data
Structures for Raster Graphics\}, L. R. A. Kessener, F. J. Peters, and
M. L. P. van Lierop (eds.), Springer-Verlag, 1985, p. 57-73. [Bounding Volumes,
Data Structures, and Object Hierarchies]

\iJAN91\} Jansen, Frederik W. ``Depth-Order Point Classification Techniques for
CSG Display Algorithms.'' \B ACM TOG\}, Vol. 10, \#1, January 1991, p. 40-70.
[CSG]

\iJEN89\} Jensen, David, and Daniel Reed. ``Ray Tracing on Distributed Memory
Parallel Systems.'' Report No. UIUCDCS-R-89-1551, Department of Computer
Science, University of Illinois at Urbana-Champaign, October 1989. [MIMD
Architectures]
 
\iJEV89a\} Jevans, David A. J., and Brian Wyvill. ``Adaptive Voxel Subdivision
for Ray Tracing.'' \B Graphics Interface '89\}, p. 164-172. Revision of
research report 88/332/44, Computer Science Department, University of Calgary,
November 1988. [Uniform Subdivision]
 
\iJEV89b\} Jevans, David A. J. ``Optimistic Multi-Processor Ray Tracing.''
\B New Advances in Computer Graphics, Proceedings of CG International '89\},
R. A. Earnshaw and B. Wyvill (eds.), p. 507-522. [MIMD Architectures]
 
\iJOY86\} Joy, Kenneth I., and Murthy N. Bhetanabhotla. ``Ray Tracing
Parametric Surface Patches Utilizing Numerical Techniques and Ray Coherence.''
\B SIGGRAPH '86\}, p. 279-285. Also appears in \B Tutorial: Computer Graphics:
Image Synthesis\}, Kenneth I. Joy, Charles W. Grant, Nelson L. Max, and Lansing
Hatfield (eds.), Computer Society Press, Washington, 1988, p. 189-195.
[Explicit Representations]
 
\iKAJ82\} Kajiya, James T. ``Ray Tracing Parametric Patches.'' \B SIGGRAPH
'82\}, p. 245-254. [Explicit Representations]
 
\iKAJ83\} Kajiya, James T. ``New Techniques for Ray Tracing Procedurally
Defined Objects.'' \B ACM TOG\}, Vol. 2, \#3, July 1983, p. 161-181. Also
appears in \B Tutorial: Computer Graphics: Image Synthesis\}, Kenneth I. Joy,
Charles W. Grant, Nelson L. Max, and Lansing Hatfield (eds.), Computer Society
Press, Washington, 1988, p. 168-188. [Procedurally Defined Objects]
 
\iKAJ84\} Kajiya, James T., and Brian P. Von Herzen. ``Ray Tracing Volume
Densities.'' \B SIGGRAPH '84\}, p. 165-174. [Natural Phenomena]
 
\iKAJ86\} Kajiya, James T. ``The Rendering Equation.'' \B SIGGRAPH '86\},
p. 143-150. [The Rendering Equation]
 
\iKAL89\} Kalra, Devendra, and Alan H. Barr. ``Guaranteed Ray Intersections
with Implicit Surfaces.'' \B SIGGRAPH '89\}, p. 297-306. [Implicit
Representations]
 
\iKAP87\} Kaplan, Michael R. ``The Use of Spatial Coherence in Ray Tracing.''
\B Techniques for Computer Graphics\}, David F. Rogers and Rae A. Earnshaw
(eds.), Springer-Verlag, 1987, p. 173-193. [Spatial Coherence]
 
\iKAY79a\} Kay, Douglas Scott, and Donald Greenberg. ``Transparency for
Computer Synthesized Images.'' \B SIGGRAPH '79\}, p. 158-164. [The Ray Tracing
Technique]
 
\iKAY79b\} Kay, Douglas Scott. \B Transparency, Refraction and Ray
Tracing for Computer Synthesized Images\}, Masters Thesis, Cornell University,
1979. [The Ray Tracing Technique]
 
\iKAY86\} Kay, Timothy L., and James T. Kajiya. ``Ray Tracing Complex Scenes.''
\B SIGGRAPH '86\}, p. 269-278. [Bounding Volumes, Data Structures, and Object
Hierarchies]
 
\iKED84\} Kedem, Gershon, and John L. Ellis. ``The Raycasting Machine.'' \B
Proceedings of the IEEE International Conference on Computer Design\}, 1984,
p. 533-538. Also appears in \B Tutorial: Computer Graphics Hardware: Image
Generation and Display\}, Hassan K. Reghbati and Anson Y. C. Lee (eds.),
Computer Society Press, Washington, 1988, p. 285-290. Also appears in
\B Parallel Processing for Computer Vision and Display\}, P. M. Dew,
R. A. Earnshaw, and T. R. Heywood (eds.), Addison-Wesley Publishing Company,
Reading, Massachusetts, 1989, p. 378-401. [Machines for Ray Tracing]

\iKIN86\} Kingdon, Stewart. \B Speeding Up Ray-Scene Intersections\}, Masters
Thesis, University of Waterloo, 1986. [Testing and Analysis]

\iKIR88\} Kirk, David, and James Arvo. ``The Ray Tracing Kernel.'' \B
Proceedings of Ausgraph '88\}, p. 75-82. [Image Synthesis Systems]

\iKIR87\} Kirk, David B. ``The Simulation of Natural Features Using Cone
Tracing.'' \B The Visual Computer\}, Vol. 3, 1987, p. 63-71. Revision of same
paper in \B Advanced Computer Graphics, Proceedings of Computer Graphics Tokyo
'86\}, Tosiyasu L. Kunii (ed.), Springer-Verlag, p. 129-144. [Natural Phenomena]

\iKIT86\} Kitaoka, Shoichi. ``Experimental CSG Environment for Modelling
Solid.'' \B The Visual Computer\}, Vol. 2, 1986, p. 9-14. [Image Synthesis
Systems]

\iKOB87\} Kobayashi, Hiroaki, Tadao Nakamura, and Yoshiharu Shigei. ``Parallel
Processing of an Object Space for Image Synthesis Using Ray Tracing.'' \B The
Visual Computer\}, Vol. 3, 1987, p. 13-22. [MIMD Architectures]

\iKOB88a\} Kobayashi, H., T. Nakamura, and Y. Shigei. ``A Strategy for Mapping
Parallel Ray-Tracing into a Hypercube Multiprocessor System.'' \B New Trends in
Computer Graphics, Proceedings of CG International '88\}, Nadia
Magnenat-Thalmann and Daniel Thalmann (eds.), Springer-Verlag, p. 160-169.
[Hypercube Implementations]

\iKOB88b\} Kobayashi, Hiroaki, Satoshi Nishimura, Hideyuki Kubota, Tadao
Nakamura, and Yoshiharu Shigei. ``Load Balancing Strategies for a Parallel
Ray-Tracing System Based on Constant Subdivision.'' \B The Visual Computer\},
Vol. 4, 1988, p. 197-209. [MIMD Architectures]
 
\iKOB89\} Kobayashi, Hiroaki., Hideyuki Kubota, Susumu Horiguchi, and Tadao
Nakamura. ``Effective Parallel Processing for Continuous Images.'' \B New
Advances in Computer Graphics, Proceedings of CG International '89\},
R. A. Earnshaw and B. Wyvill (eds.), p. 343-352. [MIMD Architectures]
 
\iKUC88\} Kuchkuda, Roman. ``An Introduction to Ray Tracing.'' \B
Theoretical Foundations of Computer Graphics and CAD\}, NATO ASI Series, Vol.
F40, Springer-Verlag, 1988, p. 1039-1060. [The Ray Tracing Technique]
 
\iKUN85\} Kunii, Tosiyasu L., and Geoff Wyvill. ``CSG and Ray Tracing Using
Functional Primitives.'' \B Computer-Generated Images: The State of the Art,
Proceedings of Graphics Interface '85\}, N. Magnenat-Thalmann and D. Thalmann
(ed.), p. 137-152. [CSG]

\iKUN89\} Kunii, T. L., S. Nishimura, and T. Noma. ``The Design of a Parallel
Processing System for Computer Graphics.'' \B Parallel Processing for Computer
Vision and Display\}, P. M. Dew, R. A. Earnshaw, and T. R. Heywood (eds.),
Addison-Wesley Publishing Company, Reading, Massachusetts, 1989, p. 353-377.
[MIMD Architectures]

\iLAM90\} Lamparter, Bernd, Heinrich M\"uller, J\"org Winckler. ``The
Ray-z-Buffer---An Approach for Ray Tracing Arbitrarily Large Scenes.''
Universit\"at Freiburg Institut f\"ur Informatik, April 1990.
[Yet-To-Be-Classified]
 
\iLAN88\} Lang, Laura. ``Lighting Design.'' \B Computer Graphics World\},
October 1988, p. 109-114. [Lighting Design]

\iLAN91\} Lange, Brigitta. ``The Simulation of Radiant Light Transfer with
Stochastic Ray-Tracing.'' \B Second Eurographics Workshop on Rendering\}, May
1991. [Yet-To-Be-Classified]
 
\iLEE85\} Lee, Mark E., Richard A. Redner, and Samuel P. Uselton.
``Statistically Optimized Sampling for Distributed Ray Tracing.'' \B SIGGRAPH
'85\}, p. 61-67. [Antialiasing]

\iLEI88\} Leister, W., Th. Maus, H. M\"uller, B. Neidecker, and A. St\"o\ber.
```Occursus Cum Novo' - Computer Animation by Ray Tracing in a Network.'' \B
New Trends in Computer Graphics, Proceedings of CG International '88\}, Nadia
Magnenat-Thalmann and Daniel Thalmann (eds.), Springer-Verlag, p. 83-92. [Image
Synthesis Systems]
 
\iLER87\} Leray, Pascal. ``Towards a Z-Buffer and Ray-Tracing Multimode System
Based on Parallel Architecture and VLSI Chips.'' \B Advances in Computer
Graphics Hardware I\}, W. Stra\ber (ed.), Springer-Verlag, 1987, p. 141-145.
[Machines for Ray Tracing]
 
\iLEV87\} Levner, Geoff, Paolo Tassinari, and Daniele Marini. ``A Simple,
General Method for Ray Tracing Bicubic Surfaces.'' \B Computer Graphics 1987 -
Proceedings of CG International '87\}, Tosiyasu L. Kunii (ed.),
Springer-Verlag, p.285-302. Also appears in \B Theoretical Foundations of
Computer Graphics and CAD\}, NATO ASI Series, Vol. F40, Springer-Verlag, 1988,
p. 805-820. [Explicit Representations]

\iLEV90a\} Levoy, Marc. ``A Hybrid Ray Tracer for Rendering Polygon and Volume
Data.'' \B IEEE CG\&A\}, March 1990, p. 33-40. [Volume Data]

\iLEV90b\} Levoy, Marc. ``Efficient Ray Tracing of Volume Data.'' \B ACM TOG\},
Vol. 9, \#3, July 1990, p. 245-261. [Volume Data]
 
\iLEV90c\} Levoy, Marc. ``Volume Rendering by Adaptive Refinement.'' \B The
Visual Computer\}, Vol. 6, 1990, p. 2-7. [Volume Data]
 
\iLIN87\} Lin, Jimmy Jih-Ming. \B Fast Ray Tracing on BSP-Trees\}, Masters
Thesis, Computer Science Department, University of Central Florida, Orlando,
1987. [Bounding Volumes, Data Structures, and Object Hierarchies]
 
\iLIN91\} Lin, Tony T. Y., and Mel Slater. ``Stochastic Ray Tracing Using SIMD
Processor Arrays.'' \B The Visual Computer\}, Vol. 7, July 1991, p. 187-199.
[SIMD Architectures]
 
\iLIS90\} Lischinski, Daniel, and Jokob Gonczarowski. ``Improved Techniques for
Ray Tracing Parametric Surfaces.'' \B The Visual Computer\}, Vol. 6, 1990,
p. 134-152. [Explicit Representations]
 
\iMAC88\} MacDonald, David. \B Space Subdivision Algorithms for Ray Tracing\}.
Masters Thesis, Computer Science Department, University of Waterloo, 1988.
[Uniform Subdivision]
 
\iMAC90\} MacDonald, J. David, and Kellogg S. Booth. ``Heuristics for Ray
Tracing Using Space Subdivision.'' \B The Visual Computer\}, Vol. 6, 1990,
p. 153-166. Also appears in \B Graphics Interface '89\}, p. 152-163. [Uniform
Subdivision]
 
\iMAG85\} Magnenat-Thalmann, Nadia, and Daniel Thalmann. \B Computer Animation:
Theory and Practice\}, Springer-Verlag, 1985. [Textbooks and Other Sources]
 
\iMAG87\} Magnenat-Thalmann, Nadia, and Daniel Thalmann. \B Image Synthesis:
Theory and Practice\}, Springer-Verlag, 1987. [Textbooks and Other Sources]

\iMAR87\} Marsh, Donald M. ``UgRay: An Efficient Ray-Tracing Renderer for
UniGrafix.'' Report No. UCB/CSD87/360, Computer Science Division (EECS), UC
Berkeley, May 1987. [Image Synthesis Systems]
 
\iMAR88\} Marsh, Stephen C. ``Fine Grain Parallel Architectures and the
Creation of High-Quality Images.'' \B Theoretical Foundations of Computer
Graphics and CAD\}, NATO ASI Series, Vol. F40, Springer-Verlag, 1988,
p. 727-754. [MIMD Architectures]
 
\iMAX81\} Max, Nelson L. ``Vectorized Procedural Models for Natural Terrain:
Waves and Islands in the Sunset.'' \B SIGGRAPH '81\}, p. 317-324. [Natural
Phenomena]
 
\iMIT87\} Mitchell, Don P. ``Generating Antialiased Images at Low Sampling
Densities.'' \B SIGGRAPH '87\}, p. 65-72. [Antialiasing]

\iMIT91\} Mitchell, Don P. ``Spectrally Optimal Sampling for Distribution Ray
Tracing.'' \B SIGGRAPH '91\}, p. 157-164. [Antialiasing]

\iMON90\} Montani, C., and R. Scopigno. "Rendering Volumetric Data Using the
STICKS Representation Scheme." \B Proceedings of the San Diego Workshop on
Volume Visualization\}, 1990, p. 87-93, 112. [Volume Data]
 
\iMOR81\} Moravec, Hans P. ``3D Graphics and the Wave Theory.'' \B SIGGRAPH
'81\}, p. 289-296. [Wave Theory]
 
\iMOR89\} Morris, D. T., and P. M. Dew. ``Dynamic Dataflow Algorithms for Ray
Tracing CSG Objects.'' \B Parallel Processing for Computer Vision and
Display\}, P. M. Dew, R. A. Earnshaw, and T. R. Heywood (eds.), Addison-Wesley
Publishing Company, Reading, Massachusetts, 1989, p. 452-460. [CSG]
 
\iMOS85\} Moshell, J. M., and T. J. Cullip. ``An Array Processor for Ray
Tracing.'' Department of Computer Science, University of Central Florida,
Orlando, November 1985. [SIMD Architectures]
 
\iMUL86\} M\"uller, H. ``Image Generation by Space Sweep.'' \B Computer
Graphics Forum\}, Vol. 5, 1986, p. 189-195. [Spatial Coherence]

\iMUR88\} Murakami, Koichi, Katsuhiko Hirota and Mitsuo Ishii. ``Fast Ray
Tracing.'' \B Fujitsu Science and Technology Journal\}, vol. 24, \#2, June
1988, p. 150-159. [Uniform Subdivision]

\iMUR91\} Muraki, Shigeru. ``Volumetric Shape Description of Range Data Using
`Blobby Model'.'' \B SIGGRAPH '91\}, p. 227-235. [Other Phenomena]

\iMUS88a\} Musgrave, F. Kenton, Lewis E. Hitchner, James L. Murphy. ``A
Realistic Model of Refraction for Computer Graphics.'' \B Proceedings of
Modelling and Simulation on Microcomputers 1988\}, p. 37-43. [Other Phenomena]

\iMUS88b\} Musgrave, F. Kenton. ``Grid Tracing: Fast Ray Tracing for Height
Fields.'' Research Report YALEU/DCS/RR-639, Yale University, July 1988. [Other
Phenomena]

\iMUS89a\} Musgrave, F. Kenton. ``Prisms and Rainbows: a Dispersion Model for
Computer Graphics.'' \B Proceedings of Graphics Interface '89 - Vision
Interface '89\}, p. 227-234. [Other Phenomena]
 
\iMUS89b\} Musgrave, F. Kenton, Craig E. Kolb, and Robert S. Mace. ``The
Synthesis and Rendering of Eroded Fractal Terrains.'' \B SIGGRAPH '89\},
p. 41-50. [Natural Phenomena]

\iMUS90\} Musgrave, F. Kenton. ``A Note on Ray Tracing Mirages.'' \B IEEE
CG\&A\}, November 1990, p. 10-12. [Natural Phenomena]

\iNAK89\} Nakamae, Eihachiro, Takao Ishizaki, Tomoyuki Nishita, and Shinichi
Takita. ``Compositing 3D Images with Antialiasing and Various Shading
Effects.'' \B IEEE CG\&A\}, March 1989, p. 21-29. [Antialiasing]
 
\iNEM86\} Nemoto, Keiji, and Takao Omachi. ``An Adaptive Subdivision by Sliding
Boundary Surfaces for Fast Ray Tracing.'' \B Proceedings of Graphics Interface
'86/Vision Interface '86\}, p. 43-48. [Nonuniform Subdivision]
 
\iNIS83\} Nishimura, Hitoshi, Hiroshi Ohno, Toru Kawata, Isao Shirakawa, and
Koichi Omura. ``LINKS-1: A Parallel Pipelined Multimicrocomputer System for
Image Creation.'' \B Proceedings of the 10th Annual International Symposium on
Computer Architecture\}, 1983, p. 387-394. Also appears in \B Tutorial:
Computer Graphics Hardware: Image Generation and Display\}, Hassan K. Reghbati
and Anson Y. C. Lee (eds.), Computer Society Press, Washington, 1988,
p. 320-327. [MIMD Architectures]

\iNIS90\} Nishita, Tomoyuki, Thomas W. Sederberg, and Masanori Kakimoto. ``Ray
Tracing Trimmed Rational Surface Patches.'' \B SIGGRAPH '90\}, p. 337-345.
[Explicit Representations]

\iNOV90\} Novins, Kevin L., Francois X. Sillion, and Donald P. Greenberg. "An
Efficient Method for Volume Rendering Using Perspective Projection." \B
Proceedings of the San Diego Workshop on Volume Visualization\}, 1990,
p. 95-102. [Volume Data]

\iOHT87\} Ohta, Masataka, and Mamoru Maekawa. ``Ray Coherence Theorem and
Constant Time Ray Tracing Algorithm.'' \B Computer Graphics 1987 - Proceedings
of CG International '87\}, Tosiyasu L. Kunii (ed.), Springer-Verlag, p. 303-314.
[Spatial Coherence]

\iOHT90\} Ohta, Masataka, and Mamoru Maekawa. ``Ray-Bound Tracing for
Perfect and Efficient Anti-Aliasing.'' \B The Visual Computer\}, Vol. 6,
1990, p. 125-133. Revision of ``Bounded Ray Tracing for Perfect Efficient
Anti-aliasing.'' Technical Report No. 87-03, Dept. of Information Science,
University of Tokyo, January 1987. [Antialiasing]

\iORC88\} Orcutt, David Edward. ``Implementation of Ray Tracing on the
Hypercube.'' \B Third Conference on Hypercube Concurrent Computers and
Applications\}, Geoffrey Fox (ed.), Vol. 2, 1988, p. 1207-1210. [Hypercube
Implementations]
 
\iPAC87\} Packer, Jamie. ``Exploiting Concurrency: A Ray Tracing Example.''
Inmos Technical Note 7, Inmos Limited, October 1987. [Transputer
Implementations]
 
\iPAI89\} Painter, James, and Kenneth Sloan. ``Antialiased Ray Tracing by
Adaptive Progressive Refinement.'' \B SIGGRAPH '89\}, p. 281-288. [Antialiasing]
 
\iPAL89\} Palmer, Thomas C, Frederick H. Hausheer, and Jeffrey D. Saxe.
 ``Applications of Ray Tracing in Molecular Graphics.'' \B Journal of Molecular
Graphics\}, Vol. 7, September 1989, p. 157, 160-164. [Molecular Modeling]
 
\iPEA84\} Peachey, Darwyn R. ``PORTRAY - An Image Synthesis System for
Realistic Computer Graphics.'' Research Report 84-18, Department of
Computational Science, University of Saskatchewan, 1984. [Image Synthesis
Systems]
 
\iPEA86\} Peachey, Darwyn R. ``PORTRAY - An Image Synthesis System.''
\B Proceedings of Graphics Interface '86/Vision Interface '86\}, p. 37-42.
[Image Synthesis Systems]

\iPEN87\} Peng, Qunsheng, Yining Zhu, and Youdong Liang. ``A Fast Ray Tracing
Algorithm Using Space Indexing Techniques.'' \B Proceedings of Eurographics
'87\}, Guy Mar\'echal (ed.), p. 11-23. [Bounding Volumes, Data Structures, and
Object Hierarchies]
 
\iPER89\} Perlin, Ken, and Eric M. Hoffert. ``Hypertexture.'' \B SIGGRAPH
'89\}, p. 253-262. [Natural Phenomena]

\iPET87\} Peterson, John W. ``Ray Tracing Spline Surfaces with Motion Blur.''
Department of Computer Science, University of Utah, 1987. [Explicit
Representations]
 
\iPET90\} Peterson, Ivars. ``Space-Time Odyssey.'' \B Science News\}, Vol. 137,
\#15, April 14, 1990, p. 232-237. [Relativity]
 
\iPLU83\} Plunkett, David J., Joseph M. Cychosz, and Michael J. Bailey. ``The
Vectorization of a Ray Tracing Program for Image Generation.'' \B Proceedings
of Cyber 200 Applications Seminar\}, NASA Conference Publication 2295, October
1983, p. 315-323. [Machines for Ray Tracing]

\iPLU84\} Plunkett, David J. \B A Vectorized Ray Tracing Algorithm\}, M.S.M.E.
Thesis, Purdue University, August 1984. [Machines for Ray Tracing]
 
\iPLU85\} Plunkett, David J., and Michael J. Bailey. ``The Vectorization of a
Ray-Tracing Algorithm for Improved Execution Speed.'' \B IEEE CG\&A\}, August
1985, p. 52-60. [Machines for Ray Tracing]

\iPOT89\} Potmesil, Michael, Leonard McMillan, Eric M. Hoffert, Jennifer
F. Inman, Robert L. Farah, and Marc Howard. ``A Parallel Image Computer with a
Distributed Frame Buffer: System Architecture and Programming.'' \B Proceedings
of Eurographics '89\}, W. Hansmann, F. R. A. Hopgood and W. Strasser (eds.),
p. 197-208, 549. [MIMD Architectures]
 
\iPRI89\} Priol, Thierry, and Kadi Bouatouch. ``Static Load Balancing for a
Parallel Ray Tracing on a MIMD Hypercube.'' \B The Visual Computer\}, Vol. 5,
1989, p. 109-119. [Hypercube Implementations]
 
\iPUE91\} Pueyo, Xavier. ``Diffuse Interreflections. Techniques for Form-Factor
Computation: A Survey.'' \B The Visual Computer\}, Vol. 7, July 1991,
p. 200-209. [Radiosity]
 
\iPUL87\} Pulleyblank, Ron, and John Kapenga. ``The Feasibility of a VLSI Chip
for Ray Tracing Bicubic Patches.'' \B IEEE CG\&A\}, March 1987, p. 33-44. Also
appears in \B Tutorial: Computer Graphics Hardware: Image Generation and
Display\}, Hassan K. Reghbati and Anson Y. C. Lee (eds.), Computer Society
Press, Washington, 1988, p. 328-339. Also appears as ``A VLSI Chip for Ray
Tracing Bicubic Patches'' in \B Advances in Computer Graphics Hardware I\},
W. Stra\ber (ed.), 1987, p. 125-140. [Special Purpose Hardware]

\iPUR86\} Purgathofer, Werner. ``A Statistical Method for Adaptive Stochastic
Sampling.'' \B Proceedings of Eurographics '86\}, A. A. G. Requicha (ed.),
p. 145-152. [Antialiasing]
 
\iQUE88\} Quek, Lee Hian, and D. D. Hearn. ``Efficient Space-Subdivision Methods
in Ray-Tracing Algorithms,'' Report No. UIUCDCS-R-88-1468, Department of
Computer Science, University of Illinois at Urbana-Champaign, November 1988.
[Nonuniform Subdivision]
 
\iQUE89\} Quek, Lee Hian. \B Ray Tracing with Space Subdivision on a
Vector-Multiprocessor System\}, Masters Thesis, Report No. UIUCDCS-R-89-1491,
Department of Computer Science, University of Illinois at Urbana-Champaign,
February 1989. [MIMD Architectures]
 
\iRAN90\} Ransen, Owen F. ``The Art of Ray Tracing.'' \B Byte\}, February 1990,
p. 238-242. [Transputer Implementations]
 
\iROB90\} Robb, Paul, and Barbara Pawlowski. ``Computer Ray Tracing Speeds.''
\B Applied Optics\}, Vol. 29, \#13, May 1 1990, p. 1933-1939. [Testing and
Analysis]

\iROE90\} Roelens, M., G. Fertey, B. Peroche. ``Light Sources in a Ray Tracing
Environment.'' Technical Report \#90-6, Ecole Nationale Sup\'erieure des Mines
de Saint-Etienne, D\'epartement Informatique Appliqu\'ee, June 1990. Also
appears in \B Proceedings Eurographics Workshop on Photosimulation, Realism and
Physics in Computer Graphics\}, June 1990, p. 195-213. [Lighting Models]
 
\iROG85\} Rogers, David F. \B Procedural Elements for Computer Graphics\},
McGraw-Hill Book Company, New York, 1985. [Textbooks and Other Sources]
 
\iROT82\} Roth, Scott D. ``Ray Casting for Modeling Solids.'' \B Computer
Graphics and Image Processing\}, Vol. 18, 1982, p. 109-144. [The Ray Tracing
Technique]
 
\iRUB80\} Rubin, Steven M., and Turner Whitted. ``A 3-Dimensional
Representation for Fast Rendering of Complex Scenes.'' \B SIGGRAPH '80\}, p.
110-116. [Bounding Volumes, Data Structures, and Object Hierarchies]

\iRUS90\} Rushmeier, Holly E., and Kenneth E. Torrance. ``Extending the
Radiosity Method to Include Specularly Reflecting and Translucent Materials.''
\B ACM TOG\}, Vol. 9, \#1, January 1990, p. 1-27. [Radiosity]

\iSAE90\} Le Saec, Betrand, and Christophe Schlick. ``A Progressive
Ray-Tracing-Based Radiosity with General Reflectance Functions.'' Technical
Report \#90-17, Laboratoire Bordelais de Recherche en Informatique, Universit\'e
de Bordeaux I. Also appears in Proceedings Eurographics Workshop on
Photosimulation, Realism and Physics in Computer Graphics, June 1990,
p. 103-116. [Radiosity]

\iSAL89\} Salesin, David, and Jorge Stolfi. ``The ZZ-Buffer: a Simple and
Efficient Rendering Algorithm with Reliable Antialiasing.'' \B Proceedings of
the PIXIM '89 Conference\}, p. 451-466. [Antialiasing]

\iSAL90\} Salesin, David, and Jorge Stolfi. ``Rendering CSG Models with a
ZZ-Buffer.'' \B SIGGRAPH '90\}, p. 67-76. [CSG]

\iSAL88\} Salmon, John, and Jeff Goldsmith. ``A Hypercube Ray-tracer.'' \B
Third Conference on Hypercube Concurrent Computers and Applications.\},
Geoffrey Fox (ed.), Vol. 2, 1988, p. 1194-1206. [Hypercube Implementations]

\iSAL89\} Salmon, Rod, and Mel Slater. \B Computer Graphics: Systems \&
Concepts\}. Addison-Wesley Publishing Company, Reading, Massachusetts, 1989.
[Textbooks and Other Sources]

\iSAM89\} Samet, Hanan. ``Implementing Ray Tracing with Octrees and Neighbor
Finding.'' \B Computers \& Graphics\}, Vol. 13, \#4, 1989, p. 445-460.
[Bounding Volumes, Data Structures, and Object Hierarchies]
 
\iSAM90\} Samet, Hanan. \B Applications of Spatial Data Structures: Computer
Graphics, Image Processing, and GIS\}, Addison-Wesley, 1990. [Textbooks and
Other Sources]
 
\iSCHE87\} Scherson, Isaac D., and Elisha Caspary. ``Data Structures and the
Complexity of Ray Tracing.'' \B The Visual Computer\}, Vol. 3, 1987, p. 201-213.
[Bounding Volumes, Data Structures, and Object Hierarchies]
 
\iSCHE88\} Scherson, Isaac D., and Elisha Caspary. ``Multiprocessing for Ray
Tracing: A Hierarchical Self-Balancing Approach.'' \B The Visual Computer\},
Vol. 4, 1988, p. 188-196. [MIMD Architectures]

\iSCH91\} Schlick, Christophe. ``An Adaptive Sampling Technique for
Multidimensional Integration by Ray-Tracing.'' \B Second Eurographics Workshop
on Rendering\}, May 1991, p. ?. [Yet-To-Be-Classified]
 
\iSCHM88\} Schmitt, Alfred, Heinrich M\"uller, and Wolfgang Leister.
``Ray Tracing Algorithms --- Theory and Practice.'' \B Theoretical
Foundations of Computer Graphics and CAD\}, NATO ASI Series, Vol. F40,
Springer-Verlag, 1988, p. 997-1030. [The Ray Tracing Technique]
 
\iSCH88\} Schneider, Bengt-Olaf. ``Ray Tracing Rational B-Spline Patches in
VLSI.'' \B Advances in Computer Graphics Hardware II\}, A. A. M. Kuijk and
W. Stra\ber (eds.), Springer-Verlag, 1988, p. 45-63. [Special Purpose Hardware]
 
\iSED84\} Sederberg, Thomas W., and David C. Anderson. ``Ray Tracing of Steiner
Patches.'' \B SIGGRAPH '84\}, p. 159-164. [Implicit Representations]
 
\iSEM86\} Semwal, S. K., and J. M. Moshell. ``Geometric Issues of the Slicing
Extent Technique for Ray Tracing.'' Technical Report CS-TR-86-17, Department of
Computer Science, University of Central Florida, Orlando, 1986. [Nonuniform
Subdivision]
 
\iSEM87\} Semwal, S. K. \B The Slicing Extent Technique for Fast Ray Tracing\}.
Ph.D. Dissertation, Computer Science Department, University of Central Florida,
1987. [Nonuniform Subdivision]
 
\iSEQ89\} S\'equin, Carlo H., and Eliot K. Smyrl. ``Parametric Ray Tracing.''
\B SIGGRAPH '89\}, p. 307-314. [Temporal Coherence]
 
\iSHI87\} Shinya, Mikio, Tokiichiro Takahashi, and Seiichiro Naito.
``Principles and Applications of Pencil Tracing.'' \B SIGGRAPH '87\}, p. 45-54.
[Spatial Coherence]

\iSHI89\} Shinya, Mikio, Takafumi Saito,, and Tokiichiro Takahashi. ``Rendering
Techniques for Transparent Objects.'' \B Graphics Interface '89\}, p. 173-181.
[Spatial Coherence]

\iSHI90a\} Shirley, Peter. ``A Ray Tracing Method for Illumination Calculation
in Diffuse-Specular Scenes.'' \B Proceedings of Graphics Interface '90\},
p. 205-212. [Radiosity]

\iSHI90b\} Shirley, Peter, Kelvin Sung, and William Brown. ``A Ray Tracing
Framework for Global Illumination Systems.'' \B Graphics Interface '90\},
p. 117-128  [Lighting Models] *

\iSHI91\} Shirley, Peter S. \B Physically Based Lighting Calculations for
Computer Graphics\}, Ph.D. Thesis, Computer Science Department, University of
Illinois at Urbana-Champaign, 1991. [Lighting Models]
 
\iSIL89\} Sillion, Francois, and Claude Pucch. ``A General Two-Pass Method for
Integrating Specular and Diffuse Reflection.'' \B SIGGRAPH '89\}, p. 335-344.
[Radiosity]
 
\iSNY87\} Snyder, John M., and Alan H. Barr. ``Ray Tracing Complex Models
Containing Surface Tessellations.'' \B SIGGRAPH '87\}, p. 119-128.
[Procedurally Defined Objects]

\iSPA90\} Spackman, John. \B Scene Decompositions for Accelerated Ray Tracing\},
Ph.D. Thesis, The University of Bath, UK, 1990. Available as Bath Computer
Science Technical Report 90/33. [Nonuniform Subdivision]

\iSPE85\} Speer, L. Richard, Tony D. DeRose, and Brian A. Barsky. ``A
Theoretical and Empirical Analysis of Coherent Ray-Tracing.'' \B
Computer-Generated Images: The State of the Art, Proceedings of Graphics
Interface '85\}, N. Magnenat-Thalmann and D. Thalmann (ed.), p. 11-25. Also
appears in \B Graphics Interface '85\}, p. 1-8. [Spatial Coherence]
 
\iSTE84\} Steinberg, Herbert A. ``A Smooth Surface Based on Biquadratic
Patches.'' \B IEEE CG\&A\}, September 1984, p. 20-23. [Explicit Representations]
 
\iSTE88\} Stepoway, Stephen L., and Michael Christiansen. ``Parallel Rendering
of Fractal Surfaces.'' \B International Journal of Parallel Programming\},
Vol. 17, \#1, 1988, p. 43-58. [MIMD Architectures]
 
\iSTE89\} Stettner, Adam, and Donald P. Greenberg. ``Computer Graphics
Visualization for Acoustic Simulation.'' \B SIGGRAPH '89\}, p. 195-206.
[Acoustics]
 
\iSTO88\} St\"o\ber, Achim, Alfred Schmitt, Burkhard Neidecker, Heinrich
M\"uller, Thomas Maus, and Wolfgang Leister. ```Occursus Cum Novo' - Tools for
Efficient Photo-Realistic Computer Animation.'' \B Proceedings of Eurographics
'88\}, David A. Duce and Pierre Jancene (eds.), p. 31-41, C-1. [Image Synthesis
Systems]

\iSUB90\} Subramanian, K. R. ``Adapting Search Structures to Scene
Characteristics for Ray Tracing'', Ph.D. thesis, Department of Computer
Sciences, University of Texas at Austin, December 1990. [Nonuniform
Subdivision]

\iSUB91\} Subramanian, K. R., and Donald S. Fussell. ``Automatic Termination
Criteria for Ray Tracing Hierarchies.'' \B Graphics Interface '91\}, p. ?.
[Bounding Volumes, Data Structures, and Object Hierarchies] *

\iSUN91\} Sung, Kelvin. ``A DDA Octree Traversal Algorithm for Ray Tracing.''
\B Eurographics '91\}, p. ?. [Nonuniform Subdivision]
 
\iSWE86\} Sweeney, Michael A. J., and Richard H. Bartels. ``Ray Tracing
Free-Form B-Spline Surfaces.'' \B IEEE CG\&A\}, February 1986, p. 41-49.
[Explicit Representations]

\iTAK90\} Takagi, Atsushi, Hitoshi Takaoko, Tetsuya Oshima, and Yoshinori
Ogata. ``Accurate Rendering Techique Based on Colorimetric Conception.'' \B
SIGGRAPH '90\}, p. 263-272. [Other Phenomena]

\iTAM84\} Tamminen, Markku, Olli Karonen, and Martti M\"antyl\"a. ``Ray-Casting
and Block Model Conversion Using a Spatial Index.'' \B CAD\}, Vol. 16, \#4,
July 1984, p. 203-208. [Bounding Volumes, Data Structures, and Object
Hierarchies]

\iTEZ85\} Tezenas du Montcel, Bruno, and Alain Nicolas. ``An
Illumination Model for Ray Tracing.'' \B Proceedings of Eurographics '85\},
Carlo E. Vandoni (ed.), p. 63-75. [Lighting Models]

\iTHI90a\} Thirion, J. P. ``Interval Arithmetic for High Resolution Ray
Tracing.'' Technical Report 90-4, Laboratoire d'Informatique de l'Ecole Normale
Sup\'erieure, Paris, France, February 1990. [Spatial Coherence]

\iTHI90b\} Thirion, J. P. ``Tries: Data Structures Based on Boolean
Representation for Ray Tracing.'' Technical Report 90-3, Laboratoire
d'Informatique de l'Ecole Normale Sup\'erieure, Paris, France, February 1990.
Also appears in \B Proceedings of Eurographics '90\}, p. 530-542. [Bounding
Volumes, Data Structures, and Object Hierarchies]
 
\iTHO86\} Thomas, Spencer W. ``Dispersive Refraction in Ray Tracing.'' \B The
Visual Computer\}, Vol. 2, 1986, p. 3-8. [Other Phenomena]

\iTHO89\} Thomas, D., Arun N. Netravali, and D. S. Fox. ``Anti-aliased Ray
Tracing with Covers.'' \B Computer Graphics Forum\}, 8 (1989), p. 325-336.
[Antialiasing]
 
\iTOT85\} Toth, Daniel L. ``On Ray Tracing Parametric Surfaces.'' \B SIGGRAPH
'85\}, p. 171-179. [Explicit Representations]

\iTRO87\} Trousset, Yves, and Francis Schmitt. ``Active-Ray Tracing for 3D
Medical Imaging.'' \B Proceedings of Eurographics '87\}, Guy Mar\'echal (ed.),
p. 139-150. [Medical Imaging]
 
\iULL83\} Ullner, Michael Karl. \B Parallel Machines for Computer Graphics\},
Ph.D. Dissertation, California Institute of Technology, 1983. [MIMD
Architectures]
 
\iVAT84\} Vatti, Bala R. \B Multiprocessor Ray Tracing\}. University
of Calgary, M.S. Thesis, 1984. * [Read it, but don't have abstract]

\iVLA90\} Vlassopoulos, Vasilis. ``Adaptive Polygonization of Parametric
Surfaces.'' \B The Visual Computer\}, Vol. 6, 1990, p. 291-298. [Explicit
Representations]
 
\iWAI88\} Waij, Rudi. \B Acceleration of Ray Tracing\}, Masters Thesis, Delft
University Press, Delft University of Technology, 1988. [Testing and Analysis]

\iWAL87\} Wallace, John R., Michael F. Cohen, and Donald P. Greenberg. ``A
Two-Pass Solution to the Rendering Equation: A Synthesis of Ray Tracing and
Radiosity Methods.'' \B SIGGRAPH '87\}, p. 311-320. [Radiosity]
 
\iWAL89\} Wallace, John R., Kells A. Elmquist, and Eric A. Haines. ``A Ray
Tracing Algorithm for Progressive Radiosity.'' \B SIGGRAPH '89\}, p. 315-324.
[Radiosity]
 
\iWAR88\} Ward, Gregory J., Francis M. Rubinstein, and Robert D. Clear. ``A Ray
Tracing Solution for Diffuse Interreflection.'' \B SIGGRAPH '88\}, p. 85-92.
[Radiosity]

\iWAR91\} Ward, Gregory J. ``Adaptive Shadow Testing for Ray Tracing.'' \B
Second Eurographics Workshop on Rendering\}, May 1991, p. ?. [Shadow Testing]
 
\iWAT89\} Watt, Alan. \B Fundamentals of Three-Dimensional Computer
Graphics\}, Addison-Wesley Publishing Company, Reading, Massachusetts, 1989.
[Textbooks and Other Sources]

\iWAT90\} Watt, Mark. ``Light-Water Interaction Using Backward Beam Tracing.''
\B SIGGRAPH '90\}, p. 377-385. [Natural Phenomena]
 
\iWEB90\} Webber, Robert E. ``Ray Tracing Voxel Data Via Biquadratic Local
Surface Interpolation.'' \B The Visual Computer\}, Vol. 6, 1990, p. 8-15.
[Explicit Representations]
 
\iWEG84\} Weghorst, Hank, Gary Hooper, and Donald P. Greenberg. ``Improved
Computational Methods for Ray Tracing.'' \B ACM TOG\}, Vol. 3, \#1, January
1984, p. 52-69. [Bounding Volumes, Data Structures, and Object Hierarchies]
 
\iWHI80\} Whitted, Turner. ``An Improved Illumination Model for Shaded
Display.'' \B CACM\}, Vol. 23, \#6, June 1980, p. 343-349. Also appears in
\B Tutorial: Computer Graphics: Image Synthesis\}, Kenneth I. Joy, Charles W.
Grant, Nelson L. Max, and Lansing Hatfield (eds.), Computer Society Press,
Washington, 1988, p. 132-138. [The Ray Tracing Technique]
 
\iWHI82\} Whitted, Turner. ``Processing Requirements for Hidden Surface
Elimination and Realistic Shading.'' \B IEEE Digest of Papers, COMPCON\},
Spring 1982, p. 245-250. [Basic Ray Tracing]

\iWHI85\} Whitted, Turner, and Robert L. Cook. ``A Comprehensive Shading
Model.'' \B Tutorial: Computer Graphics: Image Synthesis\}, Kenneth I. Joy,
Charles W. Grant, Nelson L. Max, and Lansing Hatfield (eds.), Computer Society
Press, Washington, 1988, p. 232-243. Also appears in unpublished course notes
from \B State of the Art in Image Synthesis, SIGGRAPH '85 Course Notes \#11\}.
[Lighting Models]
 
\iWIJ84a\} van Wijk, Jarke J. ``Ray Tracing Objects Defined by Sweeping a
Sphere.'' \B Proceedings of Eurographics '84\}, Ketil B\o and Hugh A. Tucker
(ed.), p. 73-82. [Objects Defined by Sweeps and Revolutions]
 
\iWIJ84b\} van Wijk, Jarke J. ``Ray Tracing Objects Defined by Sweeping Planar
Cubic Splines.'' \B ACM TOG\}, Vol. 3, \#3, July 1984, p. 223-237. [Objects
Defined by Sweeps and Revolutions]

\iWIJ84c\} van Wijk, J. J., and F. W. Jansen. ``Realism in Raster Graphics.''
\B Computers and Graphics\}, Vol. 8, \#2, 1984, p. 217-219. [Image Synthesis
Systems]

\iWIJ86\} van Wijk, Jarke J. \B On New Types of Solid Models and Their
Visualization with Ray Tracing\}, Ph.D. Thesis, Delft University Press, Delft
University of Technology, 1986. [CSG]

\iWILN88\} Williams, Nicholas S., B. F. Buxton, and H. Buxton. ``Distributed
Ray Tracing Using an SIMD Processor Array.'' \B Theoretical Foundations of
Computer Graphics and CAD\}, NATO ASI Series, Vol. F40, Springer-Verlag, 1988,
p. 703-725. [SIMD Architectures]
 
\iWILT88\} Williams, Tom. ``Graphics System Designers Strive for
Photorealism.'' \B Computer Design\}, August 1, 1988, p. 50-61. [Image
Synthesis Systems]
 
\iWIL89\} Wilson, Thomas B. \B Ray Tracing Techniques\}, M.S. Thesis,
Computer Science Department, University of Central Florida, Orlando, 1989.
[The Ray Tracing Technique]

\iWOL90\} Wolff, Lawrence B., and David J. Kurlander. ``Ray Tracing with
Polarization Parameters.'' \B IEEE CG\&A\}, Novemer 1990, p. 44-55. [Wave
Theory]

\iWOO90a\} Woo, Andrew, Pierre Poulin, and Alain Fournier. ``A Survey of Shadow
Algorithms.'' \B IEEE CG\&A\}, November 1990, p. 13-32. [Shadow Testing]

\iWOO90b\} Woo, Andrew, and John Amanatides. ``Voxel Occlusion Testing: A
Shadow Determination Accelerator for Ray Tracing.'' \B Proceedings of Graphics
Interface '90\}, p. 213-220. [Shadow Testing]

\iWOO89\} Woodward, Charles. ``Ray Tracing Parametric Surfaces by Subdivision in
Viewing Plane.'' \B Theory and Practice of Geometric Modeling\}, Wolfgang
Stra\ber and Hans-Peter Seidel (eds.), Springer-Verlag, 1989, p. 273-287.
[Explicit Representations]

\iWYV85\} Wyvill, Geoff, and Tosiyasu L. Kunii. ``A Functional Model for
Constructive Solid Geometry.'' \B The Visual Computer\}, Vol. 1, 1985, p. 3-14.
[CSG]
 
\iWYV86a\} Wyvill, Geoff, Tosiyasu L. Kunii, and Yasuto Shirai. ``Space
Division for Ray Tracing in CSG.'' \B IEEE CG\&A\}, April 1986, p. 28-34. [CSG]
 
\iWYV86b\} Wyvill, Geoff, Andrew Pearce, and Brian Wyvill. ``The Representation
of Water.'' \B Proceedings of Graphics Interface '86/Vision Interface '86\},
p. 217-222. [Natural Phenomena]

\iWYV87\} Wyvill, Geoff, Alistair Ward, and Tim Brown. ``Sketches by Ray
Tracing.'' \B Computer Graphics 1987 - Proceedings of CG International '87\},
Tosiyasu L. Kunii (ed.), Springer-Verlag, p. 315-333. [Yet-To-Be-Classified]

\iWYV88\} Wyvill, G., and P. Sharp. ``Volume and Surface Properties in CSG.''
\B New Trends in Computer Graphics, Proceedings of CG International '88\},
Nadia Magnenat-Thalmann and Daniel Thalmann (eds.), Springer-Verlag, p. 257-267.
[CSG]

\iWYV89\} Wyvill, Geoff, and P. Sharp. ``Fast Antialiasing of Ray Traced
Images.'' \B New Trends in Computer Graphics, Proceedings of CG International
'89\}, p. 578-588. [Antialiasing]

\iWYV90\} Wyvill, Geoff, and Andrew Trotman. ``Ray-Tracing Soft Objects.'' \B
Proceedings of CG International '90\}, p. 467-476. [Implicit Representations]
 
\iYAN87\} Yang, Chang-Gui. ``On Speeding Up Ray Tracing of B-Spline Surfaces.''
\B CAD\}, 1987, p. 122-130. [Explicit Representations]

\iYOK86\} Yokoi, Shigeki, Kosuke Kurashige, and Jun-ichiro Toriwaki.
``Rendering Gems with Asterism or Chatoyancy.'' \B The Visual Computer\},
Vol. 2, 1986, p. 307-312. [Other Phenomena]

\iYOK88\} Yokoi, Shigeki, and Jun-ichiro Toriwaki. ``Realistic Expressions of
Solids with Feeling of Material.'' \B Computer Science \& Technologies: Japan
Annual Reviews in Electronics, Computers \& Telecommunications\}, Vol. 18,
1988, p. 273-288. [Other Phenomena]

\iYOU86\} Youssef, Saul. ``A New Algorithm for Object Oriented Ray Tracing.''
\B Computer Vision, Graphics, and Image Processing\}, Vol. 34, 1986, p. 125-137.
[CSG]

\iYOU87\} Youssef, Saul. ``Vectorized Simulation and Ray Tracing.'' Technical
report FSU-SCI-87-63, Supercomputer Computations Research Institute, October,
1987. [Machines for Ray Tracing]

\iYOU88\} Youssef, Saul. ``Generalized Ray Tracing and Point Location.''
Technical report FSU-SCI-88-72, Supercomputer Computations Research Institute,
1988. [Yet-To-Be-Classified]
 
\iYUA88\} Yuan, Ying, Tosiyasu L. Kunii, Naota Inamoto, and Lining Sun.
``GemstoneFire: Adaptive Dispersive Ray Tracing of Polyhedrons.'' \B The Visual
Computer\}, Vol. 4, 1988, p. 259-270. [Other Phenomena]