\documentstyle{article}
\pagestyle{myheadings}
\oddsidemargin=0in
\evensidemargin=0in
\topmargin=-0.6in
\textwidth=6.0in
\textheight=9.5in
\newcommand{\mk}{\medskip}
\newcommand{\bk}{\bigskip \noindent $\bullet$ \mbox{\ }}
\begin{document}
\title{Ray Tracing Abstracts Survey}
\author{Tom Wilson \\ Center for Parallel Computation \\ University of Central
Florida \\ P.O. Box 25000 \\ Orlando, FL 32816-0362 \\ wilson@cs.ucf.edu}
\date{}
\maketitle
\section{Introduction}
This document contains the abstracts of the ray tracing papers that have been
added to the collection since the last release. The new papers are, in no
particular order:
\section{New Papers}
\bk
Sabella, Paolo. ``A Rendering Algorithm for Visualizing 3D Scalar
Field.'' {\em Volume Visualization}, IEEE Computer Society Press Tutorial,
1991, p. 160-167. Also appears in {\em SIGGRAPH '88}, p. 51-58.
\label{SAB91}
\mk
This paper presents a ray tracing algorithm for rendering 3D scalar fields. An
illumination model is developed in which the field is characterized as a
varying density emitter with a single level of scattering. This model is
equivalent to a particle system in which the particles are sufficiently small.
Along each ray cast from the eye, the field is expressed as a function of the
ray parameter. The algorithm computes properties of the field along the ray
such as the attenuated intensity, the peak density, and the center of gravity,
etc. These are mapped into HSV color space to produce an image for
visualization.
Images are produced in this manner are perceived as a varying density 'cloud'
where color highlights the computed attributes. The application of this
technique is demonstrated for visualizing a three dimensional seismic data set.
\bk
Samet, Hanan. ``Hierarchical Data Structures and Algorithms for
Computer Graphics - Part II: Applications.'' {\em Volume Visualization}, IEEE
Computer Society Press Tutorial, 1991, p. 72-88. Also appears in {\em IEEE
CG\&A}, July 1988, p. 59-75.
\label{SAM91}
\mk
This is the second part of a two-part overview of the use of hierarchical data
structures and algorithms in computer graphics. The focus of Part I was on
fundamentals. Part II focuses on advanced applications. Emphasis is on the
octree, and the applications are primarily display methods. Topics include use
of the quadtree as a basis for hidden-surface algorithms, parallel and
perspective projection methods to display a collection of objects represented
by an octree, and the use of octrees to facilitate such image-rendering
techniques as ray tracing and radiosity.
\bk
Woo, Andrew. ``Ray Tracing Polygons Using Spatial Subdivision.'' {\em
Graphics Interface '92}, p. 184-191.
\label{WOO92}
\mk
Ray tracing consumes a lot of computational resources to render images. This
expense usually lies in the ray-surface intersection tests. If the surfaces
were polygonal, then we should be able to apply more polygon-specific
optimizations to partially cull intersections. Our ray tracer uses a non-memory
intensive, voxel traversal intersection culler to assist in such optimizations.
\bk
Schr\"{o}der, Peter, and Steven M. Drucker. ``A Data Parallel
Algorithm for Raytracing of Heterogeneous Databases.'' {\em Graphics Interface
'92}, p. 167-175.
\label{SCH92}
\mk
We describe a new data parallel algorithm for raytracing. Load balancing is
achieved through the use of {\em processor allocation}, which continually
remaps available resources. In this manner heterogeneous databases are handled
without problems of low resource usage. The proposed approach adapts well to
both extremes: a small number of rays and a large database; a large number of
rays and a small database. The algorithm scales linearly--over a wide range--in
the numbgr of rays and available processors. We present an implementation on
the Connection Machine CM2 system and provide timings.
\bk
Jevans, David A. ``Object Space Temporal Coherence for Ray Tracing.''
{\em Graphics Interface '92}, p. 176-183.
\label{JEV92}
\mk
A method is presented for exploiting object space temporal coherence to speed
up ray tracing of animation sequences where the camera remains static. The
object space is subdivided with a hierarchical voxel grid structure. Each voxel
keeps a list of the rays that pass through it when the first frame of a
sequence is rendered. To render a successive frame, only rays that passed
through voxels in which an object has moved are retraced. The method speeds up
ray tracing of a test animation sequence by nearly a factor of four.
The method is easily adapted to work with any spatial subdivision technique.
The memory requirements of the method are low.
\bk
Paglieroni, David W., and Sidney M. Petersen. ``Parametric Height
Field Ray Tracing.'' {\em Graphics Interface '92}, p. 192-200.
\label{PAG92}
Height field ray tracing is one approach to photorealistic visualization of
terrain. {\em Parametric methods}, which fall into a new class of height fields
ray trace methods, are introduced. The height field is horizontally sliced into
evenly spaced cross-sections. For each cross-section, the Euclidean distance
from each point to the nearest point where the slice cuts through terrain is
computed off-line. These planes of distance values are condensed into
{\em parameter planes} that encode cones of empty space above each height field
cell, where cone width is bounded by the terrain relief. Parametric ray tracing
occurs along intersections betwen rays and these cones. Parametric methods are
shown to be memory efficient and often much faster than the other popular
height field ray trace methods.
\bk
Mitchell, Don, and Pat Hanrahan. ``Illumination from Curved
Reflectors.'' {\em SIGGRAPH '92}, p. 283-291.
\label{MIT92}
\mk
A technique is presented to compute the reflected illumination from curved
mirror surfaces onto other surfaces. In accordance with Fermat's principle,
this is equivalent to finding extremal paths from the light source to the
visible surface via the mirrors. Once pathways of illumination are found,
irradiance is computed from the Gaussian curvature of the geometrical
wavefront. Techniques from optics, differential geometry, and interval
analysis are applied to this problem in global illumination.
\bk
Hui, K. C., and S. T. Tan. ``Display Techniques and Boundary
Evaluation of a Sweep-CSG Modeller.'' {\em The Visual Computer}, Vol. 8, 1991,
p. 18-34.
\label{HUI91}
\mk
Among the various techniques for displaying solid objects, ray tracing is the
most popular method for sweep-generated objects, owing to its simplicity and
effectiveness. The main problem in ray tracing is to find the point of
intersection between the ray and the object. By taking consideration of the
special features of a surface generated by a sweep, the ray/object intersection
problem can be reduced to a 2-D planar problem. This paper presents a
ray-casting technique for displaying Sweep-CSG-represented solids. This
technique works directly on the Sweep-CSG representation and does not require
explicit boundary information. Boundary information is, however, essential for
line-drawing outputs. In this paper, boundary-evaluation techniques for
obtaining edges of a Sweep-CSG solid are described. Special techniques for
evaluating the boundaries of a solid are also discussed.
\bk
Hsiung, Ping-Kang, and Robert Thibadeau. ``Accelerating ARTS.'' {\em
The Visual Computer}, Vol. 8, 1992, p. 181-190.
\label{HSI92}
A major fraction of ray-tracing computation time is spent on ray-object
intersection calculation. To reduce this calculation cost, one method, ARTS,
subdivides the 3-D object space into voxels and uses a 3-D line-drawing
routine to simulate ray propagation in the subdivided space to select objects
for intersection testing. Finer space subdivision gives better object selection
resolution and few ray-object tests. However, as the subdivision increases, the
improvement is offset by a linear degradation of the line-drawing-routine
efficiency and a cubic growth of the memory requirement. We solve these time
and memory scalability problems in ARTS using an adaptive 3-D line-drawing
algorithm, which traverses space with multiple step-sizes, and a hybrid
database that employs both the octree and the 3-D array data structures. The
space traversal cost in our solution grows logarithmically with the subdivision
increase, and the memory requirement grows only linearly.
\bk
Wilson, Tom, and Narsingh Deo. ``Acceleration Schemes for Ray Tracing.''
Technical Report CS-TR-92-22, Department of Computer Science, University of
Central Florida, September 1992.
\label{WIL92a}
\mk
This paper surveys the many ray tracing acceleration schemes. We concentrate on
techniques that construct hierarchies of bounding volumes and/or perform
spatial subdivision. Also included are techniques that apply to certain
situations: ray reduction schemes, and primary ray and shadow ray accelerators.
Then, we discuss comparisons between these acceleration techniques. Finally,
we survey parallel ray tracing acceleration schemes on special-purpose machines
and on general-purpose MIMD, SIMD, and vector machines.
\bk
Wilson, Tom, and Narsingh Deo. ``Comparing Extent Tracing to Other Ray Tracing
Accelerators.'' Technical Report CS-TR-92-21, Department of Computer Science,
University of Central Florida, September 1992.
\label{WIL92b}
\mk
This report examines the feasibility of a new ray-tracing acceleration scheme
called {\em extent tracing} by comparing it to some established techniques on
established benchmark scenes. The other techniques implemented for comparison
are binary space-partitioning (BSP) tree, hierarchical tree of extents (HTE),
octree, and uniform subdivision. The statistics used in the comparison are the
execution times, memory requirements, object intersections per ray, bounding
volume intersections per ray, and voxels traversed per ray.
\bk
Wilson, Tom, and Narsingh Deo. ``Extent Tracing: Algorithm and
Implementation.'' Technical Report CS-TR-92-34, Department of Computer Science,
University of Central Florida, December 1992.
\label{WIL92c}
\mk
This paper describes a new ray tracing acceleration algorithm called {\em
extent tracing}. The algorithm works on a structure that is conceptually
related to a hierarchical tree of extents (HTE), but does not require the
hierarchy. To speed up extent tracing, spatial subdivision is added, resulting
in a nonuniform subdivision grid. Implementation details and the results of
comparisons to some other established acceleration techniques are given.
\bk
Yagel, Roni, Daniel Cohen, and Arie Kaufman. ``Discrete Ray
Tracing.'' {\em IEEE CG\&A}, September 1992, p. 19-28.
\label{YAG92}
\mk
[No abstract. The following is taken from the Conclusions]
Our new ray tracing approach, RRT, in its basic version ray traces voxelized
scenes in record speeds, at the price of negligible degradation in image
quality. One can progressively refine the image by employing the more
sophisticated variations of the algorithm, which employ supersampling and
intersection verification. Even the processing time of the algorithm's most
elaborate variation proves attractive compared to existing techniques, with
comparable image quality. RRT especially suits complex scenes and constructive
solid geometry. It also offers ray tracing for photorealism of sampled and
computed voxel data sets, or mixtures thereof with synthetic models.
\bk
Julian, B. R., and D. Gubbins. ``Three-Dimensional Seismic Ray
Tracing.'' {\em Journal of Geophysics}, Vol. 43, 1977, p. 95-113.
\label{JUL77}
\mk
Two methods for tracing seismic rays between 2 given end points through three
dimensional, continuously varying velocity structures are available. This paper
describes and compares them for problems of practical interest and for
analytical ray paths through an idealized velocity structure. One method
involves ``shooting'' the ray from one point with a given starting direction
and then modifying this starting direction until the ray emerges at the desired
target, while the other method involves ``bending'' an initial path between
the end points until it satisfies the principal of stationary time. For most
of the models investigated, ``bending'' is computationally faster than
``shooting'' by a factor of 10 or more. The ``bending'' method can be modified
to deal with discontinuities in the velocity model, and can also be adapted for
use in conjunction with a table of distances as a function of ray parameter
when the three dimensional anomaly influences only a small fraction of the
total ray path. The geometrical spreading effect on the amplitude of the ray
may be retrieved easily from the ``bending'' solution.
\bk
Nolet, G. ``Seismic Wave Propagation and Seismic Tomography.'' {\em Seismic
Tomography}, Guust Nolet (ed.), D. Reidel Publishing Company, Boston, Mass.,
1987, p. 1-23.
\label{NOL87}
\mk
This chapter develops the basic principles of seismic tomography and serves as
a general introduction to this book.
\bk
Wielandt, E. ``On the Validity of the Ray Approximation for Interpreting Delay
Times.'' {\em Seismic Tomography}, Guust Nolet (ed.), D. Reidel Publishing
Company, Boston, Mass., 1987, p. 85-98.
\label{WIE87}
\mk
[Excerpt from Abstract]
This chapter deals with the influence of diffracted waves on tomographic
observations. Probably most workers in tomography are aware of the existence
of such waves and of their potential to interfere with the direct wave on
which the tomographic interpretation is based. Strong diffraction effects are
expected when the scale of heterogeneity is in the order of the seismic
wavelength, but the smallest detail one wants to resolve with seismic
tomography is typically one or two orders of magnitude larger. Can we safely
neglect diffraction in this case?
\bk
Jobert, N., and G. Jobert. ``Ray Tracing for Surface Waves.'' {\em Seismic
Tomography}, Guust Nolet (ed.), D. Reidel Publishing Company, Boston, Mass.,
1987, p. 275-300.
\label{JOB87}
\mk
[Excerpt from Introduction]
Surface waves (at least the fundamental mode, see below) are the latest
arrivals on the seismic record at a given epicentral distance. On classical
records, thehy show up as long-period oscillations, predominating in the
record for shallow earthquakes and distances larger than a thousand
kilometers. Their relative importance increases with the distance, which can
be explained by their 2-dimensional propagation in a direction parallel to
the surface of the earth. Indeed they are guided waves with standing wave
properties in a direction normal to this surface: along this direction the
displacements are in phase at all depths. Thus their geometrical spreading, as
guided waves, is less than that of body waves which propagate in 3 dimensions.
\bk
Kunii, T. L., S. Nishimura, and T. Noma. ``The Design of a Parallel Processing
System for Computer Graphics.'' {\em 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.
\label{KUN89}
\mk
This chapter proposes a novel approach to designing an application-oriented
parallel processing system for computer graphics. In our approach, we divide
each problem into tasks, represent it with a directed acyclic graph (task
graph) and determine the assignment of tasks to processors. To determine the
task assignment, we introduce a newly developed task assignment algorithm,
which considers both processing cost and communication cost. The designing of
systems for ray tracing is described as an example of our approach.
\bk
Crow, F. C., G. Demos, J. Hardy, J. McLaughlin, and K. Sims. ``3D Image
Synthesis on the Connection Machine.'' {\em 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.
\label{CRO89}
\mk
Supercomputers are coming into wider use for generating realistic imagery for
commercial animation, special effects, and scientific simulation. The
Connection Machine requires a more radical rethinking of rendering algorithms
than previous supercomputers since it is not intended to function as a scalar
processor. A fascinating mix of changes from conventional approaches is
emerging. Some procedures can run virtually unchanged while others must be
turned completely inside out.
We have confidence, at this rather early point, in the viability of the
Connection Machine as an architecture for high-end computer graphics. For
complex scenes resulting in at least tens of thousands of polygons per frame,
most steps of the rendering pipeline can make effective use of the massive
number of processors available.
Early approaches to massively parallel graphics systems have focused on
processor-per-pixel organizations. We show that a dynamic mix of
organizations, including processor-per-pixel, processor-per-vertex, and
processor-per-polygon are necessary. Additionally, we note that an apparent
consequence of the style of algorithm enforced by the Connection Machine is
an enormously increased appetite for memory.
We are currently implementing a rendering system on a frequently upgraded
Connection Machine installation at Whitney/Demos Productions. While the small
memory of the first generation Connection Machine, CM-1, limited early
experiments, the second generation Connection Machine, CM-2, has provided
interesting experience toward understanding massively parallel computation
applied to 3D image synthesis.
\bk
Hollasch, Steven R. {\em Four-Space Visualization of 4D Objects}, Masters
Thesis, Arizona State University, 1991.
\label{HOL91}
\mk
In the field of scientific visualization, the term ``four dimensional
visualization'' usually refers to the process of rendering a three dimensional
field of scalar values. While this paradigm applies to many different data
sets, there are also uses for visualizing data that correspond to actual
four-dimensional structure. Four dimensional structures have typically been
visualized via wireframe methods, but this process alone is usually
insufficient for an intuitive understanding; all but the most simple datasets
easily overwhelm the viewer. This research covers the visualization of four
dimensional objects through wireframe methods with extended visualization cues,
and through raytracing methods. Both the wireframe and raytracing methods
employ true four-space viewing parameters and geometry. The raytracing approach
easily solves the hidden surface and shadowing problems of 4D objects, and
yields an image in the form of a three-dimensional field of RGB values, which
can be rendered with a variety of existing methods. The 4D raytracer also
supports true four-dimensional lighting, reflections, and refractions.
\bk
\v{C}erven\'{y}, V. ``Ray Tracing Algorithms in Three-Dimensional Laterally
Varying Layered Structures.'' {\em Seismic Tomography}, Guust Nolet (ed.),
D. Reidel Publishing Company, Boston, Mass., 1987, p. 99-133.
\label{CER87}
\mk
[Excerpt from Introduction]
This chapter presents a concise review of recent methods of ray tracing and
travel time computations of high-frequency seismic body wave propagating in
three-dimensional laterally varying isotropic layered structures. Large
attention is devoted mainly to {\em initial value ray tracing}, in which a
single ray under consideration is specified by its initial point and by the
initial direction of the ray at that point. The numerical, analytic, and cell
simple algorithms are obtained for the ray tracing in the ``{\em quadratic
slowness}'' model, in which the quadratic slowness $(1/V^{2})$ is used instead
of the propagation velocity $V$. In Section 6, the ray tracing system is
rewritten into an arbitrary curvilinear orthogonal coordinate system, and in
Section 7 into a spherical coordinate system. In all these cases, the ray
tracing system is supplemented by the appropriate reflection/transmission laws
which allow it to perform the ray tracing and the travel time computations even
{\em across arbitrary curved interfaces}.
\bk
Schr\"{o}der, Peter, and James B. Salem. ``Fast Rotation of Volume Data on
Data Parallel Architectures.'' ?.
\label{SCH??}
\mk
Data parallel computer architectures hold great promises for high performance
computing. Volume visualization (raytracing) is an application that can
greatly benefit from these architectures. We describe an algorithm for
rendering of orthographic views of volume data on such architectures. In
particular the problem of rotating the volume in regard to the communication
overhead associated with finely distributed memory is analyzed. We extend an
earlier technique (shear decomposition) to 3D and show how this can be mapped
onto a data parallel architecture using only grid communication during the
resampling associated with the rotation. The rendering uses efficient parallel
computation constructs that allow us to use sophisticated shading models and
still maintain high speed throughout. This algorithm has been implemented on
the Connection Machine parallel supercomputer and is used in an interactive
volume rendering application, with multiple frame per second performance.
\bk
Moser, T. J. ``Shortest Path Calculation of Seismic Rays.'' {\em Geophysics},
Vol. 56, \# 1, 1991, p. 59-67.
\label{MOS91}
\mk
Like the traveling salesman who wants to find the shortest route from one city
to another in order to minimize his time wasted on traveling, one can find
seismic raypaths by calculating the shortest traveltime paths through a network
that represents the earth. The network consists of points that are connected
with neighboring points by connections as ``long'' as the traveltime of a
seismic wave along it. The shortest traveltime path from one point to another
is an approximation to the seismic ray between them, by Fermat's principal.
The shortest path method is an efficient and flexible way to calculate the
raypaths and traveltimes of first arrivals to all points in the earth
simultaneously. There are no restrictions of classical ray theory: diffracted
raypaths and paths to shadow zones are found correctly. There are also no
restrictions to the complexity or the dimensionality of the velocity model.
Furthermore, there are no problems with convergence of trial raypaths toward
a specified receiver nor with raypaths with only a local minimal traveltime.
Later arrivals on the seismogram, caused by reflections on interfaces or by
multiples, can be calculated by posing constraints to the shortest paths. The
computation time for shortest paths from one point to all other points of the
networks is almost linearly dependent on the number of points. The accuracy of
the results is quadratically dependent upon the number of points per coordinate
direction and the number of connections per point.
\bk
Pellegrini, Marco. ``Stabbing and Ray Shooting in 3 Dimensional Space.''
{\em Proceedings of the 6th Annual Symposium on Computational Geometry},
1990, p. 177-186.
\label{PEL90}
\mk
In this paper we consider the following problems: given a set $T$ of triangles
in 3-space, with $|T| = n$,
a) answer the query ``given a line $l$, does $l$ stab the set of triangles?''
({\em query problem}).
b) find whether a stabbing line exists for the set of triangles ({\em existence
problem}).
c) Given a ray $\rho$, which is the first triangle in $T$ hit by $\rho$?
The following results are shown:
1. There is an $\Omega(n^{3})$ lower bound on the descriptive complexity of the
set of all stabbers for a set of triangles.
2. The existence problem for triangles on a set of planes with $g$ different
plane inclinations can be solved in $O(g^{2}n^{2}\log n)$ time (Theorem 2).
3. The query problem is solvable in quasiquadratic $O(n^{2+\epsilon})$
preprocessing and storage and logarithmic $O(\log n)$ query time (Theorem 4).
4. If we are given $m$ rays we can answer ray shooting queries in
$O(m^{5/6-\delta}n^{5/6+5\delta}\log^{2} n + m \log^{2} n + n\log n \log m)$
randomized expected time and $O(m+n)$ space (Theorem 5).
5. In time $O((n+m)^{5/3+4\delta})$ it is possible to decide whether two
nonconvex polyhedra of complexity $m$ and $n$ intersect (Corrolary 1).
6. Given $m$ rays and $n$ axis-oriented boxes we can answer ray shooting
queries in randomized expected time $O(m^{3/4-\delta}n^{3/4+3\delta}\log^{4} n
+ m \log^{4} n + n\log n \log m)$ and $O(m+n)$ space (Theorem 6).
\bk
Pitot, Paul. ``The Voxar Project.'' {\em IEEE CG\&A}, January 1993, p. 27-33.
\label{PIT93}
\mk
[Taken from Introduction]
The Voxar project has attempted to define a parallel processing model to
simulate 3D physical phenomena. This article discusses an implementation of the
ray tracing algorithm baased on this model.
The idea behind our project is an analogy between the way light rays interact
with objects in the physical world and the manner in which traced rays run
through simulated space. Just as a point in space reacts to a light beam, our
voxels react to rays through the modified behavior of their corresponding
processors, hence the project name Voxel Architecture. The implementation of
such a machine required some compromises, but we have done our best to preserve
the basic idea.
\bk
Semwal, Sudhanshu K., Charulata K. Kearney, and J. Michael Moshell. ``Ray
Tracing Using the Slicing Extent Technique.'' {\em 1992 International
Conference on 3D Graphics (?)}, p. ?.
\label{SEM92}
\mk
We present a novel approach to ray tracing called the Slicing Extent Technique
(SET) and its variations. SET partitions object space with slicing planes
perpendicular to all three axes. Slicing planes are divided into two
dimensional rectangular cells, which contain pointers to nearby objects. The
novelty of SET is that rather than using a collection of volumes as an extent,
SET uses a collection of planar cells and is based on analysis of projections
of objects onto slicing planes. These rectangular cells are used to quickly
traverse through the sparse area of the scene and also provide further
subdivision in the highly populated dense area. These 2D cells can also define
tighter extents.
In comparison to the existing space subdivision techniques for ray tracing, SET
avoids tree traversal and multiple ray-object intersections. It guarantees no
increase in image generation time when number of cells per slice increase in
multiples of four. There is no reorganization when new objects arrive and
preprocessing to create slices is inexpensive.
\bk
Dauenhauer, David E., and Sudhanshu K. Semwal. ``Approximate Ray Tracing.''
{\em Proceedings of Graphics Interface '90}, p. 75-82.
\label{DAU90}
\mk
We provide a general technique for all ray tracing space subdivision methods to
perform what we term ``Approximate Ray Tracing.'' An implementation of the
Approximate Ray Tracing called the Approximate Slicing Extent Technique or ASET
is provided. ASET checks only one ray-polygon intersection per cell along the
path of the ray. All other ray-object intersections are eliminated.
While the benefits of standard area subdivision techniques have proven to be
fairly optimal, our experiments have shown an average of fifteen to fifty
percent reduction in the time required to ray trace approximate images. Time
savings are expected to be greater when more complex scenes are rendered.
Irrespective of the scene complexity, ASET adds only a constant amount of
memory overhead.
\bk
Logan, James, Sudhanshu K. Semwal, and J. Michael Moshell. ``The Modified
Slicing Extent Technique of Subdivision for Ray Tracing.'' ?.
\label{LOG??}
\mk
Currently there are many techniques for generating realistic images in the
field of computer graphics. Ray tracing is a popular method for generating
realistic images. The inherent computational complexity of ray tracing makes
image generation a very slow process. Space subdivision techniques have been
suggested to speed up the ray tracing process. The {\em Modified Slicing Extent
Technique} or MSET is presented as an alternative to existing space subdivision
techniques. Comparisons are made with the octree and grid methods for ray
tracing. These comparisons are based on preprocessing times, rendering times,
memory usage and the number of ray-object intersections. Our results show the
proposed MSET method is fast and computationally efficient.
\bk
Bronsvoort, Willem F., Frederik W. Jansen, and Frits H. Post. ``Design and
Display of Solid Models.'' {\em Advances in Computer Graphics VI -- Images:
Synthesis, Analysis, and Interaction}, G\'{e}rald Garcia and Ivan Herman
(eds.), Springer-Verlag, 1991, p. 1-57.
\label{BRON91}
\mk
Solid modelling plays an important role in CAD/CAM and other advanced
applications of 3D graphics. This survey presents an overview of graphics
techniques for the design, fast display, and high-quality rendering of solid
models ({\em i.e.\ Graphics for Solid Modelling}). Emphasis will be on
techniques for Constructive Solid Geometry (CSG).
After an introduction on representation techniques, the following topics on
interactive design of solid models will be covered: input and editing curves,
surfaces and solids, assembly modelling, parametrization, constraints,
modelling languages and direct manipulation. The second part of the survey will
discuss display techniques: ray tracing, scanline and depth buffer algorithms,
CSG classification techniques and efficiency-improving methods.
\bk
Cohen, Michael F., and James S. Painter. ``State of the Art in Image
Synthesis.'' {\em Advances in Computer Graphics VI -- Images: Synthesis,
Analysis, and Interaction}, G\'{e}rald Garcia and Ivan Herman (eds.),
Springer-Verlag, 1991, p. 59-111.
\label{COH91}
\mk
[Excerpt from the Introduction]
Creating a realistic synthetic image on a computer requires two steps: (1)
describing the geometry of the environment to be rendered and the material
properties of the objects which make up the environment, and (2) simulating the
propagation of light through the synthetic environment and displaying the
results of the simulation.
The technology is not yet capable of creating images as fantastic as those of
Bosch and Escher, but the shortcomings can probably be placed primarily in the
first task, that of describing the environment to the computer. The focus of
this tutorial will be on the second part of the problem, that of simulating and
displaying the interaction of light in the synthetic environment.
\bk
Crow, Franklin C. ``Parallel Computing for Graphics.'' {\em Advances in
Computer Graphics VI -- Images: Synthesis, Analysis, and Interaction},
G\'{e}rald Garcia and Ivan Herman (eds.), Springer-Verlag, 1991, p. 113-140.
\label{CRO91}
\mk
The cost of computing cycles for state-of-the-art imagery continues to rise
exponentially. Fortunately, so does the cost-effectiveness of state-of-the-art
computer processors. However, that leaves us continually several orders of
magnitude short on processing power if we wish to make state-of-the-art images
in real-time or even interactive time. An obvious answer to this dilemma lies
in parallel processing. As massively parallel supercomputers become a reality
and promise a future including massively parallel everyday computers, it is no
longer a silly exercise to consider how to use thousands or even millions of
processors in computer graphics.
Many algorithms from traditional computer graphics lend themselves to parallel
implementation. However, there are many ways in which the remaining algorithms
can prevent a system from realizing the potential of a massively parallel
computing resource. Many parallel architectures for graphics have been proposed
and a few have even been available commercially in the past few years. A close
look at these architectures usually reveals underlying assumptions about the
nature of computations for graphics which may not always prove true.
\bk
Kilgour, A. C. ``Techniques for Modelling and Displaying 3D Scenes.'' {\em
Advances in Computer Graphics II}, F. R. A. Hopgood, R. J. Hubbold, and
D. A. Duce (eds.), Springer-Verlag, 1986, p. 55-113.
\label{KIL86}
\mk
In this article basic data structures for representing 3D objects are
described, ranging from {\em ad hoc} methods which are quite acceptable for
simple applications, through general-purpose methods such as Baumgart's
winged-edge structure, capable of representing the topology of any polyhedron,
to the set theoretic structures generated by ``constructive solid geometry''
(CSG) modelling systems. Quadric surfaces such as spheres and cylinders are
discussed, but general sculptured surfaces based on B\'{e}zier or B-spline
patches are not covered. The emphasis is on techniques which can be readily
applied to simple cases.
The choice of an appropriate rendering technique is closely linked to the
modelling method adopted. Conventional rendering techniques are described for
objects which can be readily reduced to a set of polygonal facets. These
techniques include hidden surface removal and scan conversion, which are often
closely linked. The need for antialiasing on a raster display is discussed, and
suitable methods described. Halftoning techniques, which allow the apparent
number of intensity levels or colors to be increased at the cost of some
reduction in resolution, are of importance for output both on raster displays
and hard copy devices such as laser printers, and suitable methods are
described in detail.
The use of ray tracing as an alternative to conventional rendering techniques
is discussed, and it relationship explained to the class of model being used
(boundary representation or CSG).
The realism of a 3D picture is heavily dependent on the accuracy with which the
illumination of the constituent surfaces is modelled. A range of approximations
of increasing accuracy is presented for carrying out the illumination
calculations, and the tradeoff between realism and computational cost
explained.
Algorithms and data structures are expressed throughout either in ``structured
English,'' or, where more detail is required, in C, which is rapidly
establishing itself as ``the thinking person's Fortran.'' As far as possible
the C code has been constrained to look like Pascal, as an aid to readability.
\bk
Murakami, Koichi, and Katsuhiko Hirota. ``Incremental Ray Tracing.'' {\em
Photorealism in Computer Graphics}, K. Bouatouch, and C. Bouville (eds.),
Springer-Verlag, 1992, p. xiii-xiv, 17-32.
\label{MUR92}
\mk
We have developed a method to reduce the ray tracing time that recomputes or
updates only the changed parts of the image for a fixed viewpoint for a
dynamic sequence of images. This method enables a designer to make small
changes in geometry or surfaces properties of a ray-traced scene without
recalculating the entire image. The intersection tree is extended to contain
the intersection point, surface normal, and related data that record the path
through which the ray propagated using a voxel partition scheme. These
descriptions are then used during the update to quickly determine which parts
of the image need recomputation and to reduce the number of recomputations. The
key idea behind the method is to localize the influence of changed objects
using the voxel partition and to minimize the access cost of the data
structures. Testing if a ray is changed by the changed object is done with a
hash index, which represents the ray's path. Intersection recalculation to
determine a changed ray's new visible point can be reduced with information
saved in the intersections. The optimal tree traversal algorithm limits the
parts of developed on the {\em CAP (Cellular Array Processor)} parallel
processor. An implementation approach that accounts for data storage and load
balancing is also presented. The results demonstrate great performance
improvements over calculating an entirely new rendering. With this method ray
tracing may become practical for some computer graphics applications, such as
CAD and animation which require high-quality images.
\bk
Biard, Luc. ``Parametric Surfaces and Ray Tracing.'' {\em Photorealism in
Computer Graphics}, K. Bouatouch, and C. Bouville (eds.), Springer-Verlag,
1992, p. 33-53.
\label{BIA92}
\mk
A new method for ray tracing polynomial and rational parametric surfaces is
presented. The algorithm we describe is based on algebraic tools
(implicitization and inversion) and does not proceed by a previous
approximation of the surface. Each surface can be associated with numerical
matrices in such a way that operations to be done on surfaces can be
translated into operations on the corresponding matrices and treated by
numerical matrix techniques. These matrices are an implicit version of a given
parametric surface and contain all algebraic and topological informations about
it.
\begin{thebibliography}{999}
\bibitem{BIA92}
Biard, Luc. ``Parametric Surfaces and Ray Tracing.'' {\em Photorealism in
Computer Graphics}, K. Bouatouch, and C. Bouville (eds.), Springer-Verlag,
1992, p. 33-53.
\{\pageref{BIA92}\}
\bibitem{BRON91} Bronsvoort, Willem F., Frederik W. Jansen, and Frits H. Post.
``Design and Display of Solid Models.'' {\em Advances in Computer Graphics VI
-- Images: Synthesis, Analysis, and Interaction}, G\'{e}rald Garcia and Ivan
Herman (eds.), Springer-Verlag, 1991, p. 1-57.
\{\pageref{BRON91}\}
\bibitem{CER87} \v{C}erven\'{y}, V. ``Ray Tracing Algorithms in
Three-Dimensional Laterally Varying Layered Structures.'' {\em Seismic
Tomography}, Guust Nolet (ed.), D. Reidel Publishing Company, Boston, Mass.,
1987, p. 99-133.
\{\pageref{CER87}\}
\bibitem{COH91} Cohen, Michael F., and James S. Painter. ``State of the Art in
Image Synthesis.'' {\em Advances in Computer Graphics VI -- Images: Synthesis,
Analysis, and Interaction}, G\'{e}rald Garcia and Ivan Herman (eds.),
Springer-Verlag, 1991, p. 59-111.
\{\pageref{COH91}\}
\bibitem{CRO89} Crow, F. C., G. Demos, J. Hardy, J. McLaughlin, and K. Sims.
``3D Image Synthesis on the Connection Machine.'' {\em 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.
\{\pageref{CRO89}\}
\bibitem{CRO91} Crow, Franklin C. ``Parallel Computing for Graphics.'' {\em
Advances in Computer Graphics VI -- Images: Synthesis, Analysis, and
Interaction}, G\'{e}rald Garcia and Ivan Herman (eds.), Springer-Verlag, 1991,
p. 113-140.
\{\pageref{CRO91}\}
\bibitem{DAU90} Dauenhauer, David E., and Sudhanshu K. Semwal. ``Approximate
Ray Tracing.'' {\em Proceedings of Graphics Interface '90}, p. 75-82.
\{\pageref{DAU90}\}
\bibitem{HOL91} Hollasch, Steven R. {\em Four-Space Visualization of 4D
Objects}, Masters Thesis, Arizona State University, 1991.
\{\pageref{HOL91}\}
\bibitem{HSI92} Hsiung, Ping-Kang, and Robert Thibadeau. ``Accelerating ARTS.''
{\em The Visual Computer}, Vol. 8, 1992, p. 181-190.
\{\pageref{HSI92}\}
\bibitem{HUI91} Hui, K. C., and S. T. Tan. ``Display Techniques and Boundary
Evaluation of a Sweep-CSG Modeller.'' {\em The Visual Computer}, Vol. 8, 1991,
p. 18-34.
\{\pageref{HUI91}\}
\bibitem{JEV92} Jevans, David A. ``Object Space Temporal Coherence for Ray
Tracing.'' {\em Graphics Interface '92}, p. 176-183.
\{\pageref{JEV92}\}
\bibitem{JOB87} Jobert, N., and G. Jobert. ``Ray Tracing for Surface Waves.''
{\em Seismic Tomography}, Guust Nolet (ed.), D. Reidel Publishing Company,
Boston, Mass., 1987, p. 275-300.
\{\pageref{JOB87}\}
\bibitem{JUL77} Julian, B. R., and D. Gubbins. ``Three-Dimensional Seismic Ray
Tracing.'' {\em Journal of Geophysics}, Vol. 43, 1977, p. 95-113.
\{\pageref{JUL77}\}
\bibitem{KIL86} Kilgour, A. C. ``Techniques for Modelling and Displaying 3D
Scenes.'' {\em Advances in Computer Graphics II}, F. R. A. Hopgood,
R. J. Hubbold, and D. A. Duce (eds.), Springer-Verlag, 1986, p. 55-113.
\{\pageref{KIL86}\}
\bibitem{KUN89} Kunii, T. L., S. Nishimura, and T. Noma. ``The Design of a
Parallel Processing System for Computer Graphics.'' {\em 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.
\{\pageref{KUN89}\}
\bibitem{LOG??} Logan, James, Sudhanshu K. Semwal, and J. Michael Moshell.
``The Modified Slicing Extent Technique of Subdivision for Ray Tracing.'' ?.
\{\pageref{LOG??}\}
\bibitem{MIT92} Mitchell, Don, and Pat Hanrahan. ``Illumination from Curved
Reflectors.'' {\em SIGGRAPH '92}, p. 283-291.
\{\pageref{MIT92}\}
\bibitem{MOS91} Moser, T. J. ``Shortest Path Calculation of Seismic Rays.''
{\em Geophysics}, Vol. 56, \# 1, 1991, p. 59-67.
\{\pageref{MOS91}\}
\bibitem{MUR92}
Murakami, Koichi, and Katsuhiko Hirota. ``Incremental Ray Tracing.'' {\em
Photorealism in Computer Graphics}, K. Bouatouch, and C. Bouville (eds.),
Springer-Verlag, 1992, p. xiii-xiv, 17-32.
\{\pageref{MUR92}\}
\bibitem{NOL87} Nolet, G. ``Seismic Wave Propagation and Seismic Tomography.''
{\em Seismic Tomography}, Guust Nolet (ed.), D. Reidel Publishing Company,
Boston, Mass., 1987, p. 1-23.
\{\pageref{NOL87}\}
\bibitem{PAG92} Paglieroni, David W., and Sidney M. Petersen. ``Parametric
Height Field Ray Tracing.'' {\em Graphics Interface '92}, p. 192-200.
\{\pageref{PAG92}\}
\bibitem{PEL90} Pellegrini, Marco. ``Stabbing and Ray Shooting in 3 Dimensional
Space.'' {\em Proceedings of the 6th Annual Symposium on Computational
Geometry}, 1990, p. 177-186.
\{\pageref{PEL90}\}
\bibitem{PIT93} Pitot, Paul. ``The Voxar Project.'' {\em IEEE CG\&A}, January
1993, p. 27-33.
\{\pageref{PIT93}\}
\bibitem{SAB91} Sabella, Paolo. ``A Rendering Algorithm for Visualizing 3D
Scalar Field.'' {\em Volume Visualization}, IEEE Computer Society Press
Tutorial, 1991, p. 160-167. Also appears in {\em SIGGRAPH '88}, p. 51-58.
\{\pageref{SAB91}\}
\bibitem{SAM91} Samet, Hanan. ``Hierarchical Data Structures and Algorithms for
Computer Graphics - Part II: Applications.'' {\em Volume Visualization}, IEEE
Computer Society Press Tutorial, 1991, p. 72-88. Also appears in {\em IEEE
CG\&A}, July 1988, p. 59-75.
\{\pageref{SAM91}\}
\bibitem{SCH??} Schr\"{o}der, Peter, and James B. Salem. ``Fast Rotation of
Volume Data on Data Parallel Architectures.'' ?.
\{\pageref{SCH??}\}
\bibitem{SCH92} Schr\"{o}der, Peter, and Steven M. Drucker. ``A Data Parallel
Algorithm for Raytracing of Heterogeneous Databases.'' {\em Graphics Interface
'92}, p. 167-175.
\{\pageref{SCH92}\}
\bibitem{SEM92} Semwal, Sudhanshu K., Charulata K. Kearney, and J. Michael
Moshell. ``Ray Tracing Using the Slicing Extent Technique.'' {\em 1992
International Conference on 3D Graphics (?)}, p. ?.
\{\pageref{SEM92}\}
\bibitem{WIE87} Wielandt, E. ``On the Validity of the Ray Approximation for
Interpreting Delay Times.'' {\em Seismic Tomography}, Guust Nolet (ed.),
D. Reidel Publishing Company, Boston, Mass., 1987, p. 85-98.
\{\pageref{WIE87}\}
\bibitem{WIL92a} Wilson, Tom, and Narsingh Deo. ``Acceleration Schemes for Ray
Tracing.'' Technical Report CS-TR-92-22, Department of Computer Science,
University of Central Florida, September 1992.
\{\pageref{WIL92a}\}
\bibitem{WIL92b} Wilson, Tom, and Narsingh Deo. ``Comparing Extent Tracing to
Other Ray Tracing Accelerators.'' Technical Report CS-TR-92-21, Department of
Computer Science, University of Central Florida, September 1992.
\{\pageref{WIL92b}\}
\bibitem{WIL92c} Wilson, Tom, and Narsingh Deo. ``Extent Tracing: Algorithm and
Implementation.'' Technical Report CS-TR-92-34, Department of Computer Science,
University of Central Florida, December 1992.
\{\pageref{WIL92c}\}
\bibitem{WOO92} Woo, Andrew. ``Ray Tracing Polygons Using Spatial
Subdivision.'' {\em Graphics Interface '92}, p. 184-191.
\{\pageref{WOO92}\}
\bibitem{YAG92} Yagel, Roni, Daniel Cohen, and Arie Kaufman. ``Discrete Ray
Tracing.'' {\em IEEE CG\&A}, September 1992, p. 19-28.
\{\pageref{YAG92}\}
\end{thebibliography}
\end{document}