Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!crdgw1!ge-dab!tarpit!osceola.cs.ucf.edu!wilson
From: wilson@cs.ucf.edu (tom wilson)
Newsgroups: comp.graphics
Subject: Re: Ray Tracing Acceleration ... Is non-uniform spatial subdivision the best??
Keywords: Ray tracing Spatial subdivision Voxel
Message-ID: <1991May18.041609.9623@osceola.cs.ucf.edu>
Date: 18 May 91 04:16:09 GMT
References: <1991May14.070444.18261@images.cs.und.ac.za>
Sender: news@osceola.cs.ucf.edu (News sysetm)
Organization: University of Central Florida, Orlando
Lines: 38

In article <1991May14.070444.18261@images.cs.und.ac.za> mikhaley@images.cs.und.ac.za writes:
>I have been working on algorithms for traversing voxels in an octree,(ie. Have been using
>non-uniform spatial subdivision techniques) and I have come up with some fairly good routines
>but I just want to know if any of the other methods are better and am I thus just wasting my
>time barking up the wrong tree. Also I would appreciate it, if any of you have any really 
>efficient voxel traversal routines that you would like to compare with mine, to contact me!

I have been trying to determine which subdivision schemes work best and in
which situations. I have implemented my own nonuniform subdivision scheme,
a (US) uniform subdivision scheme, a BSP tree, and an octree. To avoid tree
traversal, I used a voxel index grid along with the leaves of the tree (octree
and BSP tree). I haven't finished testing, but I can make some comments.

While US isn't always the fastest (but often is), it does seem to perform best
on the average. The BSP tree seems to outperform the octree. The BSP tree that
I've implemented divides along the axis with the largest dimension (this may
not be the best "simple" approach, but it does seem to outperform the octree
so far). My scheme (which I won't explain) is comparable to the others.

I have picked at the code for my scheme so that I doubt I can speed it up any
more. I haven't had the time to do that with the other schemes. I doubt I can
improve the US scheme any more since it is so simplistic. The BSP tree and
octree may be improved, but I don't know. A question I asked the net was
whether a pure tree (octree/BSP tree) is slower than the index grid. I
received no replies, but perhaps it didn't go out.

I would say, without a doubt, that implementing US is by far the easiest. If
anyone wants to implement a speedup scheme, I would suggest US. I would like to
implement some other schemes (e.g. ray classification), but I don't think I
can devote the amount of time to write and debug other schemes (which tend to
be much more complicated than the ones I've already done). No one seems to
have other techniques implemented that they are willing to give away.

One last note concerns octrees and BSP trees. There are several papers that
discuss heuristics for determining how much or where to subdivide. I haven't
tried to implement any of these.

Tom