Newsgroups: comp.graphics
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!uupsi!pixar!markv
From: markv@pixar.com (Mark VandeWettering)
Subject: Re: Ray Tracing Acceleration ... Is non-uniform spatial subdivision the best??
Message-ID: <1991May31.175154.4496@pixar.com>
Keywords: Ray tracing Spatial subdivision Voxel
Sender: news@pixar.com (Usenet Newsmaster)
Nntp-Posting-Host: woody
Organization: Pixar -- Point Richmond, California
References: <1991May14.070444.18261@images.cs.und.ac.za>
Date: Fri, 31 May 1991 17:51:54 GMT

In article <1991May14.070444.18261@images.cs.und.ac.za> mikhaley@images.cs.und.ac.za writes:

[ What's the best ray accleration technique? ]

Well, the best technique (in a way) is not to do ray tracing if you don't
have too.  I take it for granted that you have considered this solution.

Now that you have decided on ray tracing, you have an enormous number of
ray accelerators to choose from.  First of all, I believe that most of 
the common ones (uniform subdivision, octrees, Kay/Kajiya bounding volumes,
BSP trees, etc...) are all pretty good and a good implementation of any 
of them is probably within a factor of two of any of the others.  (ooooh, 
bold statement.. :-)

Some personal comments about some of the more important ones.

1. 	Uniform subdivision is great because the cost of casting 
	rays is kept very low, and the object data base is searched from
	the eye out.  Its only unfortunate characteristic occurs when a 
	large number of primitive objects happen to fall within a single 
	voxel.  This makes certain scenes render very fast, while others 
	crawl along, even with the same number of pixels.  I have yet to
	see a really nice way of automatically detecting this condition
	and "regridding" the environment.  What is usually done is to arrange
	these grids hierarchically.  For example, Eric Haines usually brings
	up the "teapot in the football stadium" as an example of where all
	the triangles which make up the teapot happen to fall within a voxel.		The solution is to have two separate grids, one surrounding the 
	stadium and the other surrounding the teapot.  Usually this is done
	by hand.

2.	Octrees seem fine to me, once you actually get code that handles 
	some of the nasty cases worked out (ray leaves a cube via a face, 
	edge or vertex).  Many people swear by these, I have little 
	experience.  

3.	Kay/Kajiya bounding volumes are what I used in the MTV raytracer, 
	with an automatic hierarchy generator.  When compared against 
	Craig Kolb's ray tracer, MTV was definitely slower, but not by
	as great an amount as I would have imagined.  I believe that the 
	chief advantage of an automatic hierarchy generator is that 
	performance never seems to get AWFUL or other than you might 
	reasonably expect.

4.	BSP trees are sort of midway between Kay Kajiya and Octrees.
	If you were confined to polygonal models, you could implement
	CSG nicely using this.  Good stuff.


Anyway, you might try reading the chapter "A Survey of Ray Acceleration
Techniques" in Introduction to Ray Tracing edited by Andrew Glassner.

Mark VandeWettering, Pixar (disclaim disclaim disclaim)