During my PhD work, I’ve ran into a lot of practical issues with constructing and traversing sparse voxel Octrees. I’m introducing a new file format to store them, based on the .binvox file format by Michael Kashdan. The format is called .moctree, which stands for Morton-encoded Octree. It contains the leaf level of the octree, with leafs stored in an order which allows easy sparse voxel octree construction.
A file looks like this:
- An ASCII header containing:
- Moctree version (1 for now, for obvious reasons)
- Octree dimensions (only cubical grids supported for now)
- A data section containing a run-length encoded list of voxels in Morton-encoded order (Z-order).
The advantage of this new format lies in the fact that the voxels are not listed in the standard order (z runs fastest, then y, then x), but in an order which groups sibling voxels at the lowest level, like demonstrated in the following image.
This order is not only maintained within an 8-sibling voxel group, but also in a similar way on a higher level (quadtree example, image from Wikipedia)
This makes it easier to quickly build a sparse voxel octree from the data in a streaming way: you don’t need the full voxel grid in memory to build the tree, you only need to look at 8 bits at a time. The .moctree file format only contains info on whether or not a given voxel position contains data, not the data itself.
In order for easy experimenting with this new format, and quickly generating .moctree files from existing .binvox files, I’ve made a small command line tool called Binvox2Moctree, which takes as its only input a .binvox file and writes out a .moctree file with the same name.
Current version: v0.1
- binvox2moctree (Windows Executable, 32-bit version)
- binvox2moctree_x64 (Windows Executable, 64-bit version) (recommended)