I am trying to create a sparse voxel octree game and to make it simpler I am starting with a prototype 2D version. The method I am using comes from this Nvidia paper: https://research.nvidia.com/sites/default/files/pubs/2010-02_Efficient-Sparse-Voxel/laine2010i3d_paper.pdf

Here is a picture I use to explain the problem: There are 2 drawings on the top. One of them is the original and the other is the edited version (yes I know I spelt original wrong). The data to the right of those 2 drawings are the coordinates of the 2 added voxels assuming the top left is (0, 0), and the bitmask path to the coordinates for each voxel.

The two blocks of data at the bottom are our 2 quadtree structures. The left one is the original, and the right one is the edited.

A quadtree is structured as follows:
Column 1 – A letter for each node (Just so you can see where each node ends up in the edited version)
Column 2 – A relative pointer to the first child of this node. The other child nodes are found by going to the child pointed it at by the pointer and are the nodes directly after it. The pointer for node A address 0 in the original is 1. This means that you move one down from this address.
Column 3 – The Valid Mask bit mask. it has 4 bits, one for each quadrant, and tells you if there is a node for that quadrant or not. 1st bit is top left, 2nd bit is top right, 3rd bit is bottom left, 4th bit is bottom right. Represented by the green outlined boxes.
Column 4 – The Leaf Mask bit mask. If a bit in this mask and a bit in the Valid Mask are both active, then the corresponding quadrant is a leaf voxel meaning it is a voxel but it contains no more children. All the purple boxes are leaf nodes.
The numbers to the right of each node simply represent the address.

In the edited version, nodes highlighted in pink are nodes that had to be added to ensure the path existed. the bits in the bitmasks highlighted in blue were bits that existed in a node already but were changed to 1 to account for their new child nodes.

My goal is to find a method to add voxels given just the path and an already existing quadtree structure. Generating a new quadtree every time a voxel is added is too slow. It would be much simpler to use a normal quadtree instead of sparse quadtree; However, a sparse quadtree would be ideal for every other aspect of the project and thus is my structure of choice.

I have an idea on the overall approach but am getting stuck on the exact implementation. The best way I could come up with was to follow the path as far down the tree as you can until the node you try to reach does not exist. At that point you can insert a new node and shift the rest of the tree below that node down and recalculate the pointers after the new path is made. the only thing I can’t figure out is how to figure out where to add the new node? Any suggestions on things I should try or ideas on other approaches are much appreciated.

The structure will be stored directly in memory where each node will only consume one 64 bit byte, and an extra byte for each node that contains leaf nodes to store their type.

I have tried figuring some sort of actual implementation behind editing the data, but I was not able to come up with anything or find anything online that achieved this.