Out-Of-Core Construction of Sparse Voxel Octrees - reference implementation
This is a proof of concept implementation of the algorithm explained in our HPG 2013 paper, Out Of Core Construction of Sparse Voxel Octrees. The project was subsequently updated after the article was also published in Computer Graphics Forum 2014. The paper and additional material can be found on the project page.
There are two tools distributed in this release, both are required to convert a model into a Sparse Voxel Octree representation:
tri_convert: A tool to convert any model file to a simple, streamable .tri format, described in this manual. You can use this tool, or format your model files yourself.
svo_builder: Out-Of-Core SVO Builder: Partitioning, voxelizing and SVO Building rolled into one executable, needs a .tri file as input
ooc_svo_buildercan be built on:
linuxfolder. Also, see the travis.yml for how the automated build is made.
Additional library dependencies are:
tri_converttool. I maintain my own fork which is compatible.
For the Windows build, you have to configure the location of the external libraries (see dependencies) in the supplied props files. You can configure where VS should copy the compiled binaries to and where the build process can find the required trimesh2 and glm libraries.
C:\Binaries\ C:\libs\glm\/msvc/vs2019/triconvertcustom_includes.props :
C:\Binaries\ C:\libs\trimesh2\ C:\libs\glm\
This release supports two modes of SVO building: * Binary-only: SVO building (only geometry, the default mode presented in the paper). The result will be an SVO with all leaf nodes referencing the same, white default voxel. The data part of the SVO will only be a couple of bytes. * Payload: SVO building with a (normal vector + vertex colors) payload per voxel. The result will be an SVO with all leaf nodes referencing their own sampled voxel payload.
Please note how "binary" is used as a description of the content of the SVO. Binary as in: either a voxel present or not. I know this is confusing with the programming-related usage of "binary". What can I say? It be like dat sometimes.
Throughout all executables, the tools for binary voxelization are postfixed with
_binary. During compilation, you can define the preprocessor directive #BINARY_VOXELIZATION to generate the binary-only SVO construction version.
The builder uses a simple binary format for triangles and their information. Before you can build an SVO from a 3d model you have, you've got to convert it to the .tri format using the
tri_converttool. For more info about the .tri file format, check libtri.
The bounding box of the model will be padded to be cubical.
tri_convertaccepts .ply, .off, .3ds, .obj, .sm or .ray files. For geometryonly .tri file generation, use `triconvertbinary
, for .tri file generation with a normal vector payload, usetriconvert`.
tri_convert(_binary) -f (path to model file)
tri_convert(_binary) -f /home/jeroen/bunny.plyThis will generate a bunny.tri + bunny.tridata file pair in the same directory
The SVO builder takes a .tri file as input and performs the three steps (partitioning, voxelization and SVO building) described in the paper. Depending on the memory limit you specify, the model is partitioned into several subgrids in a pre-pass, then each of these subgrids is voxelized and the corresponding part of the SVO is built. The output is stored in the .octree file format, described further below.
Since v1.2, side-buffer of configurable maximum size is also used to speed up SVO generation. This is especially interesting for sparse models (voxelizations of thin models).
To build an octree for a geometry-only file, use
svo_builder_binary. For building an octree for files with a normal vector payload, use
svo_builder. The tools will slap you with a trout if you try to run them with the wrong type of file.
Syntax: svobuilder(binary) -options
svo_builder_binary -f bunny.triWill generate a geometry-only SVO file bunny.octree for a 1024^3 grid, using 2048 Mb of system memory.
svo_builder -f bunny.tri -s 2048 -l 1024 -d 0.2 -c normal -vWill generate a SVO file bunny.octree for a 2048^3 grid, using 1024 Mb of system memory, with 20% of additional memory for speedup, and be verbose about it. The voxels will have a payload and their colors will be derived from their normal.
The .octree file format is a very simple straightforward format. It is not optimized for GPU streaming or compact storage, but is easy to parse and convert to whatever you need in your SVO adventures.
Please note that I am reworking this format in the liboctree repository. Currently, these repositories are not compatible, so don't mix them. Keep using the provided headers included in the `oocsvobuilder` repository.
It consists of a text-based header (extension .octree) containing the relevant SVO info and two binary data files, with extensions .octreenodes and .octreedata, containing the octree nodes and actual node data payload respectively. This seperation of the SVO from the actual data is done to seperate hot (tree itself) from cold (payload) data, since the payload of course grows quickly when you store more properties in a voxel.
A typical .octree header file is text-based and looks like this. All keyword - values lines are separated by a newline: ```
gridlength 1024 nnodes 1474721 ndata 484322 end ``` All elements are required. * #octreeheader (version_number): (int) Octree version number. * gridlength (n): (int) Length of one side of the cubical voxel grid. Should be a power of 2. * n_nodes (n): (int) The total amount of SVO nodes. * n_data (n): (int) The total amount of data payloads. This is not automatically the same as n_nodes, you can have several nodes point to the same data. In the case of a geometry-only SVO, all nodes refer to the same voxel payload, at position 1. * END: Indicating the end of the header file.
An .octreenodes file is a binary file which describes the big flat array of octree nodes. In the nodes, there are only child pointers, which are constructed from a 64-bit base address combined with a child offset, since all nonempty children of a certain node are guaranteed by the algorithm to be stored next to eachother. The .octreenodes file contains an amount of n_nodes nodes.
An .octreedata file is a binary file representing the big flat array of data payloads. Nodes in the octree refer to their data payload by using a 64-bit pointer, which corresponds to the index in this data array. The first data payload in this array is always the one representing an empty payload. Nodes refer to this if they have no payload (internal nodes in the tree, ...).
The current payload contains a morton code, normal vector and color information. This can be easily extended with more appearance data. I refer to the 'Appearance' section in our paper. As described in the .octreeheader, the .octreedata file contains n_data nodes.
The generated .octree files and data packages can be visualized using this CPU Voxel Raycaster. Mind you: this is an old version, I'm actively developing a newer, more modern viewer. Things will break.
I would like to thank Ares Lagae and Philip Dutre for their continuing great input and co-authorship. We would also like to thank the anonymous reviewers for their remarks and comments. Jeroen Baert is funded by the Agency for Innovation by Science and Technology in Flanders (IWT). Ares Lagae is a postdoctoral fellow of the Research Foundation - Flanders (FWO). I would also like to thank all people who've contributed fixes to this repository over the years.
Over the years, there have been a few papers building on this codebase. Feel free to check them for improvements and ideas: * Pätzold & Kolb, 2015 - Grid-free out-of-core voxelization to sparse voxel octrees on GPU (PDF) * Matsuda, Furuya, Ohbuchi, 2015 - Lightweight binary voxel shape features for 3D data matching and retrieval (PDF)
Feel free to contact me with questions/suggestions at jeroen.baert (at) cs.kuleuven.be
Keep in mind that this tool is in active development and that it is research code. I am not responsible or liable if it crashes your system, runs over your dog and/or steals your partner.