Using a naive octree with 8 pointers has finally lead to too much memory overhead and traversal time. My idea to fix this is to create a tree where each node is either an array of trees or an array of voxels. The world doesn’t change that often, so it’s not that expensive to destroy and recreate small arrays.
I decided to limit node locations to 5 bits (0-31) per axis. This gives 32x32x32 chunks of voxels or 32x32x32 chunks of trees! Sparse of course. I only store the surface nodes in memory. If I want to use this structure in a universe with 32bit numbers then I end up with a tree like this. tree -> tree -> tree -> tree -> tree -> nodes. Each level is 5 bits so 6 levels gives me 30bits. Using a naive octree I had 16 levels since its 2 bits per axis.
Using 5 bits to store the nodes position in a short (16 bits) will also help the vertex shaders performance. The extra bit is reserved for future extension. Voxel face visibility is also stored (6 bits) and a node type lookup 10 bits. This gives a total of 32 bits per node. That’s only four megabytes for a million voxels (the parent nodes add little overhead ~80k). The unoptimized prototype octree was using 300 megabytes!
Traversal of neighboring nodes is now blazing fast since they are stored in a sorted array instead of traversing up and down the octree.