base on Fast, hierarchical, sparse Voxel Grid  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](https://octomap.github.io/) 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](https://www.openvdb.org/) 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](http://www.museth.org/Ken/Publications_files/Museth_TOG13.pdf). 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. # 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: ```c++ #include "bonxai/bonxai.hpp" ``` To create a VoxelGrid, where each cell contains an integer value and has a size of 0.05. ```c++ double voxel_resolution = 0.05; Bonxai::VoxelGrid<int> grid( voxel_resolution ); ``` Nothing prevents you from having more complex cell values, for instance: ```c++ 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 the value 42: ```c++ // Each cell will contain a `float` and it will have size 0.05 double 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 ); ``` ## Note about multi-threading `Bonxai::VoxelGrid` is **not** thread-safe, for write operations. If you want to access the grid in **read-only** mode, you can use multi-threading, but each thread should have its own `accessor`. # Roadmap - [x] serialization to/from file. - [x] full implementation of the Octomap algorithm (ray casting + probability map). - [x] integration with ROS 2. - [ ] RViz2 visualization messages. - [ ] integration with [FCL](https://github.com/flexible-collision-library/fcl) for collision detection (?) # Frequently Asked Questions **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 algorithm to 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, Bonxai will probably use more memory (20-40% more). If the point cloud is relatively dense, Bonxai might use less memory than Octomap (even less than half). ", Assign "at most 3 tags" to the expected json: {"id":"2012","tags":[]} "only from the tags list I provide: [{"id":77,"name":"3d"},{"id":89,"name":"agent"},{"id":17,"name":"ai"},{"id":54,"name":"algorithm"},{"id":24,"name":"api"},{"id":44,"name":"authentication"},{"id":3,"name":"aws"},{"id":27,"name":"backend"},{"id":60,"name":"benchmark"},{"id":72,"name":"best-practices"},{"id":39,"name":"bitcoin"},{"id":37,"name":"blockchain"},{"id":1,"name":"blog"},{"id":45,"name":"bundler"},{"id":58,"name":"cache"},{"id":21,"name":"chat"},{"id":49,"name":"cicd"},{"id":4,"name":"cli"},{"id":64,"name":"cloud-native"},{"id":48,"name":"cms"},{"id":61,"name":"compiler"},{"id":68,"name":"containerization"},{"id":92,"name":"crm"},{"id":34,"name":"data"},{"id":47,"name":"database"},{"id":8,"name":"declarative-gui "},{"id":9,"name":"deploy-tool"},{"id":53,"name":"desktop-app"},{"id":6,"name":"dev-exp-lib"},{"id":59,"name":"dev-tool"},{"id":13,"name":"ecommerce"},{"id":26,"name":"editor"},{"id":66,"name":"emulator"},{"id":62,"name":"filesystem"},{"id":80,"name":"finance"},{"id":15,"name":"firmware"},{"id":73,"name":"for-fun"},{"id":2,"name":"framework"},{"id":11,"name":"frontend"},{"id":22,"name":"game"},{"id":81,"name":"game-engine "},{"id":23,"name":"graphql"},{"id":84,"name":"gui"},{"id":91,"name":"http"},{"id":5,"name":"http-client"},{"id":51,"name":"iac"},{"id":30,"name":"ide"},{"id":78,"name":"iot"},{"id":40,"name":"json"},{"id":83,"name":"julian"},{"id":38,"name":"k8s"},{"id":31,"name":"language"},{"id":10,"name":"learning-resource"},{"id":33,"name":"lib"},{"id":41,"name":"linter"},{"id":28,"name":"lms"},{"id":16,"name":"logging"},{"id":76,"name":"low-code"},{"id":90,"name":"message-queue"},{"id":42,"name":"mobile-app"},{"id":18,"name":"monitoring"},{"id":36,"name":"networking"},{"id":7,"name":"node-version"},{"id":55,"name":"nosql"},{"id":57,"name":"observability"},{"id":46,"name":"orm"},{"id":52,"name":"os"},{"id":14,"name":"parser"},{"id":74,"name":"react"},{"id":82,"name":"real-time"},{"id":56,"name":"robot"},{"id":65,"name":"runtime"},{"id":32,"name":"sdk"},{"id":71,"name":"search"},{"id":63,"name":"secrets"},{"id":25,"name":"security"},{"id":85,"name":"server"},{"id":86,"name":"serverless"},{"id":70,"name":"storage"},{"id":75,"name":"system-design"},{"id":79,"name":"terminal"},{"id":29,"name":"testing"},{"id":12,"name":"ui"},{"id":50,"name":"ux"},{"id":88,"name":"video"},{"id":20,"name":"web-app"},{"id":35,"name":"web-server"},{"id":43,"name":"webassembly"},{"id":69,"name":"workflow"},{"id":87,"name":"yaml"}]" returns me the "expected json"