palmer@ncifcrf.gov (Thomas Palmer) (09/06/88)
This is a summary of the replies I received to my query regarding vectorizing ray-object intersection calculations. ---------------------------------------------------------------------------- >From: spencer@tut.cis.ohio-state.edu (Stephen Spencer) There was an article in IEEE CG&A about four years ago about vectorizing ray-sphere intersections on a Cyber 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 Ohio State University | spencer@hardy.cgrg.ohio-state.edu 1224 Kinnear Road, Columbus OH 43212 | spencer@tut.cis.ohio-state.edu ---------------------------------------------------------------------------- >From: mbc@a.cs.okstate.edu (Michael Carter) 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 ARPA: mbc%okstate.csnet@csnet-relay.arpa ---------------------------------------------------------------------------- >From: mcvax!tokaido.irisa.fr!priol@uunet.UU.NET (Thierry Priol -- Equipe Hypercubes) There is few work in vectorization of ray-objet intersection, one of this work has been done by Plunkett on a CDC-CYBER. The reference is : @Article(PLUNKETT85, 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. ---------------------------------------------------------------------------- >From: stan!dodge!dave@boulder.Colorado.EDU (Dave Plunkett) You might try any of: "The Vectorization of a Ray Tracing Program for Image Generation", with J.M. Cychosz and M.J. Bailey. Cyber 200 Applications Seminar, NASA Goddard, October 1983. "Ray Tracing on a Cyber 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 ---------------------------------------------------------------------------- >From: 3ksnn64@ee.ecn.purdue.edu (Joe Cychosz) I have developed a vectorized ray tracing package for the CYBER 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 Frederick, MD 21701 Arpanet: palmer@ncifcrf.gov