Ideal representation for 3D point clouds with multiple fields

[YoshuaNava]

Hi,
Thanks for this awesome library.

Im planning to use OpenVDB for 3D mapping. For that, I need to represent 3D points, normals (always expected, at the point, and leaf node levels) and optional multi-dimensional fields (e.g. occupancy, signed distance, local curvature, Color, etc). I would also like to use standard VDB tools to perform filtering, ray casting, and meshing.

After reading through the documentation, GitHub issues/discussions and Google forum threads I found at least 4 suggested approaches to represent point cloud data:

1. Create a custom voxel type: This could be advantegeous as all data would be stored together per voxel. However, I would miss the chance to use many of the VDB tools, and I would need to rebuild the library to add a new data field,
2. Use multiple FloatGrids: This is recommended by K. Museth in this discussion, as well as in the VDB Cookbook. It is described as a flexible and memory-efficient approach, even though we would need to perform multiple tree traversals to find all the fields that correspond to a single node,
3. Use PointDataGrid with attributes: the OpenVDB Cookbook for Points shows how to append optional attributes to voxels. However, there is no information on how optional data is represented in memory, whether attributes are saved into files, can be visualised, if they can be used for processes like meshing, and how efficient it is to access and modify them,
4. Use a standard large VDB voxel type to represent arbitrary data via a packed struct: First described here, this approach allows arbitrary data fields to be stored per voxel but requires a reinterpret_cast to access the stored values. Although quite insightful and efficient, it bears higher complexity to access values, and potentially prevents the use of VDB utilities.

I wanted to ask for your feedback on this matter. There is no direct comparison between the approaches cited above, and I think there is high potential for VDB to deliver value to 3D mapping.

Best regards,
Yoshua Nava

[Idclip]

Hi Yoshua Nava,

This is a great question. I'll do my best to answer but I'm sure other members of the TSC will have thoughts on this too.

My TL;DR would be to, for dynamic point cloud representation, use PointDataGrids. If you data is static and can fit into LeafNodes, start by using multiple grids.

---

Create a custom voxel type / Use a standard large VDB voxel type to represent arbitrary data via a packed struct.

These two methods are extremely similar. Creation/deletion would be relative to the ValueType you end up choosing. So long as the type is trivially copyable the data can be represented efficiently (see NodeUnion.h). Organizing the data in this way would allow you to represent it using a single tree and thus a single topology. This would use less memory than representing the data in multiple FloatTrees, however the cost of the topology is usually fairly light in comparison to the type of data you're thinking of storing.

As well as having all element data available on request, using a single topology would also allow you to write algorithms which could benefit from subsequent accesses using VDB's ValueAccessor. If you write two or more "disjoint" algorithms then there is little benefit to this data living together. For example if you need to process 'occupancy' on all points before processing 'curvature', then whether this data lives in a single consolidated structure won't have much of an impact.

Another thing to think about is whether or not you need serialization support for this data or if it's only required as a temporary in-memory representation (i.e. [read custom data in]->[transform to vdb]->[process]->[back to custom format]->[write]). If you're reading and writing it as VDB data you may benefit from Delay Load support. This is where leaf data is de-serialized on buffer accesses, not on file read. If you only need to read portions of your data set or if you only need to read specific attributes then storing all this data in one type may not be ideal as all data that corresponds to a particular leaf node would need to be read from disk.

Regarding using existing VDB algorithms with custom data types; it's very much dependent on the type of operation you'd want to run. It is possible to, say, run a level set utility on a custom type - but it would require your type to define various operations. These operations may also not be valid with other VDB algorithms. Whether you use a custom type or use an existing VDB type doesn't really change this as I doubt your data will have a semantic meaning as a VDB type. That is, you'd still have to define how your data is interpreted between different VDB tools.

These methods can be compared directly to the multiple FloatGrid solution; if you're writing a bunch of mega-tools which need all point data, and the data can be represented as a trivial type, then it may be worth using a custom type. There is little benefit to using an existing VDB type as far as utilizing existing VDB algorithms go, unless your data makes sense in the context of the VDB type you use. The main thing using an existing VDB type would give you is native serialization support in other applications that read VDB files.

Use multiple FloatGrids

The main trade off here are the duplicate topology and inability to share ValueAccessor caches. You would however benefit from being able to individually de/serialize data if that was important to you. It very much depends on the type of algorithms you want to run and whether you're running them across the entire data structure. This would lend itself far nicer to using existing VDB tooling. If you choose either the above or this technique, my advise would be to start off with multiple grids and see what kind of performance/usability you get. You should find it easier to implement your tools and use existing methods with this method and can switch if you think it's necessary.

You can currently only store a single Index32 value alongside LeafNodes in a given tree. If you need more flexibility, my advice would be to maintain a tiled tree of values which you can lookup into. Because this tree would hold a single value per Leaf level node, you would never need it to contain a dense topology. You would still pay a cost to lookup into this tree but it would be fairly lightweight.

PointDataGrids / PointIndexGrids

I think conceptually this is the way to go. I'm not entirely sure how you plan to represent 3D point information in a numerical VDB without discretizing it or without using dynamic data per leaf. Using PointData/PointIndex Grids would allow you to store any number of 3D point information per leaf without the need to worry about discretizing it. With PointDataGrids, each attribute is stored in separate arrays relative to a LeafNode. Attributes can be manipulated independently (to each other and to other leaf nodes). This includes independent access, delay loaded de-serialization (PointDataGrids include I/O support for their attributes, PointIndexGrids don't) and creation/destruction/resize. Most PointDataGrid tools are templated to work with custom attribute types which allows you to define your own and maintain the native tool support.

In terms of voxel storage, both PointIndexGrids and PointDataGrids are simply integer grids in disguise. PointIndexGrids requires you to maintain 'sidecar' data which actually stores your data; you can use the grid to provide you with a spatially organised list of indices into this data. PointDataGrids on the other hand store their attributes and attribute information alongside the LeafNodes which implicitly gives you a data structure that maintains spatial locality whilst using different algorithms. I would only suggest using PointIndexGrids if you cannot pay the conversion cost to PointDataGrids (which is small) or if reformatting your data into a PointDataGrid doesn't make sense (if you only need to point to an existing data structure).

PointDataGrids have been designed to be fast and follow a similar tool pattern to VDB volumes; that is, tools multi-thread across branches of the tree. With PointDataGrids you can have a dynamic number of points per branch/LeafNode, so you may find that some tools work better depending on the distribution of your data. It's very hard to make 1:1 comparisons with the volume storage solution! To put it into perspective though, a naive access to a value in a PointDataGrid is the same speed as accessing a VDB voxel, plus an additional lookup into the list of attributes. This additional lookup is not expensive and tools are typically written in such a way that this cost is only paid once per LeafNode or once per active voxel.

You could also use PointDataGrids in a roundabout way to store per node information. As PointDataGrid attributes are dynamic, they can be collapsed to a single value if they are uniform. So if you need more than a single Index32, you could instead add uniform attribute(s) which represents a Node's summary value(s).

You can't currently go directly from a PointDataGrid to a mesh, you would first have to discretize their positions or some attribute to a volume and then use existing tools (such as volumeToMesh) to build meshes.

---

Hope this helps!

[YoshuaNava]

Hi @Idclip,

Thank you very much for the answer, it shed light on many aspects of VDB that I was not fully aware yet.

Create a custom voxel type / Use a standard large VDB voxel type to represent arbitrary data via a packed struct.

As well as having all element data available on request, using a single topology would also allow you to write algorithms which could benefit from subsequent accesses using VDB's ValueAccessor. If you write two or more "disjoint" algorithms then there is little benefit to this data living together. For example if you need to process 'occupancy' on all points before processing 'curvature', then whether this data lives in a single consolidated structure won't have much of an impact.

The type of access I expect to do is selective on the type of data, and would probably benefit from the VDB ValueAccessor cache 👍

Another thing to think about is whether or not you need serialization support for this data or if it's only required as a temporary in-memory representation (i.e. [read custom data in]->[transform to vdb]->[process]->[back to custom format]->[write]). If you're reading and writing it as VDB data you may benefit from Delay Load support. This is where leaf data is de-serialized on buffer accesses, not on file read. If you only need to read portions of your data set or if you only need to read specific attributes then storing all this data in one type may not be ideal as all data that corresponds to a particular leaf node would need to be read from disk.

I wasn't aware of this capability. It sounds really well suited for streaming data directly from disk. Thanks for the info!

Regarding using existing VDB algorithms with custom data types; it's very much dependent on the type of operation you'd want to run. It is possible to, say, run a level set utility on a custom type - but it would require your type to define various operations. These operations may also not be valid with other VDB algorithms. Whether you use a custom type or use an existing VDB type doesn't really change this as I doubt your data will have a semantic meaning as a VDB type. That is, you'd still have to define how your data is interpreted between different VDB tools.

This is quite positive to hear. I think for the type of data I'll handle I'll benefit more from, say, neighborhood search and ray-casting, than level-set construction. Not to say that this isn't in my radar, but it could definitely come within a separate software solution / sprint that is specially catered for level-set extraction.

Use multiple FloatGrids

The main trade off here are the duplicate topology and inability to share ValueAccessor caches. You would however benefit from being able to individually de/serialize data if that was important to you. It very much depends on the type of algorithms you want to run and whether you're running them across the entire data structure. This would lend itself far nicer to using existing VDB tooling. If you choose either the above or this technique, my advise would be to start off with multiple grids and see what kind of performance/usability you get. You should find it easier to implement your tools and use existing methods with this method and can switch if you think it's necessary.

I tried this approach, and indeed the memory usage seems a bit higher compared to a custom voxel definition. At this point I would say that this approach bears higher flexibility for introducing new data fields during development. Also, based on what you presented in the first section of your reply, I see the balance tipping more into a custom voxel field, or PointDataGrid more clearly, for production-level systems.

You can currently only store a single Index32 value alongside LeafNodes in a given tree. If you need more flexibility, my advice would be to maintain a tiled tree of values which you can lookup into. Because this tree would hold a single value per Leaf level node, you would never need it to contain a dense topology. You would still pay a cost to lookup into this tree but it would be fairly lightweight.

Thank you very much for proposing this solution, it sounds interesting. One question though: when you refer to a tiled tree, you mean a tree with 1 voxel per leaf node? (e.g. having a voxel block dimension of 0) ❓

I tried this but couldn't get it to compile, as VDB enforces a minimum size of Log2Dim > 1

PointDataGrids / PointIndexGrids

I think conceptually this is the way to go. I'm not entirely sure how you plan to represent 3D point information in a numerical VDB without discretizing it or without using dynamic data per leaf. Using PointData/PointIndex Grids would allow you to store any number of 3D point information per leaf without the need to worry about discretizing it. With PointDataGrids, each attribute is stored in separate arrays relative to a LeafNode. Attributes can be manipulated independently (to each other and to other leaf nodes). This includes independent access, delay loaded de-serialization (PointDataGrids include I/O support for their attributes, PointIndexGrids don't) and creation/destruction/resize. Most PointDataGrid tools are templated to work with custom attribute types which allows you to define your own and maintain the native tool support.

I'm currently implementing this approach. I'l follow up with my conclusions/analysis.

In terms of voxel storage, both PointIndexGrids and PointDataGrids are simply integer grids in disguise. PointIndexGrids requires you to maintain 'sidecar' data which actually stores your data; you can use the grid to provide you with a spatially organised list of indices into this data. PointDataGrids on the other hand store their attributes and attribute information alongside the LeafNodes which implicitly gives you a data structure that maintains spatial locality whilst using different algorithms. I would only suggest using PointIndexGrids if you cannot pay the conversion cost to PointDataGrids (which is small) or if reformatting your data into a PointDataGrid doesn't make sense (if you only need to point to an existing data structure).

Anecdote: I had also considered using PointIndexGrids to co-maintain a dense array of data + its 'spatial indexing structure' (OpenVDB), and I honestly thought this could be convenient (not super fast) for adding and reading data, but a nightmare for removing data, as we would be saving array indices in a large tree.

Said differently, with this approach resizing the dense array to keep its memory footprint limited in the event of point removal could be way too complex.

PointDataGrids have been designed to be fast and follow a similar tool pattern to VDB volumes; that is, tools multi-thread across branches of the tree. With PointDataGrids you can have a dynamic number of points per branch/LeafNode, so you may find that some tools work better depending on the distribution of your data. It's very hard to make 1:1 comparisons with the volume storage solution! To put it into perspective though, a naive access to a value in a PointDataGrid is the same speed as accessing a VDB voxel, plus an additional lookup into the list of attributes. This additional lookup is not expensive and tools are typically written in such a way that this cost is only paid once per LeafNode or once per active voxel.

I'll try to profile this for my application.

Hope this helps!

It helps a lot!

[YoshuaNava]

@Idclip thank you very much for your thorough reply. I'm reading through it in full detail 🙂