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

Advanced Computing Center for the Arts and Design (ACCAD)

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

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