Motivation

[SteveMacenski]

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?!)

[facontidavide]

I am glad you ask, also because I learn about OpenVDB thanks to spatio_temporal_voxel_layer. 😉

My number one motivation is fun: I love coding.

But as a roboticist, I have the following motivation:

• I want to build a drop-in replacement for OctoMap.
• OpenVDB is a big library with a lot of terms focused on computer graphics. Its size and documentation is intimidating for roboticists. I want to create a small and easy-to-read one, with an easy-to-integrate, header-only, core.
• Third reason...

On a good number of benchmarks, I am faster than OpenVDB 😎

[facontidavide]

In a sense, I want Treexy to be the same that NanoFlann is to libFlann.

An efficient and small library that people can embed quickly in their projects.

[SteveMacenski]

Yeah, Octomap is pretty old and not really the thing I want to be using anymore. If not OpenVDB, some sort of grid_map or other sparse occ grid. OpenVDB has some issues in 20.04 that wouldn't let me release STVL to binaries due to some issues in the binaries in OpenVDB from {whoever releases those binaries which I was never able to figure out}. If we continue to have that issue in 22.04 for Humble, I'll be seriously considering stripping out OpenVDB to something else for STVL because that has to get out in binary form.

But more largely, whenever I get back to environmental modeling work, I'll be doing some trade-studies on available libraries to base off of. Why do you figure yours is faster? Dreamworks has some real resources...

[facontidavide]

Well, you can download and run the benchmarks RIGHT now 😄

Treexy is a header-only c++17 library, therefore any problem with the binaries would be gone. Can be precompiled, of course.

I'll be seriously considering stripping out OpenVDB to something else for STVL because that has to get out in binary form.

Well, you can use NanoVDB, or... Treexy :)

Why do you figure yours is faster? Dreamworks has some real resources...

First of all, I don't "need" to be faster: equally fast is ok too. If finally, I realize that Treexy is slower... well, bad luck!
Just because hash maps exist already, people still try their own implementation and, sometimes, they are faster than well established alternatives.

But there is a technical reason too. You may know that the hierarchy of OpenVDB is composed of 4 layers:

Treexy uses only 1 (not 2) Internal layer. This means one less level of indirection that will pay off in certain cases, precisely those cases that I think are relevant for me.

What we lose is the ability to "leap-frog" bigger cubes. This is relevant for ray-tracing applications where you want to find the intersection between a ray and a volume, but I won't need this.

I started this project the last week (even if it has been in the back of my mind for a long time).

I think you may want to give it a try, do some benchmark and... let me know 😉

[SteveMacenski]

It'll probably be quite awhile before I circle back to this, I can only handle 2 big projects at a time 😆. Once I'm done with some planning and control work, this will be back on my agenda. But this is cool to see!

[YoshuaNava]

@facontidavide Sorry for bringing this issue back to life 🙂

I'm interested in this library and in the insights you present in #1 (comment).

I wanted to ask you a few questions, if it isn't much bother:

1. Is the difference in the number of internal nodes equivalent to using openvdb::Tree3 or something else entirely?
2. Can you explain a bit the memory allocation strategy for Treexy?
   a. In the scenario of a point being inserted into Treexy, what is allocated? Which elements of the tree topology and data containers are added into the tree?
   b. Do you allocate voxels sparsely, or by blocks?
   c. A grosso modo, what strategy do you have in mind to represent free space?
3. What are your target use cases for the library? More particle/point cloud, or level-sets/SDF mapping?

Thank you very much in advance.

Best regards,
Yoshua

[YoshuaNava]

HI @facontidavide,
I was wondering if you had time to look at my recent question in this issue.

Thank you very much in advance.

[facontidavide]

• voxels allocated by blocks
• main difference with openvdb is 1 internal layer instead of 2. Everything else is the same, conceptually.
• about free space... if you can't find a voxel, it is not there. No strategy
• goal of the library: point cloud processing, in particular as alternative to Octrees

For anyone reading this thread: the library was created mostly for FUN, in particular considering that nanovdb is not in the master branch of openVDB.

[YoshuaNava]

I see. Thanks for the reply. Bonxai looks quite solid.

Have you considered pushing back to the OpenVDB upstream some of the changes? Since the introduction of Bonxai, nanovdb was merged to the master branch, and there is also a templated type within the OpenVDB definitions that creates a tree with one layer less.