elf@utcsri.UUCP (Eugene Fiume) (08/08/85)
[] > In one course I learned alot about splining motion and rotation; clipping > an arbitrary volume to another arbitrary volume; a ray-tracing algorithm > that executes in constant time ( same time for 5 polygons as for 50,000 ) > (so what if the program is available commercially, the speaker gave us > enough information to duplicate that performance); and how to extend > ray-tracing to eliminate aliasing, give motion blur, light penumbras, > amoung other things. > > > Name: Robert Skinner > Mail: Saber Technology, 2381 Bering Drive, San Jose, California 95131 > AT&T: (408) 945-0518, or 945-9600 (mesg. only) > UUCP: ...{decvax,ucbvax}!decwrl!saber!skinner > ...{amd,ihnp4,ittvax}!saber!skinner I suspect this was the 'rendering tricks' course, which I didn't attend. Can someone explain the details of that 'ray-tracing algorithm that executes in constant time'? Eugene Fiume {decvax|allegra}!utcsri!elf
glassner@unc.UUCP (Andrew S. Glassner) (08/15/85)
The basic idea is to subdivide space recursively into an octtree, until each node of the tree contains no more than some small number of objects. You then trace a ray by determining what node it is in, and only intersecting against the objects in that node. If you hit an object in that node (and you usually do), you know you don't have to test against any more objects. If you don't hit something in that node you project into the next node and try again. Since each node contains a number of objects less than or equal to some small number (like 5), you essentially test each ray against only that number of objects; hence the term "constant time". It's really not correct to say constant time, though; that's an optimistic viewpoint that is often defeated in real scenes. I refrained from giving the algorithm that name in the original publication; I guess the temptation was too great to resist in the long run. Details of the "constant time" ray tracer may be found in my paper "Space Subdivision for Fast Ray Tracing" in the October 1984 IEEE Computer Graphics & Applications. -- -Andrew Andrew Glassner glassner@unc decvax!mcnc!unc!glassner
jbn@wdl1.UUCP (08/23/85)
I don't see that this is constant time; it takes log(n) time to get down to the right cube in the octtree; for a complex enough image, this will dominate the ray tracing computation. John Nagle
curtis@uwmacc.UUCP (Alan Curtis) (08/27/85)
In addition to searching the tree for the particular node (cube) which the
ray happens to land in, all objects in the nodes which are passed through
during the search must be examined for intersection, as they may potentially
overlap the cube in question.
I haven't tested octtrees, but I've found (emperically)
that a multi-dimensional binary tree
is faster than a quadtree for determining intersections of objects because the
number of unsuccessful tests is cut by about a factor of two.
Alan Curtis