Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!waikato.ac.nz!comp.vuw.ac.nz!canterbury!otago.ac.nz!grahaf
Newsgroups: comp.graphics
Subject: Re: Ray Tracing Acceleration ... Is non-uniform s
Message-ID: <1991Jun7.174920.493@otago.ac.nz>
From: grahaf@otago.ac.nz
Date: 7 Jun 91 17:49:20 NZDT
References: <1991May14.070444.18261@images.cs.und.ac.za> <1991May31.175154.4496@pixar.com>
Organization: University of Otago, Dunedin, New Zealand
Lines: 79

In article <1991May31.175154.4496@pixar.com>, markv@pixar.com (Mark VandeWettering) writes:
> 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.. :-)

Very. We have been using a ray-tracer for commercial TV animation for the last
3+ years. This system is a Constructive Solid Geometry (CSG) system which uses
ray-tracing for ALL picture output. This includes B&W sketch prototyping and
full colour, full texture, full transparency pictures. Three years ago I
completed an MSc. which compared our system with two polygon/wire frame
systems. For reasonably complex pictures the ray-tracer was orders of magnitude
faster! 

The system uses a number of strategies to achieve this.


> 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.

1). Adaptive space division with octree. This alows the sub-division of 'busy'
voxels without bothering with the ones that are empty.( Geoff Wyvill )

> 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.  

2). Octree flattening. This takes the adaptive division from 1) and converts it
into a regular space division. This allows the use of a fast voxel skipping
algorithm. ( John Cleary and Geoff Wyvill )

3). Edge following. This uses the fact that in any picture each colour will
cover more than a few pixels. This means that rays are cast only on the edges
of areas of colour; the inside areas can be flood filled without casting extra
rays. This has resulted in casting less than %10 of the rays for a full ray
trace in some cases. Note that the resulting picture is identical to the fully
traced version. ( Geoff Wyvill, Alistair Ward and Tim Brown )

4). Fast antialiasing. Because the edges of colour patches are where aliasing 
occurs it is possible to perform antialiasing only on colour boundaries, 
saving an enourmous number of rays, again without affecting the resulting image.
( Geoff Wyvill and Paul Sharp )

The system is fast enough that we can do commercial work with one SG Personal
Iris and one DEC Station 3100. It is written in standard K&R C and uses no
special hardware. All the techniques used in our system are published, mostly 
in CGI proceedings and "The Visual Computer". If you are interested, e-mail me 
and I will send you a list of the refences. As you may have noticed Geoff 
Wyvill plays a large part in all this. He is the head of the Graphics Research 
Group here at the University of Otago.

BTW We got the loan of an IBM 6000. Just the baby one apparently BUT boy what a
mess. The salesman said it was an early version of the system but surely it
should go faster than a DEC Station 5000 (30 MFlops vs 3 MFlops :).

Graham Furniss, PhD student, Graphics Research Lab, University of Otago,

                       Dunedin, New Zealand.