watson@ames.arpa (John S. Watson) (09/10/87)
Hi Folks, I've been writing a ray-tracer for a few years now, adding a few features to it every once in a while. And now the time has come to add a "constant-time" feature, because as the number of objects in a scene gets larger, the time my raytracer takes to render an image grows radically. Currently, its finding the intersection of every ray with every object. :-( Anyway, I know there have been a few variations of the constant-time algorithms around, and what I need to know is, what is the _best_, i.e. simplest, most effiecent, etc, ... version to implement. At SIGGRAPH'85, and I read about Kaphan's version "Space Tracing, a Constant Time Ray-Tracer", [course notes], but I suppose there might be a newer, better variation since then. Could some of you wonderful people comment on these techniques in general, and maybe give me some pointers on recent research, implementions, etc. Thank you, John S. Watson NASA Ames Research Center ARPA: watson@ames.arpa UUCP: ...!ames!watson -- John S. Watson ARPA: watson@ames.arpa NASA Ames Research Center UUCP: ...!ames!watson Any opinions expressed herein are solely the responsibility of the author and do not represent the opinions of NASA or the U.S. Government
cac@drutx.ATT.COM (ConkeyCA) (09/11/87)
In article <2721@ames.arpa>, watson@ames.arpa (John S. Watson) writes: > And now the time has come to add a "constant-time" feature, >Could some of you wonderful people comment on these techniques in general, >and maybe give me some pointers on recent research, implementions, etc. > John S. Watson > NASA Ames Research Center > > ARPA: watson@ames.arpa > UUCP: ...!ames!watson > John S. Watson ARPA: watson@ames.arpa > NASA Ames Research Center UUCP: ...!ames!watson I implemented two constant time Ray Tracers for my masters degree last semester. The algorithms were based on work by: Glassner, Andrew S. "Space Subdivision for Fast Ray Tracing" IEEE Computer Graphics and Applications October 1984 pp(15-22) Fujimoto, Akira and Iwata, Kansei "Accelerated Ray Tracing" Computer Graphics Tokyo 85 April 1985 (I believe this was also republished in IEEE CG&A sometime in the first quarter of 1986) In timing the two methods against straight ray tracing, I had a time reduction of 90% using Glassners method and a reduction of 93% using Fujimoto's method on a scene consisting of 518 spheres that formed a larger sphere. I also did comparison testing between the two methods on a scene consisting of a lamp, and two vases (all surfaces of rotation constructed of polygons). By varying the degree of rotation used in constructing the objects, the number of polygons in the scene was varied from 1000 to 9000 polygons. This comparison showed Fujimoto's method to be 27% faster than Glassners for the largest scenes. I found Glassner's method the easiest and quickest to implement. Curtis Conkey ihnp4!drutx!cac AT&T Information Systems Denver Colorado