I am creating a voxel game that uses octrees for storage. The implementation details are not super relevant, but the entire octree is ordered and contiguous in memory and each branch can be merged and only stored as a single entry if all their children contain the same voxel type.
To get the voxel type at one place, I simply descend the tree at a certain location until a leaf node is found.
To set a single voxel type, I descend the tree until a leaf node is found, and if the leaf node is at the bottom level, i.e., fully subdivided, representing a single voxel, I will compare with the other 8 and merge if they are the same, and repeat until the ancestry can no longer be merged; otherwise, the tree will be subdivided at that location to insert the new node.
Due to the ordered and contiguous structure, where each branch node references their children by relative offset, insertions and deletions require offsetting all the data after the point of the insertion, and update indices to data after them that shares their ancestry. Meaning if I want to change a voxel somewhere and somewhere else, I may have to merge and split, or split and merge, or split and split again, or merge and merge again, potentially incurring more realloc calls and memmove calls than necessary. If I insert an item and insert an item after, the items after the second item will have to be moved twice.
Candidate solutions to provide an idea for the type of answer I am looking for: I could provide a function that takes a list positions and changes, and commits them all at once somehow by calculating the final offset of all sections of data before actually moving any around. But this still consists of one change at a time, just being committed in a more optimized way. This does not include the capability to set a non-bottom node to a single value to change an entire power-of-2 aligned area at once. If I want to change a large amount of voxel types in a close together area, in theory I could just 'graft' a new subtree into the original but if then I would have to construct that ahead of time incurring unnecessary overhead just to copy over to the tree. Adding a function to 'reserve' a particular portion of the tree to then build the new 'grafted' data in place to avoid a copy sort of violates encapsulation as that burdens the caller with modifying the internal structure of the tree.
To summarize, what would be a versatile interface that can commit multiple changes, at once, and is able to exploit the strengths of octrees such as being able to assign multiple voxels to a single value in a single step? For example, to generate a house structure, to clear voxels during an explosion, etc., while also maintaining the capability to change individual voxels without incurring significant additional overhead of a mechanism optimized for multiple changes at once, or duplicating core logic?
