Fast, hierarchical, sparse
Voxel Grid

Davide Faconti, ROSCon 2023

About me●Davide Faconti, nice to meet you!

●Robotic Architect, working at PickNik Robotics●20 years, doing robots of all kinds.

●Author of PlotJuggler and BehaviorTree.CPP

What is Bonxai?

A header-only, single file, C++library
to store volumetric data
in discretized cells,i.e. a Voxel Grid.
Created primarily to manage
3D maps and occupancy grids.

About Bonxai
Bonxai data structure is:● Unbounded: can represent an infinite space● Sparse: only allocates the used cells● Fast: 10x faster than Octomap● Hierarchical: more details in the next slides…
● Typical time complexity to access a voxel isO(1)About Bonxai
Bonxai data structure is:● Unbounded: can represent an infinite space● Sparse: only allocates the used cells● Fast: 10x faster than Octomap● Hierarchical: more details in the next slides● Typical time complexity to access a voxel is O(1)This slide contains a few lies.
Pay attention to the presentation, to learn moreSummary of the presentation, in one slideLiterature“VDB: High-Resolution Sparse Volumes with Dynamic Topology”, presented at SIGGRAPH 2013.
“Octomap: An Efficient Probabilistic 3D Mapping Framework Based on Octrees”, presented at ROSCon
2013"A Sparse-Dense Approach for Efficient Grid Mapping", ICARSC 2018

How to useitOctrees refresher●

Subdivision of the space, where eachcube (Node) is split in 8 cubes recursively.

●The voxel size will tell us when to stop
the recursion.

●Sparse: only defined Nodes are allocated.

●Time complexity of search and update:O(logN), where N is the number of NodesPotential problems with Octrees
Many heap allocations, whenbuilding the tree.

Not cache friendly. Memory isfragmented.

This affects negatively
insertion, searching anditeration times.

Bonxai VS Octree

460.000 points

Example, using 2 cm voxels● Create the grid: 10x faster● Update/Read existing cells: 6x faster● Iterate through all cells: 10x faster

Warning! Performance will vary a lot, based on thedensity of the data, but Bonxai always wins

How Bonxai works
under the hoodBonxai/VDB data structure
Bonxai data structure, implemented by VoxelGrid<DataType>:●

RootMap: a hashmap, where each element contains an instance of InnerGrid●

InnerGrid: a 3D grid (NxNxN) , each element contains a pointer to a LeafGrid.

●

LeafGrid: a 3D grid (MxMxM), each element contains a DataType●

Grids have a bitfield mask, to check if a cell is active or not.

RootMap

InnerGrid

LeafGrid

Voxel Coordinates (int32):

X

0

1

2

3

4

567…

2930

31

Y

01234567…

2930

31

Z

0

1

234567…

2930

31Given a set of coordinates, we want to find a unique instance of DataTVoxel Coordinates (int32):

X0

1

2

34

567…

2930

31

Y

0

1

234567…

2930

31

Z

0

1

2

3

4

567…

2930

31

These bits are used to find avalue in the hashmap, i.e.
RootMap.

Voxel Coordinates (int32):

X

0

1

2

3

4

567…

2930

31

Y

0

1

2

3

4

5

67…

2930

31

Z

0

1

2

3

4567…

2930

31

These bits are used to find theindex into the 4x4x4 InnerGrid.

Voxel Coordinates (int32):

X01234567…

2930

31

Y

01234567…

2930

31

Z

01234567…

2930

31

These bits are used to find theindex into the 8x8x8 LeafGrid.

Spatial coherency in LIDAR and RGB-D pointclouds
Distribution of points in PointClouds is not completely “random”.
When data is generated by a RGBD camera or a LIDAR,
a point has a high probability to be close of the previous one

Spatial coherency and caching

High probability that theLeafGrid is the same, for two
consecutive points

Using a simple caching strategy, we canavoid
calling std::unordered_map<>::find()Bonxai-based probabilistic mapping
Using Bonxai + Eigen,I reimplemented the Octomap
probabilistic map algorithm,
including raycasting,in 250 lines of code

Octomap

BonxaialmostLie: “Bonxai is 10x faster than Octomap”

Actually, 13-19x faster on theKitti LIDAR odometry datasetsLie: “Bonxai is Unbounded”
Since we use 32 bits indexes to represent the voxel coordinates, themaximum representable space is actually limited.

Given a voxel size equal to 1
cm, the maximum size of thegrid is about 40,000 Km.

Lie: “Bonxai is Sparse”

Technically, it is a Sparse-Densestructure, since the grid at thebottom layers is dense.
In practice, memory overhead is
not a problem.

Lie: “this presentation is about 3D mapping”
No, this talk is about a data structurethat you can easily add to your projects
Just copy “bonxai/bonxai.hpp” into your “3rdparty” folder and enjoy your life!

Thank you for your attention :)https://github.com/facontidavide/Bonxai