I’m making a voxel sport that makes use of octrees for storage. The implementation particulars are usually not tremendous related, however your complete octree is ordered and contiguous in reminiscence and every department could be merged and solely saved as a single entry if all their kids include the identical voxel kind.
To get the voxel kind at one place, I merely descend the tree at a sure location till a leaf node is discovered.
To set a single voxel kind, I descend the tree till a leaf node is discovered, and if the leaf node is on the backside degree, i.e., totally subdivided, representing a single voxel, I’ll evaluate with the opposite 8 and merge if they’re the identical, and repeat till the ancestry can now not be merged; in any other case, the tree will likely be subdivided at that location to insert the brand new node.
Because of the ordered and contiguous construction, the place every department node references their kids by relative offset, insertions and deletions require offsetting all the information after the purpose of the insertion, and replace indices to information after them that shares their ancestry. Which means if I wish to change a voxel someplace and someplace else, I’ll should merge and break up, or break up and merge, or break up and break up once more, or merge and merge once more, doubtlessly incurring extra realloc calls and memmove calls than obligatory. If I insert an merchandise and insert an merchandise after, the objects after the second merchandise should be moved twice.
Candidate options to offer an thought for the kind of reply I’m searching for: I might present a perform that takes a listing positions and modifications, and commits them all of sudden one way or the other by calculating the ultimate offset of all sections of knowledge earlier than truly shifting any round. However this nonetheless consists of 1 change at a time, simply being dedicated in a extra optimized means. This doesn’t embody the aptitude to set a non-bottom node to a single worth to alter a complete power-of-2 aligned space without delay. If I wish to change a considerable amount of voxel varieties in a detailed collectively space, in concept I might simply ‘graft’ a brand new subtree into the unique but when then I must assemble that forward of time incurring pointless overhead simply to repeat over to the tree. Including a perform to ‘reserve’ a selected portion of the tree to then construct the brand new ‘grafted’ information in place to keep away from a duplicate form of violates encapsulation as that burdens the caller with modifying the inner construction of the tree.
To summarize, what can be a flexible interface that may commit a number of modifications, without delay, and is ready to exploit the strengths of octrees akin to with the ability to assign a number of voxels to a single worth in a single step? For instance, to generate a home construction, to clear voxels throughout an explosion, and many others., whereas additionally sustaining the aptitude to alter particular person voxels with out incurring important further overhead of a mechanism optimized for a number of modifications without delay, or duplicating core logic?
