search

facontidavide / Bonxai

Fast, hierarchical, sparse Voxel Grid
Mozilla Public License 2.0
659 stars 56 forks source link

Motivation #1

Closed SteveMacenski closed 3 years ago

SteveMacenski commented 3 years ago

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 commented 3 years ago

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

My number one motivation is fun: I love coding.

But as a roboticist, I have the following motivation:

image

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

facontidavide commented 3 years ago

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 commented 3 years ago

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 commented 3 years ago

Well, you can download and run the benchmarks RIGHT now :smile:

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:

image

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.

image

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 :wink:

SteveMacenski commented 3 years ago

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

YoshuaNava commented 2 years ago

@facontidavide Sorry for bringing this issue back to life :slightly_smiling_face:

I'm interested in this library and in the insights you present in https://github.com/facontidavide/Bonxai/issues/1#issuecomment-946078079.

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 commented 2 years ago

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 commented 2 years ago

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 commented 2 years ago

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.