Just went through
VDB: High-Resolution Sparse Volumes with Dynamic Topology (22 pages) to best understand the inner workings of OpenVDB and write a summary for posterity.
For the interested readers, the sections relevant to our discussion are:
1.2: Contributions and characteristics of VDB (half page)
2: The VDB data structure (6 pages)
3: VDB access algorithms (4 pages)
B: (Appendix) Multithreading and Vectorization (half page)
VDB (OpenVDB is an open-source implementation) is a storage solution characterized, among other things, by a tree of nodes whose depth and branching factors are defined a compile time. I.e. the default tree (seen in benchmarks as best compromise between various efficiency parameters) has a
Root Node which contains a (small) list/hashmap of children nodes called
Internal Nodes, each containing in turn 32^3 children nodes (also called Internal Nodes), each containing a further 16^3 children called
Leaf Nodes, each containing 8^3 voxels. As such, the tree has five levels (from root to voxels) and a single Internal Node immediate child of the root node is a cube (32x16x8)=4096 voxels per side (or 68 Billion voxels). The default tree configuration provides cubic nodes but custom configurations allow for individually chosen dimensions along the three axis, the only restriction being they must be powers of 2. This restriction allows for much of the bitwise magic detailed in the paper, allowing for example to pinpoint the memory offset of node (at any level in the tree) containing a set of global x,y,z coordinates by using only three bitwise & operations, one per axis.
To recap the tree structure: Root Node -> N Internal Nodes -> 32^3 Internal nodes -> 16^3 Leaf Nodes -> 8^3 voxels. The author, by the way, finds a notable analogy between the empirically obtained (32/16/8)^3 sizes (best for balanced performance) with the relative sizes of modern CPU's L3/L2/L1 caches. He hints there might be a sweet performance spot with those numbers given current hardware.
An interesting characteristic of VDB is the concept of
Tile. A tile is a child node full of identical voxels. I.e. if a Leaf Node (say, 8x8x8 voxels) is full of identical voxel it is not instantiated, or it is pruned as soon as it becomes homogeneous or at another convenient time. A tile object is used in its place, containing a single reference to the voxel. As tiles can be children of any Internal Node in the tree, a tile of the default tree configuration described above could be taking the place of anywhere between 8^3=512 blocks (when replacing a Leaf node) and 32^3=32768 blocks (when replacing an internal node child of the root node). This greatly reduces memory consumption both in RAM and during serialization. Also, the bitwise algorithms mentioned above remain valid as they find which node contains a set of xyz coordinates. If the node is a tile instead of a proper node with children, so be it: the tree traversal stops there and returns the voxel stored in the tile.
Because the tree is height balanced by its statically defined, compile-time configuration, random access to voxels is, in the worst case scenario, constant time or O(1). Obviously if a set of coordinates points to a tile somewhere earlier in the tree, it is faster than that. The paper also describes
caching mechanisms on the basis that random access is actually
rarely truly random. I.e. a player will interact by and large only with blocks that are near him and most likely only with blocks he or she can see. Caching previous tree traversals to reach a voxel allows for reverse traversals from that voxel to nearby ones, the cache in most case limiting the traversals to the first common ancestor node rather than requiring ascending all the way to the root node.
Bit masks are another attractive feature for this project's intent and purposes, I suspect. Every node has a bit mask describing which child node is
active. The definition of "active" is application-specific. One potential use is to flag as active all nodes that neighbor air, water or other transparent blocks as a subset of them is what gets rendered. Special blocks that need to remain active even when hidden can also use this feature. I would expect this mechanism to speed up visibility testing as one needs to iterate only on the bitmask rather than the content of a whole node. I imagine additional bitmasks could also be used for other purposes.
Sequential and stencil access is probably where VDB mostly shines. The combined use of contiguous memory, caching, tiles and bitmasks makes iteration fast, especially in sparse, heterogeneous volumes or even in dense, relatively homogeneous volumes. The system also prescribes an
out-of-core offset on a per-node basis, so that if a node needs to be loaded from disk, its file offset is readily available.
Finally, a few considerations from me.
The reason I wrote this summary is not to advocate the implementation or adoption of VDB as a whole. More likely, we could use some of its principles. I.e. I doubt its default tree structure, characterized by cube-shaped nodes would be appropriate. In the case of a minecraft-like, vanilla world the individual nodes might be more appropriately biased toward square, flatter boxes instead of cubes, to reflect the horizontal nature of most landscape. I also doubt a full five levels of tree hierarchy is necessary for this project. Perhaps four levels (root/internal/leaf/voxels) would be enough, the root node being dense, array-based (VDB's root node is sparse, list/hashmap-based).
However, the concept of tiles replacing homogeneous volumes whenever possible seems quite relevant to this thread and perhaps easily applicable.
One thing VDB does -not- provide out of the box is multi-resolution, i.e to support low-resolution, vast(er) landscapes visible in the distance. I imagine however that it would be easy to store for this purpose some additional data at leaf level and above, so that while nearby individual blocks are rendered as usual, boxes the size of a leaf node (i.e. 16^3) or even bigger are rendered in the distance.
That's all for now. Looking forward to somebody a couple of years from now digging this out and implementing something out!
