BZVX

BZVX is a voxel geometry library that uses Sparse Voxel Directed Acyclic Graphs (SVDAGs) for a variety of operations.

Sparse Voxel Directed Acyclic Graphs (SVDAGs)

A SVDAG is similar to a sparse voxel octree (SVO): A cubic volume is recursively subdivided in 8 parts where there are boundaries between materials, while uniform volumes are not subdivided. However, In a SVDAG, multiple nodes can point to the same child in cases where there would have been duplicated subtrees in an SVO. This has the potential to vastly reduce the memory footprint of the voxel data.

Reading and storing a SVDAG is very similar to a SVO. Absolute position data can't be stored along with the nodes, since one node may represent multiple different volumes. Therefore, absolute position information must be calculated implicitly as you traverse the datastructure. Other than that, traversing SVDAGs is the same as traversing SVOs, and the compression is "free" from a reading/traversing perspective.

Modifying a SVDAG is more complicated, however. Nodes can be referenced from multiple parents, so each time voxel data is changed, parent nodes potentially up to the root node may need modifications to avoid invalid changes to other data. The simplest method is to simply duplicate every node while traversing from the root and modify the new copy (and the original child of the root). Inductively, if a node can be modified without causing collateral changes, then a direct child node can be duplicated, the current node can be modified to point to the duplicate, and the child can then also be modified without causing