Treexy is a library that implements a compact hierarchical data structure that can store and manipulate volumetric data, discretized on a three-dimensional 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 
   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 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
Fast, hierarchical, sparse Voxel 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 271 Aug 6, 2022
Fast, hierarchical, sparse Voxel 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 274 Aug 7, 2022
DimensionalAnalysis - A compact C++ header-only library providing compile-time dimensional analysis and unit awareness

Dimwits ...or DIMensional analysis With unITS is a C++14 library for compile-time dimensional analysis and unit awareness. Minimal Example #include <i

NJOY 8 Jul 8, 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 533 Jul 27, 2022
Linux x86_64 Process Injection Utility | Manipulate Processes With Customized Payloads (beta)

K55 - Linux x86_64 Process Injection Utility (C++11) About K55 (pronounced: "kay fifty-five") The K55 payload injection tool is used for injecting x86

Josh Schiavone 57 Jul 6, 2022
Volumetric progressive photon mapping written in C++.

volppm Volumetric progressive photon mapping written in C++. WIP. Features Homogeneous medium Hero wavelength sampling for chromatic absorption/scatte

yumcyawiz 33 Jul 20, 2022
KernelReadWriteMemory - Simple code to manipulate the memory of a usermode process from kernel.

KernelReadWriteMemory Simple proof of concept -code to manipulate the memory of a usermode process from kernelmode of a windows NT operating system. T

Zer0Mem0ry 144 Jul 16, 2022
A Quake Enhanced mod to manipulate entities. Inspired by the Half-Life metamod plugin 'Entmod'

QEEntmod A Quake Enhanced mod to manipulate entities. Inspired by the Half-Life metamod plugin 'Entmod' Can be used standalone or easily implemented i

null 2 Jul 5, 2022
C/C++ Application to solve irrigation rotation whatever two-turn rotation or three-turn rotation, longitudinal section design, hydraulic calculations, and design of hydraulic structures like weirs and tail escape.

Irrigation works C/C++ Application to solve irrigation rotation whatever two-turn rotation or three-turn rotation, longitudinal section design, hydrau

Mohamed Jamal Ghayyad 1 Jun 24, 2022
By putting in a lot of speed, the speed sequence is sorted and divided, three types of speed interval distribution maps are generated.(including broken line graph,histogram and curve graph)

Auto-drawing-speed-range-map By putting in a lot of speed, the speed sequence is sorted and divided, three types of speed interval distribution maps a

wellwellAllwen 4 May 14, 2022
An embedded CAN bus sniffer which is able to monitor any of the vehicle internal CAN bus and perform some action by triggering new CAN messages.

An embedded CAN bus sniffer which is able to monitor any of the vehicle internal CAN bus and perform some action by triggering new CAN messages. In this way certain vehicle functionality can be triggered by responding to custom steering wheel button events, or use the vehicle virtual cockpit to display OBD-PIDs values instead of relying on an external display to present new information to the user

null 13 May 21, 2022
A fully-functional open source and open hardware mechanical USB computer keyboard with only three keys!

threeboard threeboard is a fully-functional open source and open hardware mechanical USB computer keyboard with only three keys. It supports multiple

Conor Taylor 97 May 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 489 Jul 13, 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
This project contains three scripts to help working with the steam-runtime, especially outside of Steam.

This project contains three scripts to help working with the steam-runtime, especially outside of Steam. See these blog posts for more details: steam-

Jørgen P. Tjernø 11 Oct 22, 2021
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 109 Jul 23, 2022
Node1D and other 1-dimensional node types for making 1D games in Godot.

Godot 1D Node1D and other 1-dimensional node types for making 1D games in Godot. Have you ever wanted to make 1D games in Godot? ...no? You say you ha

Aaron Franke 12 Jul 31, 2022
Multi-dimensional dynamically distorted staggered multi-bandpass LV2 plugin

B.Angr A multi-dimensional dynamicly distorted staggered multi-bandpass LV2 plugin, for extreme soundmangling. Based on Airwindows XRegion. Key featur

null 18 Apr 17, 2022
Repository created to store a C function library to use in 42 School

Libft of 42. Make with ❤︎ for Luiz Cezario ?? Index What's this Repo? List of Functions Technologies How to Run Find a Bug? Or somenthing need to chan

Luiz lima cezario 8 Feb 20, 2022