Auto-balancing (or cheaply balanced) 3D datastructure

Question

I am working on a tool that requires a 3D "voxel-based" engine. By that I mean it will involve adding and removing cubes from a grid. In order to manage these cubes I need a data structure that allows for quick insertions and deletes. The problem I've seen with k-d trees and octrees is that it seems like they would frequently need to be recreated (or at least rebalanced) because of these operations.

Before I jumped in I wanted to get opinions on what the best way to go about this would be.

Some more details:

• x,y,z position is in integer space
• needs to be efficient enough for a real-time application
• there is no hard limit on the number of cubes that would be used. In all likelihood the number will most often be inconsequentially low (<100), however I would like to have the tool handle as many cubes as possible

I guess the ultimate question is what is the best way to manage what is essentially 3D point data in a way that can handle frequent insertions and deletes?

(No I'm not making Minecraft)

Answer 1

Octrees are easy to update dynamically. Typically the tree is refined based on a per leaf upper/lower population count:

1. When a new item is inserted, it is pushed onto the item list for the enclosing leaf node. If the upper population count is exceeded, the leaf is refined.

2. When an existing item is erased, it is removed from the item list for the enclosing leaf node. If the lower population count is reached, the leaf siblings are scanned. If all siblings are leaf nodes and their cummulative item count is less than the upper population count the set of siblings are deleted and the items pushed onto the parent.

Both operations are local, traversing only the height of the tree, which is O(log(n)) for well distributed point sets.

KD-trees, on the other hand, are not easy to update dynamically, since their structure is based on the distribution of the full point set.

There are also a number of other spatial data structures that support dynamic updates - R-trees, Delaunay triangulations to name a few, but it's not clear that they'd offer better performance than an Octree. I'm not aware of any spatial structure that supports better than O(log(n)) dynamic queries.

Hope this helps.