palmer@ncifcrf.gov (Thomas Palmer) (08/26/88)
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 Frederick, MD 21701 Arpanet: palmer@ncifcrf.gov
spencer@tut.cis.ohio-state.edu (Stephen Spencer) (08/27/88)
In article <594@fcs280s.ncifcrf.gov>, palmer@ncifcrf.gov (Thomas Palmer) writes > > Has anyone done any work on vectorizing ray-object intersection > calculations? 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
mbc@a.cs.okstate.edu (Michael Carter) (08/29/88)
In article <594@fcs280s.ncifcrf.gov>, palmer@ncifcrf.gov (Thomas Palmer) writes: > > 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. > 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