Fast, hierarchical, sparse Voxel Grid

Overview

Treexy

Treexy 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").

Treexy data structure is:

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

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

On the other hand, Treexy is brutally faster and, in same cases, even more memory efficient than an Octree.

This work is strongly based on 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 implementations 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)

Treexy 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.

If you think that a data structure like this could be useful for your project, for the time being you should probably considered using OpenVDB itself.

(*) The dimension of the 3D space is virtually "infinite": since 32-bits indexes are used, given a voxel size as small as 1 cm, the maximum range of the X, Y and Z coordinates would be about +/- 20.000 Km (yes, Kilometers).

Benchmark (preliminary)

Take these numbers with a grain of salt, since they are preliminary and 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

On the left side, you see the time needed to create a new VoxelGrid or to update an existing one (less is better). On the right side, the time required to iterate through all the cells in a VoxelGrid.

How to use it

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

#include "treexy/treexy.hpp"

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

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

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

treexy::VoxelGrid<Eigen::Vector4d> vector_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:

// create the accessor ONCE and reuse it as much as possible
auto accessor = grid.createAccessor();

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 )
    {
      treexy::CoordT coord = grid.posToCoord( x, y, z );
      accessor.setValue( coord, 42 );
    }
  }
}

Finally, to read the value of a cell:

// If the value of the cell has never been set, return nullptr
int* value = accessor.value( coord );

Roadmap

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

Frequently Asked Question

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 few important aspects of the algorithm to make it slightly faster, at least for my specific use cases.

How much memory does it uses, compared with Octomap?

It is... complicated.

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

You might also like...
An FPGA accelerator for general-purpose Sparse-Matrix Dense-Matrix Multiplication (SpMM).

Sextans Sextans is an accelerator for general-purpose Sparse-Matrix Dense-Matrix Multiplication (SpMM). One exciting feature is that we only need to p

OpenVDB - Sparse volume data structure and tools

OpenVDB AX Nano Houdini Website | Discussion Forum | Documentation OpenVDB is an open source C++ library comprising a novel hierarchical data structur

The official SuiteSparse library: a suite of sparse matrix algorithms authored or co-authored by Tim Davis, Texas A&M University

SuiteSparse: A Suite of Sparse matrix packages at http://suitesparse.com May 17, 2021. SuiteSparse VERSION 5.10.1 Now includes GraphBLAS, SLIP_LU, and

Peregrine - A blazing fast language for the blazing fast world(WIP)
Peregrine - A blazing fast language for the blazing fast world(WIP)

A Blazing-Fast Language for the Blazing-Fast world. The Peregrine Programming Language Peregrine is a Compiled, Systems Programming Language, currentl

A fast base64 module for React Native

react-native-quick-base64 A native implementation of Base64 in C++ for React Native. 4x faster than base64-js on an iPhone 11 Pro.

Gaming meets modern C++ - a fast and reliable entity component system (ECS) and much more
Gaming meets modern C++ - a fast and reliable entity component system (ECS) and much more

EnTT is a header-only, tiny and easy to use library for game programming and much more written in modern C++. Among others, it's used in Minecraft by

 Typesense is a fast, typo-tolerant search engine for building delightful search experiences.
Typesense is a fast, typo-tolerant search engine for building delightful search experiences.

Fast, typo tolerant, fuzzy search engine for building delightful search experiences ⚡ 🔍

RemixDB: A read- and write-optimized concurrent KV store. Fast point and range queries. Extremely low write-amplification.

REMIX and RemixDB The REMIX data structure was introduced in paper "REMIX: Efficient Range Query for LSM-trees", FAST'21. This repository maintains a

 DLBFoam: Dynamic load balancing for fast reactive simulations
DLBFoam: Dynamic load balancing for fast reactive simulations

DLBFoam: Dynamic load balancing for fast reactive simulations DLBFoam v1.1 - What's new? DLBFoam v1.1 introduces a fully analytical chemistry Jacobian

Comments
  • Motivation

    Motivation

    Hi,

    Can you indicate the motivation of this over OpenVDB if this is more or less a reimplementation of it?

    (also, love that logo, did you make that?!)

    opened by SteveMacenski 9
  • OpenVDB benchmark

    OpenVDB benchmark

    I found that the OpenVDB benchmark for iterating over all cells was using a voxel-On iterator, which is user-friendly, safe, and fast, but not super fast. After running the benchmarks:

    ------------------------------------------------------------------
    Benchmark                        Time             CPU   Iterations
    ------------------------------------------------------------------
    Treexy_Create              2363567 ns      2347860 ns          293
    Treexy_Update              2474811 ns      2472939 ns          279
    Treexy_IterateAllCells       62399 ns        62399 ns        11633 ###
    Octomap_Create            40142650 ns     40142345 ns           17
    Octomap_Update            14739847 ns     14739871 ns           46
    Octomap_IterateAllCells     425256 ns       425099 ns         1667
    OpenVDB_Create             2785683 ns      2713275 ns          267
    OpenVDB_Update             2024528 ns      2024314 ns          347
    OpenVDB_IterateAllCells     202940 ns       202938 ns         3445 ###
    Lama_Create               10595711 ns     10595341 ns           67
    Lama_Update               10171020 ns     10170439 ns           62
    Lama_IterateAllCells       3109528 ns      3109444 ns          218
    

    Reading through this post from the OpenVDB mailing list: https://lists.aswf.io/g/openvdb-dev/topic/32212211?p=,,,20,0,0,0::,,,0,0,0,32212211

    I found that there is a class called LeafManager that allows access leaping from leaf to leaf, which also grants the chance of iterating over the voxels below a given leaf (similar to what Bonxai is doing):

    #include <openvdb/tree/LeafManager.h>
    ...
    // To make a fair comparison, use Log2DIM values similar to Treexy
    using TreeType = openvdb::tree::Tree4<int32_t, 2, 2, 3>::Type;
    using GridType = openvdb::Grid<TreeType>;
    ...
    
    static void OpenVDB_IterateAllCells(benchmark::State& state)
    {
    ...
      openvdb::tree::LeafManager<TreeType> leafManager(grid->tree());
    
      long count = 0;
      for (auto _ : state)
      {
        auto visitor = [&](const TreeType::LeafNodeType& leaf, size_t /*idx*/) {
          for (auto nodeIter = leaf.beginValueOn(); nodeIter; ++nodeIter)
          {
            count++;
          }
        };
        leafManager.foreach(visitor, false);
      }
    

    I ran the benchmarks with this modification and observed a solid improvement:

    ------------------------------------------------------------------
    Benchmark                        Time             CPU   Iterations
    ------------------------------------------------------------------
    ...
    Treexy_IterateAllCells       56818 ns        56818 ns        12411
    ...
    OpenVDB_IterateAllCells      84142 ns        84134 ns         8238
    ...
    

    Furthermore, by switching the tree configuration to openvdb::tree::Tree3<int32_t, 4, 2>::Type;, I was able to get results that almost match those of Bonxai:

    ------------------------------------------------------------------
    Benchmark                        Time             CPU   Iterations
    ------------------------------------------------------------------
    ...
    Treexy_IterateAllCells       57986 ns        57983 ns        11952
    ...
    OpenVDB_IterateAllCells      64163 ns        64159 ns        10636
    

    And when enabling multi-threaded access:

    ------------------------------------------------------------------
    Benchmark                        Time             CPU   Iterations
    ------------------------------------------------------------------
    ...
    Treexy_IterateAllCells       57688 ns        57686 ns        12146
    ...
    OpenVDB_IterateAllCells      39098 ns        39097 ns        17763
    ...
    
    opened by YoshuaNava 3
  • Bug causes by value() before setValue()

    Bug causes by value() before setValue()

    Thanks for your great work. I'm using your VoxelGrid to replace my own grid so that performance can be improved. However, I got a problem. Here's my pseudo code: /* pesudor code auto ptr = accessor.value(coord); if(ptr){ DoSomething(); } else{ accessor.setValue(coord, new_value); } */ If ptr is nullptr(coord has not been setValue before), error happens! "prev_leaf_ptr_ = getLeafGrid(coord, false)" in value() makes prev_leaf_ptr_ nullptr, then "prev_leaf_ptr_->mask.setOn(index)" in setValue() caused segmentfault. Is there anything I'm missing? Thank you.

    opened by getupgetup 2
  • vdbfusion

    vdbfusion

    Hello there! Great work, I wonder how this might speed up the vdbfusion pipeline. Any interest in giving this a try?

    To try the current implementation just pip install vdbfusion and play around, there is also a thin simple C++ API in case you don't want to use Python.

    Best!

    opened by nachovizzo 1
Owner
Davide Faconti
C++ enthusiast, passionate about Robotics. Optimizing code for fun and profit.
Davide Faconti
Treexy is a library that implements a compact hierarchical data structure that can store and manipulate volumetric data, discretized on a three-dimensional grid

Treexy is a library that implements a compact hierarchical data structure that can store and manipulate volumetric data, discretized on a three-dimens

Davide Faconti 307 Sep 20, 2022
CPU Sparse Voxel Octree Implementation

Sparse Voxel Octrees This project provides a multithreaded, CPU Sparse Voxel Octree implementation in C++, capable of raytracing large datasets in rea

Benedikt Bitterli 612 Sep 20, 2022
Off The Grid (OTG) Messenger is an easy way for people to communicate through text messages when in remote areas.

Off The Grid (OTG) Messenger is an easy way for people to communicate through text messages when in remote areas. With a theoretical transmission range of 10 miles (16kms), OTG messenger can be used by groups of people to stay connected when they are in areas not serviced by mobile connectivity.

Trevor Attema 491 Sep 15, 2022
Hierarchical Engine for Large-scale Infrastructure Co-Simulation (HELICS)

A multi-language, cross-platform library that enables different simulators to easily exchange data and stay synchronized in time. Scalable from two si

GMLC-TDC 81 Jul 21, 2022
Example code for the research paper "Masked Software Occlusion Culling"; implements an efficient alternative to the hierarchical depth buffer algorithm.

MaskedOcclusionCulling This code accompanies the research paper "Masked Software Occlusion Culling", and implements an efficient alternative to the hi

null 535 Sep 24, 2022
Real-Time Rendering with Lighting Grid Hierarchy I3D 2019 Demo

Real-Time Rendering with Lighting Grid Hierarchy I3D 2019 Demo Daqi Lin This demo is for the I3D 2019 paper Real-Time Rendering with Lighting Grid Hie

Lin Daqi 110 Sep 13, 2022
this is my simple voxel engine, appart from librairies like glad it is entierly written in C++ and GLSL

simple-voxel-raycaster this is my simple voxel engine, appart from librairies like glad it is entierly written in C++ and GLSL here is a gif: https://

null 1 Jun 4, 2022
(R) Efficient methods and operators for the sparse matrix classes in 'Matrix' (esp. CSR format or "RsparseMatrix")

MatrixExtra MatrixExtra is an R package which extends the sparse matrix and sparse vector types in the Matrix package, particularly the CSR or Rsparse

null 15 Aug 29, 2022
The QPEP-Enhanced Direct Sparse Odometry (DSO) with Loop Closure

QPEP-DSO: Quadratic Pose Estimation Problems (QPEP) Enhanced Direct Sparse Odometry with Loop Closure Code Arch The codes are motivated by DSO (https:

Jin Wu 8 Jun 23, 2022
Implementation of Monocular Direct Sparse Localization in a Prior 3D Surfel Map (DSL)

Implementation of Monocular Direct Sparse Localization in a Prior 3D Surfel Map (DSL)

Haoyang Ye 89 Sep 23, 2022