wilson@cs.ucf.edu (tom wilson) (05/06/91)
In testing several ray tracing acceleration schemes, I came across something
that I don't really want to bother to test. In my implementation of an octree
and a BSP tree, I don't keep the tree structure during ray tracing. After
constructing the tree, I put the voxel descriptions in an array (voxel size,
number of objects, etc.). I then construct a grid (as in uniform subdivision)
such that the size of a voxel in the grid is the size of the smallest voxel in
the tree. When leaving a voxel, the exit point is determined by finding the
first voxel boundary reached. Then the index grid is used to determine which
"tree" voxel is the next to be visited. This replaces the tree traversal. It
uses more memory and I assume it is faster. The technique is described in
"A New Algorithm of Space Tracing Using a CSG Model," Proceedings of
Eurographics '87, by Bouatouch, Madani, Priol, and Arnaldi. They use a BSP
tree, but the same idea works for an octree.
In case you're not following, +---+---+ +-+-+-+-+
here's a BSP tree example: -> ! ! ! !1!1!2!2!
! 1 ! ! +-+-+-+-+
Determine a ray's start point ! ! ! !1!1!2!2!
just like uniform subdiv. +-+-+ 2 ! +-+-+-+-+
When leaving a "tree" voxel, ! !4! ! !3!4!2!2!
use the size info. to !3+-+ ! +-+-+-+-+
determine exit point. ! !5! ! !3!5!2!2!
+-+-+---+ +-+-+-+-+
BSP tree index grid
The authors claim this is faster than traversing the tree, and for the most
part I believe them. Has anyone tried both? I don't want to implement tree
traversal code when I'm pretty sure it will be slower. A lot of papers on
octrees (and I guess BSP trees) don't seem to mention this idea, so I wonder
how well known it is.
Tom