rice@swatsun (Dan Rice) (07/15/87)
I'm in the midst of writing a ray-tracer, and I would be very interested in any clever and unusual intersection tests that people have come across. For example, one I saw recently calculated the intersection of a ray with a sphere by finding the closest approach of the ray to the center of the sphere with two dot products, and then found the actual intersection point by forming a triangle with the intersection point, the sphere center, and the point of closest approach. Other ray-tracers that I've seen calculate this intersection by solving a quadratic equation for the intersection point directly. I'm curious to see if there are similar examples of clever intersection tests beating brute- force tests. I'd appreciate examples or source, or pointers to literature about geometric intersection tests. -- - Dan Rice, Swarthmore College, Swarthmore PA 19081 ...!sun!liberty!swatsun!rice ...!seismo!bpa!swatsun!rice
markv@uoregon.UUCP (Mark VandeWettering) (07/18/87)
In article <1222@byzantium.swatsun.UUCP> rice@swatsun (Dan Rice) writes: > > I'm in the midst of writing a ray-tracer, and I would be very interested >in any clever and unusual intersection tests that people have come across. For I too am interested in computational methods for determining ray-object intersections. Please post 'em if you have got 'em, or at least mail 'em to me too. >I'm curious >to see if there are similar examples of clever intersection tests beating brute- >force tests. I'd appreciate examples or source, or pointers to literature about >geometric intersection tests. As am I. I have read a number of Kajiya's papers, and am amazed at how clever things one can be about managing these intersection calculations. I have constructed a small bibliography of references in refer format which I would be willing to post if people are interested. It has a couple of dozen references, having to do with ray tracing and clever approaches to realistic images, mostly gleaned from recent Siggraph proceedings. I would appreciate exchanging bibliographies with anyone else. >-- >- Dan Rice, Swarthmore College, Swarthmore PA 19081 >...!sun!liberty!swatsun!rice > ...!seismo!bpa!swatsun!rice | Mark VandeWettering | | member of UO-EXODOS - distributed operating system research group | | University of Oregon Computer and Information Sciences Department | | markv@uoregon.edu OR markv@uoregon.uucp |
ph@pixar.UUCP (Paul Heckbert) (07/20/87)
In article <1222@byzantium.swatsun.UUCP>, rice@swatsun (Dan Rice) writes: >... one I saw recently calculated the intersection of a ray with a sphere >by finding the closest approach of the ray to the center of the sphere with two >dot products,and then found the actual intersection point by forming a triangle >with the intersection point, the sphere center, and the point of closest >approach. Other ray-tracers that I've seen calculate this intersection by >solving a quadratic equation for the intersection point directly... This newsgroup already beat ray-polygon intersection testing into the ground, so now let's move on to spheres... The "best" computational formula I've seen for ray-sphere intersection testing is what you called the "brute force" method, and goes something like this: ------------------------------------------ #define EPSILON 1e-7 /* tolerance to roundoff errors */ /* * SphereIntersect: find intersection of ray X=P+tD (where |D|=1) * with sphere |C-X|^2 = r^2 by solving the quadratic equation: * |V-tD|^2 = t^2 - 2t(V.D) + (V.V-r^2) = 0 * where V=C-P. * The roots are: * t = V.D +- sqrt((V.D)^2 - V.V + r^2) */ SphereIntersect(P, D, C, r2, tp) double P[3], D[3]; /* ray origin point and direction */ double C[3], r2; /* sphere center and radius_squared */ double t[2]; /* t at intersection points (if any) */ { double V[3], b, disc; s m a 0 0 3 V = vsub(C, P); /* vector subtract */ 0 3 2 b = vdot(V, D); /* dot product */ 0 4 4 disc = b*b - vdot(V, V) + r2; if (disc < 0.) return 0; /* ray misses sphere */ 1 0 0 disc = sqrt(disc); 0 0 1 t[0] = b-disc; /* first root */ 0 0 1 t[1] = b+disc; /* second root */ return 2; /* return #roots */ } ------------------------------------------ The numbers under "s m a" are the #sqrts, #multiplies, and #add/subtracts, respectively. With this scheme, it takes 7 multiplies and 9 adds to determine if the ray hits the sphere, and 1 sqrt, 2 additions more to find t at both intersection points. I'd wager that this is "optimal" given this set of inputs, outputs, and operators. [ General tip to fellow optimization freaks: I've found that I can often knock off a few superfluous multiplies and divides if I use the quadratic formula: roots of x^2-2b*x+c=0 are x=b+-sqrt(b*b-c) instead of the tired old formula: roots of a*x^2+b*x+c=0 are x=(-b+-sqrt(b*b-4*a*c))/(2*a) ] These and other ray tracing issues will be discussed in the tutorial "Introduction to Ray Tracing" at SIGGRAPH in Anaheim next week by speakers: Andrew Glassner, Eric Haines, Rick Speer, Pat Hanrahan, Rob Cook, and myself. See you there. Paul Heckbert Pixar 415-499-3600 P.O. Box 13719 UUCP: {sun,ucbvax}!pixar!ph San Rafael, CA 94913 ARPA: ph%pixar.uucp@ucbvax.berkeley.edu
rice@swatsun (Dan Rice) (07/22/87)
Is it possible for non-attendees to purchase SIGGRAPH notes (not proceedings)? -- - Dan Rice, Swarthmore College, Swarthmore PA 19081 ``I hear you're mad about Brubeck... I like your eyes, I like him too...'' UUCP: ...!seismo!bpa!swatsun!rice, ...!sun!liberty!swatsun!rice CSNET: rice%swatsun.swarthmore.edu@relay.cs.net
daveb@pogo.TEK.COM (Dave Butler) (07/25/87)
Would someone who is consolidating all this information about "clever
intersection tests" please post a bibliography to the net, or at least
send me a copy.
Later,
Dave Butler
Remember: Silly is a state of Mind, Stupid is a way of Life.hiebeler@csv.rpi.edu (David Hiebeler) (08/03/87)
I also am interested in seeing this mentioned bibliography. If it is not
going to be posted, please e-mail (or any-mail) it to me as well, if possible.
Thanks in advance.
--
David Hiebeler hiebeler@csv.rpi.edu
R.D.Box 225A
Chatham, NY 12037
(518) 392-9702markv@uoregon.UUCP (Mark VandeWettering) (08/04/87)
In article <316@nysernic> hiebeler@csv.rpi.edu (David Hiebeler) writes: >I also am interested in seeing this mentioned bibliography. If it is not >going to be posted, please e-mail (or any-mail) it to me as well, if possible. > Thanks in advance. > It serves me right. I mentioned that I had a bibliography, and in looking it over, I realize that there are a few errors in it. I would like to correct these prior to posting it. I will try to do so by the 7th of August, and will post it then. My offer was also a request for papers which you have found interesting, and so far, all I have had is requests. If you have found papers which are useful, send a bibliography entry (refer format if you can) to me for inclusion. | Mark VandeWettering | | member of UO-EXODOS - distributed operating system research group | | University of Oregon Computer and Information Sciences Department | | markv@uoregon.edu OR markv@uoregon.uucp |
rice@swatsun (Dan Rice) (08/04/87)
In article <316@nysernic>, hiebeler@csv.rpi.edu (David Hiebeler) writes: > I also am interested in seeing this mentioned bibliography. If it is not > going to be posted, please e-mail (or any-mail) it to me as well, if possible. Since posting my request for intersection tests, I've received lots of letters like this one, but not much in the way of actual information. Apparently lots of us are interested, but no one really has much to say. To reiterate my original request, if anyone knows of clever intersection tests, neat ways to save a few multiplications, and so forth, please e-mail it to me, and I will summarize. -- - Dan Rice, Swarthmore College, Swarthmore PA 19081 ``I hear you're mad about Brubeck... I like your eyes, I like him too...'' UUCP: ...!seismo!bpa!swatsun!rice, ...!sun!liberty!swatsun!rice CSNET: rice%swatsun.swarthmore.edu@relay.cs.net