How can I handle voxels that require extra data in my octree?

Question

I am using octrees as an efficient way to store voxel data in a voxel game. The details of my octree implementation can be found here, but in a nutshell, each node is 16 bits, and the most significant bit determines whether the other 15 bits refers to a voxel type or an index to another set of 8 nodes. The index is relative to the set the node is in. There are 5 maximum levels, including a root node stored separately, making each octree 32x32x32 voxels. This means that for nodes in the bottom layer, the MSB is irrelevant to the structure of the tree and can be used for another purpose.

This system works and is efficient. Any one of 32768 voxel types (air, stone, dirt, etc.) can be stored, and any power-of-2 aligned cube inside the octree that is all the same type, is only stored as one entry, resulting in memory savings and iteration performance savings for octree regions that are mostly the same type.

The issue I have is when I need to introduce more complicated voxel types to the game, that need more data than just 15 bits to represent. I decided to split voxel types into 3 complexity categories:

• Simple (up to 15 bits). They can be stored in any level of the octree.
• Complex (up to 63? bits). They can only be stored at the bottom level of the octree, and cannot be merged if they are the same, because their MSB has to be used. The MSB would determine whether the remaining 15 bits is Simple voxel or an somehow a reference to a 64-bit object. If the LSB of the 64-bit object is not set, the remaining 63 bits are the data of a Complex entry.
• Arbitrarily complex (up to an arbitrary number of bytes in size). If the LSB of a Complex voxel entry is set, the remaining 63 bits (with the LSB cleared) becomes a pointer to some dynamically allocated entity of an arbitrary size.

I use this to describe a Complex entry:

typedef union Ptr {
    union Ptr *p;
    uint64_t u;
} Ptr;

static_assert(sizeof(Ptr)==sizeof(uint64_t), "sizeof(Ptr)!=sizeof(uint64_t)");

This brings us to my question:

How can I efficiently 'embed' these extra data entries in the octree? I have some ideas in mind but are not currently feasible in their current state:

• 16-bit entries at the bottom level of the octree with their MSB set refer to an absolute index in a separate array of Complex entries via their remaining 15 bits. The problem is insertion and deletion. As I found out with designing the octree structure as altogether, before I considered the Complex entries, absolute indices are trouble. If I have to insert/delete something in the middle of the tree and I want to keep the data ordered and contiguous, I will have to shift all the entries after the modification point, thus track down and update all the indices referring to them.

  What if I do not keep them contiguous? Then writing them to files will be trouble. I will still have to iterate all the entries to defragment and also iterate the entire tree to correct the indices to refer to the right places after defragmentation. (I refuse to save any gaps to the file).

• I could embed them inside the tree after the sets that reference them. But this means changing a simple node (even at the bottom level) to a complex node would require a potential mid-tree insertion. And the indexing can get complicated since the 8-byte Complex node entries are not the same size as the 16-byte sets of 8 nodes, meaning an odd number of Complex entries embedded in a tree could result in all sets after them becoming no longer 16-byte aligned. Implementing this could potentially cause unforeseen consequences and require a major rewrite of the octree_set() function I already have and worked so hard on.

Are there any other options that I have for embedding 64-bit entries in an octree designed for 16-bit entries? Are there any variations of my existing ideas that would make implementing them less troublesome?

Note: I also refuse to simply quadruple the size of the entire tree to make every entry 64 bits. This would quadruple memory usage.

Answer 1

I would suggest going with a variant an absolute index in a separate array.

Rather than insert/delete with shifting (which would be painful to implement and slow), or leaving gaps, there is a third option: every time an entry is deleted, retarget whatever is in the last entry in the array to fill that gap created by the deletion. Adding an entry just goes on the end of the array.

So for instance, if the array is originally:

A,B,C,D,E,F

and entry C (index 2) is deleted, move F (originally index 5) to fill in the gap to get:

A,B,F,D,E

Then adding an entry G would give:

A,B,F,D,E,G

Finding the entry in the voxel structure to change does involve a reverse lookup (what points to index 5 that we now want to point to index 2?). Two options here, depending on whether space or speed is more important:

• If space is more important, just scan the tree replacing the index wherever it occurs (can stop after the first one is found if there is only one pointer to each element of this array)

• If speed is more important, have some information about where the pointer is either stored elsewhere (parallel array?) or embedded into the complex data structure, although that does mean that you lose the plain 64 bit option.

This is outside the scope of your question, but if you are prepared to limit yourself to 16384 simple voxel types (14 bits), using the two most significant bits rather than one means that you can have the complex structure at levels other than the bottom of the tree:

There are many possible encoding options for this, but one example:

0xxxxxxxxxxxxxxx - index to another set of 8 nodes

10xxxxxxxxxxxxxx - simple voxel type

11xxxxxxxxxxxxxx - pointer to a complex or arbitrarily complex entry.