Is there are compact way to represent octrees in memory?

Just curious if anyone has wrapped their brain around this one?
Posted on 2003-02-16 12:39:23 by bitRAKE
Octrees are pretty efficient man - they eliminate a lot of empty space.
The basic problem is that you need eight pointers per node.
If your octree is stored as a linked list of nodes, the best way you can hope to begin is to rebuild the "floating" nodes into a linear array.
The bulk of each Node in the linearly-arranged linkedlist is its link pointers.
They contain the addresses of other nodes within the now linear array.
You could try tokenizing the links for each node into a table, and at the same time rebuild the linearized linklist array, throwing away the links since they are encoded now in a linear lookup table.
You now have a linear array of nodes containing just pointers to lists of geometry for each terminal octree node, plus a linear lookup table of pointers encoded by node offset. It should be roughly 7 times smaller than the original octree.
Posted on 2003-02-16 23:35:11 by Homer
Posted on 2003-02-17 05:10:15 by AmkG
In 3d, an octree can be used to divided up and sort objects according to their location just like a binary tree. The space is first divided in the xy plane into 4 spaces, upper left, upper right, lower left, lower right. The these are divided into 4 spaces by depth giving a total of 8 boxes. Hence, the oct.

While scanning a scene if your pixel location or ray is in the upper left cell, you know it's safe to ignore objects in the other cells.
Posted on 2003-02-17 08:10:43 by drhowarddrfine
EvilHomer2k, don't linear octrees require a full tree?
http://www.cg.tuwien.ac.at/studentwork/VisFoSe98/eder/octree.htm

I was able to find a lot of source code using octrees, but very little text describing them in detail.

Some other texts on octrees:
http://www.albany.edu/~sysrcy/dissertation/PR-11.TXT
Posted on 2003-02-17 12:38:02 by bitRAKE
I described a linearized tree, not a linear array. The difference is the addition of a table which describes whether or not a node is linked, and this table is arranged in order of appearance of actual nodes, so its ideal for non symettrical trees.
Note that the table does not contain actual pointers to other nodes - they no longer exist, but are encoded in the table by virtue of offset.
We are not even taking advantage of the inherent pattern in an octree.
Posted on 2003-02-18 02:41:57 by Homer
If you really need a small octree representation, you can discard the subnode pointers completly and just store a list of objects (which can be 16-bit per element if there are few objects) and a flag which tells if it is a non-terminal or not. You can then store the octree in a linear array. This is, however, quite time consuming to traverse and ruins the point of octrees a bit. Here is a binary tree built around the same idea (first parameter is the number of objects, second parameter is a object list and third is the non-terminal flag):

``````
NODE1 3, (0, 1, 3), TRUE
NODE2 3, (2, 4, 5), TRUE
NODE3 5, (6, 7, 9, 10, 11), TRUE:
NODE4 2, (8, 12), FALSE
NODE5 2, (13, 14), FALSE
NODE6 1, (15), FALSE
NODE7 1, (15), FALSE
``````

This can be encoded in 2 + 2*n bytes per node if n is the number of objects and we know that the maximum number of objects is 32768.
I hope you get the idea :).
Posted on 2003-02-24 03:46:01 by gliptic