Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!hao!oddjob!gargoyle!ihnp4!drutx!cac
From: cac@drutx.ATT.COM (ConkeyCA)
Newsgroups: comp.graphics
Subject: Re: Constant Time Ray Tracing?
Message-ID: <5265@drutx.ATT.COM>
Date: Thu, 10-Sep-87 17:33:33 EDT
Article-I.D.: drutx.5265
Posted: Thu Sep 10 17:33:33 1987
Date-Received: Sat, 12-Sep-87 11:06:01 EDT
References: <2721@ames.arpa>
Organization: AT&T, Denver, CO
Lines: 42
Keywords: ray tracing, computer graphics, search algorithms
Summary: Two constant time ray tracing algorithms

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