Summary of replies to vectorizing ray-object intersection query

Summary of replies to vectorizing ray-object intersection query

This is a summary of the replies I received to my query regarding
vectorizing ray-object intersection calculations.

----------------------------------------------------------------------------

There was an article in IEEE CG&A about four years ago about vectorizing
ray-sphere intersections on a * which included an algorithmic workup
of how it worked.

As far as ray-polygon intersection goes, the article in SIGGRAPH '87 dealing
with tesselation of polygonal objects (it had the pictures of grass and the
Statue of Liberty in it) included the algorithm for fast ray-polygon
intersection, and I did implement it and it did vectorize quite nicely.
I unfortunately no longer seem to have that piece of code, but it wasn't
difficult.  Of course you still have to do the sorting of the intersection
points but the heavy intersection calculations can be done quickly.

Stephen Spencer

----------------------------------------------------------------------------

The real problem in the inner ray tracing loop is not ray-object
intersections, but ray-bounding volume intersections.  If you refer
to the article by Kay and Kajiya from SIGGRAPH '86, they describe
a method of breaking down the OBJECT space into a hierarchical data
structure, and intersecting rays against simple bounding volumes
constructed from sets of planes.  This method queries the objects
in the order that they occur along the ray, therefore, NO SORTING IS
NEEDED.  It takes at lease three pairs of planes to completely
enclose an object, therefore this intersection calculation could be
done efficiently, in parallel (on perhaps more than one object at a
time!) on a vector machine.  Most of the time is spent in this ray-
bounding volume intersection loop, and not in the ray-object intersection
algorithms.
I realize that this is not something that the C compiler can do
on its own, but remember: no pain -- no gain.  (-:

--
Michael B. Carter
Department of Electrical and Computer Engineering, Oklahoma State University
UUCP:  {cbosgd, ea, ihnp4, isucs1, mcvax, pesnta, uokvax}!okstate!mbc

----------------------------------------------------------------------------

There is few work in vectorization of ray-objet intersection, one of this
work has been done by Plunkett on a CDC-*. The reference is :

Author="D. Plunkett and M. Bailey",
Key="Vectorisation",
Title="The Vectorisation of a Ray Tracing Algorithm for Improved Execution Speed",
Journal="IEEE Computer Graphics and Applications",
Pages="52-60",
Month="August",
Year="1985")

Personnaly, i work in ray-tracing on parallel MIMD (hypercube iPSC/2) computer.

Thierry PRIOL
Institut de Recherche en Informatique et Systemes Aleatoires
Campus de Beaulieu
35042 RENNES CEDEX
FRANCE
e-mail : mcvax!inria!irisa!priol

PS: Sorry for my poor english.

----------------------------------------------------------------------------

You might try any of:

"The Vectorization of a Ray Tracing Program for Image Generation",
with J.M. Cychosz and M.J. Bailey.
* 200 Applications Seminar, NASA Goddard, October 1983.

"Ray Tracing on a * 205",
Conference Proceedings VIM-40,
San Francisco, CA, April 1984.

"A Vectorized Ray Tracing Algorithm",
Masters Thesis,
Purdue University, West Lafayette, IN.  August 1984.

"The Vectorization of a Ray Tracing Algorithm for Improved Execution Speed",
with M.J. Bailey.  IEEE Computer Graphics and Applications,
Vol. 5, No. 8, August 1985.

The last two of these are more readily accessible.  These papers
describe my Master's research, a vectorized ray tracing algorithm for use on
csg objects that was written using explicit vector syntax on the 205.
If you have any specific questions, I'd be glad to answer any that I can.

Dave Plunkett
Solbourne Computer, Inc.
Longmont, CO 80501
(303) 772-3400
...sun!stan!dave

----------------------------------------------------------------------------

I have developed a vectorized ray tracing package for the * 205.
Part of the work is discussed in Plunketts CG&A paper.  Nelson
Max also had a paper on vectorized intersections of height fields used
to produce Carlos' Island.  Saul Youseff at Florida State has also
been doing some work using raytracing for collector plate design.

Both Plunkett and myself use a ray queue to collect rays, and then
vectorize such that serveral rays are intersected with an object.
This approach does make it difficult to implement these accelerated
ray traces such as Mike Kaplan's "Constant Time Ray Tracing".

I have a variation of Kaplan's approach that sub-divides the object
space and uses bit operators to elliminate unnecessary intersection
calculations.

Joe Cychosz

----------------------------------------------------------------------------

-Tom

Thomas C. Palmer       National Cancer Institute Supercomputer Facility
c/o PRI, Inc.          Phone: (301) 698-5797
PO Box B, Bldg. 430    Uucp: ...!uunet!ncifcrf.gov!palmer

Has anyone done any work on vectorizing ray-object intersection
calculations?  The vectorizing C compiler on a Cray X/MP will not
(automatically) vectorize loops smaller than about 5 or 6 iterations
(nor should it - the vector register load time outweighs the gain).
Typical ray tracing vector operations involve vectors of length 3 or 4.

-Tom

Thomas C. Palmer       NCI Supercomputer Facility
c/o PRI, Inc.          Phone: (301) 698-5797
PO Box B, Bldg. 430    Uucp: ...!uunet!ncifcrf.gov!palmer