Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!cs.utexas.edu!wuarchive!kuhub.cc.ukans.edu!brownrigg
From: brownrigg@kuhub.cc.ukans.edu
Newsgroups: comp.graphics
Subject: Octree representations: A consensus?
Message-ID: <27118.27530b8d@kuhub.cc.ukans.edu>
Date: 28 Nov 90 06:57:49 GMT
Organization: University of Kansas Academic Computing Services
Lines: 24

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