Fast, hierarchical, sparse Voxel Grid

Related tags

Miscellaneous Bonxai
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).

Issues
  • 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 8
  • 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 0
  • 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 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 241 Jun 24, 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 604 Jun 23, 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 488 Jun 19, 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 Jun 25, 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 528 Jun 10, 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 108 Jun 27, 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 13 Jun 20, 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 74 Jun 25, 2022
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

linghao.song 19 May 24, 2022
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

Academy Software Foundation 1.7k Jun 23, 2022
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

Tim Davis 612 Jul 1, 2022
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

Peregrine 1.5k Jun 27, 2022
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.

Takuya Matsuyama 184 Jul 3, 2022
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

Michele Caini 6.9k Jun 24, 2022
Typesense is a fast, typo-tolerant search engine for building delightful search experiences.

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

Typesense 10.2k Jun 27, 2022
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

Xingbo Wu 72 Jun 26, 2022
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

Aalto-CFD 40 Jun 5, 2022