[comp.graphics] Octree representations: A consensus?

brownrigg@kuhub.cc.ukans.edu (11/28/90)

So what has experience proven about how to best represent (for the purposes
of ray tracing) octree structures?  Is it preferable to:

1).  use a "linear" encoding method, whereby only the leaves are explicitly
     represented, and their locations derived somehow (ala Glassner [84],
     Gargantini, EXCELL, etc....)

or

2).  burn the storage and explicitly represent the interior nodes, complete
     with 8 explicit pointers to child nodes (as in Fujimoto [86]).


What do we opt for in '90s technology?  It seems clear that 1) optimizes 
space.  Both should have a theoretical complexity of O(lnN) in accessing
a node given a point.  But with 2), it seems that we can often do better
than this worst-case by vertically traversing the tree up only to the 
parent of the "current" node and the "next" node we are interested in;
rather than always traverse down from the root.

Any takers?  Comments, discussions, flames, thesis, etc. are all welcome.

Rick Brownrigg
Kansas Geological Survey