Repository files navigation

Bonxai is a library that implements a compact hierarchical data structure thatcan store and manipulate volumetric data, discretized on a three-dimensionalgrid (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":since32-bits indices are used, given a voxel size of1 cm,the maximum range of the X, Y and Z coordinates would be about40.000 Km.As a referencethe diameter of planet Earth is 12.000 Km.

If you are familiar withOctomap and Octrees, you knowthat those data structures are also sparse and unbounded.

On the other hand, Bonxai ismuch faster and, in some cases, even more memory-efficientthan an Octree.

This work is strongly influenced byOpenVDB and it can be consideredan 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 paperhere.

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 foreducational purposes. Don't expect any API stability for the time being.

Take these numbers with a grain of salt, since they are preliminary and the benchmark isstrongly 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 usOctomap_Create            25522 usBonxai_Update               851 usOctomap_Update             3824 usBonxai_IterateAllCells      124 usOctomap_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.

The core ofBonxai is a header-only library that you can simply copy into your projectand 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 );// orstructFoo {int a;double b;};Bonxai::VoxelGrid<Foo>foo_grid( voxel_resolution );

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

// Each cell will contain a `float` and it will have size 0.05double voxel_resolution =0.05;Bonxai::VoxelGrid<float>grid( voxel_resolution );// Create this accessor once, and reuse it as much as possible.auto accessor = grid.createAccessor();// Create cells with value 42.0 in a 1x1x1 cube.// Given voxel_resolution = 0.05, this will be equivalent// to 20x20x20 cells in the grid.for(double x =0; x <1.0; x += voxel_resolution ) {for(double y =0; y <1.0; y += voxel_resolution ) {for(double z =0; z <1.0; z += voxel_resolution ) {// discretize the position {x,y,z}      Bonxai::CoordT coord = grid.posToCoord(x, y, z);      accessor.setValue( coord,42.0 );    }  }}// You can read (or update) the value of a cell as shown below.// If the cell doesn't exist, `value_ptr` will be `nullptr`,Bonxai::CoordT coord = grid.posToCoord(x, y, z);float* value_ptr = accessor.value( coord );

Bonxai::VoxelGrid isnot thread-safe, for write operations.

If you want to access the grid inread-only mode, you canuse multi-threading, but each thread should have its ownaccessor.

• serialization to/from file.
• full implementation of the Octomap algorithm (ray casting + probability map).
• integration with ROS 2.
• RViz2 visualization messages.
• integration withFCL for collision detection (?)

What is the point of reimplementing OpenVDB?

• The number one reason is to have fun and to learn something new :)
• I want this library to be small and easy to integrate into larger projects.The core data structure is less than 1000 lines of code.
• It is not an "exact" rewrite, I modified a few important aspects of the algorithmto make it slightly faster, at least for my specific use cases.

How much memory does it use, compared with Octomap?

It is... complicated.

If you need to store very sparse point clouds, you should expect Bonxai to use more memory (20-40% more).If the point cloud is relatively dense, Bonxai might use less memory than Octomap (less than half).