Bonxai is a library that implements a compact hierarchical data structure that can store and manipulate volumetric data, discretized on a three-dimensional grid (AKA, a “Voxel Grid”).

Bonxai data structure is:

• Sparse: it uses only a fraction of the memory that a dense 3D voxel grid would use.
• Unbounded: you don’t need to define the boundary of the 3D space (*).

(*) The dimension of the 3D space is virtually “infinite”: since 32-bits indices are used, given a voxel size of 1 cm, the maximum range of the X, Y and Z coordinates would be about 40.000 Km. As a reference the diameter of planet Earth is 12.000 Km.

If you are familiar with Octomap and Octrees, you know that those data structures are also sparse and unbounded.

On the other hand, Bonxai is much faster and, in some cases, even more memory-efficient than an Octree.

This work is strongly influenced by OpenVDB and it can be considered an implementation of the original paper, with a couple of non-trivial changes:

K. Museth,
“VDB: High-Resolution Sparse Volumes with Dynamic Topology”,
ACM Transactions on Graphics 32(3), 2013. Presented at SIGGRAPH 2013.

You can read the previous paper here.

There is also some overlap with this other paper, but their implementation is much** simpler, even if conceptually similar:

 Eurico Pedrosa, Artur Pereira, Nuno Lau
 "A Sparse-Dense Approach for Efficient Grid Mapping"
 2018 IEEE International Conference on Autonomous Robot Systems and Competitions (ICARSC)

Bonxai is currently under development and I am building this mostly for fun and for educational purposes. Don’t expect any API stability for the time being.

Benchmark (preliminary)

Take these numbers with a grain of salt, since they are preliminary and the benchmark is strongly influenced by the way the data is stored. Anyway, they gave you a fair idea of what you may expect, in terms of performance.

-------------------------------------------
Benchmark                     Time
-------------------------------------------
Bonxai_Create              1165 us
Octomap_Create            25522 us

Bonxai_Update               851 us
Octomap_Update             3824 us

Bonxai_IterateAllCells      124 us
Octomap_IterateAllCells     698 us

• Create refers to creating a new VoxelGrid from scratch
• Update means modifying the value of an already allocated VoxelGrid.
• IterateAllCells will get the value and the coordinates of all the existing cells.

How to use it

The core of Bonxai is a header-only library that you can simply copy into your project and include like this:

#include "bonxai/bonxai.hpp"

To create a VoxelGrid, where each cell contains an integer value and has size 0.05.

double voxel_resolution = 0.05;
Bonxai::VoxelGrid<int> grid( voxel_resolution );

Nothing prevents you from having more complex cell values, for instance:

Bonxai::VoxelGrid<Eigen::Vector4d> vector_grid( voxel_resolution );
// or
struct Foo {
 int a;
 double b;
};
Bonxai::VoxelGrid<Foo> foo_grid( voxel_resolution );

To insert values into a cell with coordinates x, y and z, use a VoxelGrid::Accessor object. In the next code sample, we will create a dense cube of cells with value 42:

```c++ // Each cell will contain a float and it will have size 0.05

File truncated at 100 lines see the full file