Octree Overhead

A quick look at the amount of memory overhead in a simple octree structure like:

struct blockinfo_t
{
      byte Type;
      byte Flags;
      byte Extra1;
      byte Extra2;
}; //sizeof() = 4 bytes
struct octreenode_t
{
       octreenode_t *pNodes[8];
       int Size;
       blockinfo_t* pBlockInfo;
}; //sizeof() = 44 bytes + 4 * NumBlocks

Taking a 1024x1024x1024 block world we get the following amount of memory required for each level of the octree (this does not include the actual block data):

  1. 44 bytes
  2. 352 bytes
  3. 2.8 kb
  4. 22.5 kb
  5. 180 kb
  6. 1.4 Mb
  7. 11.5 Mb
  8. 92 Mb
  9. 738 Mb
  10. 5.9 Gb
  11. 47 Gb

Now, a real octree won’t be completely full at all levels so the above numbers are a worst-case scenario but we can clearly see that the overhead of the octree itself gets worse at the higher levels of detail. For example, at the second highest (10) each there is 40 bytes of octree for every 32 bytes of actual block data. This actually gets much worse if we consider a 64-bit system.

One way of combating the high memory overhead at the high details levels in the octree is to combine it with the concept of block chunks. The octree will be used until it reaches the chunk size at which point the octree subdivision ends and all blocks in the chunk are stored at once. This also helps combat the extreme non-locality of adjacent blocks if we use the octree structure down to the individual block.

As a specific example let us take the previous case and use a chunk size of 16x16x16. At this size the octree ends after #7 in the list meaning we have less than 15 Mb of total octree data compared to 4 Tb of possible block data. This is a much more manageable overhead level to a point where we probably don’t need to be too worried about it, so long as the chunk size doesn’t get too small, which it likely can’t for a variety of other reasons.

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>