Different tree size configurations of PointDataGrid

[kdma...@gmail.com]

PointConversion.h:createPointDataGrid() function appears to not be fully templated on the call parameter grid types:

    using PointDataTreeT = typename PointDataGridT::TreeType;

    using LeafT = typename PointDataTree::LeafNodeType;

    using PointIndexLeafT = typename PointIndexGridT::TreeType::LeafNodeType;

    using PointIndexT = typename PointIndexLeafT::ValueType;

    using LeafManagerT = typename tree::LeafManager<PointDataTreeT>;

    using PositionAttributeT = TypedAttributeArray<Vec3f, CompressionT>;

the LeafT uses the default LeafNodeType of the surrounding namespace rather than the one provided by the template deduction.

Is this a mistake or is there a specific reason? Since everything else uses the template deduction it seems like their might be a complicated reason for the non-template-deduced "using LeafT ..." line.

The reason I run in to this is because I want to increase the leaf node size, which I do like so:

namespace vb = openvdb::v8_0;

namespace vt = openvdb::tree;

namespace vp = openvdb::v8_0::points;

using EnlargedPointDataTree = vt::Tree<vt::RootNode<vt::InternalNode<

    vt::InternalNode<vp::PointDataLeafNode<vb::PointDataIndex32, 4>, 4>, 5>>>;

using EnlargedPointDataGrid = openvdb::Grid<EnlargedPointDataTree>;

I later do:     

openvdb::initialize();

EnlargedPointDataGrid::registerGrid(); 

 fails with the error:

/nix/store/jy5q3n6mwcbr4r5kr3dv1mzaqsjwkwj9-openvdb/include/openvdb/points/PointConversion.h|656 col 9| note: no known conversion for argument 1 from 'openvdb::v8_0::tree::LeafManager<openvdb::v8_0::tree::Tree<openvdb::v8_0::tree::RootNode<openvdb::v8_0::tree::InternalNode<openvdb::v8_0::tree::InternalNode<openvdb::v8_0::points::PointDataLeafNode<openvdb::v8_0::PointIndex<unsigned int, 1>, 4>, 4>, 5> > > >::LeafType' {aka 'openvdb::v8_0::points::PointDataLeafNode<openvdb::v8_0::PointIndex<unsigned int, 1>, 4>'} to 'LeafT&' {aka 'openvdb::v8_0::points::PointDataLeafNode<openvdb::v8_0::PointIndex<unsigned int, 1>, 3>&'}

due to LeafT getting bound to the default PointDataLeafNode size in PointConversion.h:656

There are also a few other conversion errors for the leaf node type cast internal to PointAttribute.h

I may just be making the different sized tree wrong with a simple usage error. I wasn't able to find any creation of different sized point data grid trees in the test suite or documentation they all use the default so an example might also solve my issue.

Thank you for any ideas!

[Dan Bailey]

Hi,

Thanks for reporting this, it's just a mistake. I've gone through the Point headers and tried to fix up any of these that aren't correct as well as fixing a number of much less serious cases where we happen to use the same name for the template type as the alias. Finally, I added a new unit test that builds the PointDataGrid with a different configuration and verified that this now works as expected. You can find the PR here:

https://github.com/AcademySoftwareFoundation/openvdb/pull/1030

I am curious why you wish to use a larger leaf node though? In the Technical Steering Committee, we have been discussing potentially dropping support for non-standard tree configurations in the future, so it's helpful for us to hear about different use cases where people are doing this if you'd be willing to share a bit more information?

Thanks,

Dan

[kdma...@gmail.com]

Oh thank you for that excellent PR! I'm developing from it.

I recently started testing PointDataGrid in high-scale, sparse neuroimaging research for stenciled / fastsweeping methods with grids of several attribute values. At a high level, the unique spatial coherence of the data has sparsity that the default tree is not necessarily optimized for, for example for minimum footprint, so I am partially reproducing some of the tradeoffs from the 2013 paper for a particular data set. Since the attributes are tied to leaves, I also ideally need to balance the attributes used by a thread to fit in L1 or L2 while still balancing the work effectively. The parallel overhead of my algorithm also increases with smaller regions of independent processing subdomains. In short, the flexibility of the OpenVDB trees is incredible and saves researchers, domain specific engineers, etc. having to reimplement comparisons. It's also an excellent example of C++'s power with templating and performance via compile-time optimizations. But, I'm also new to the openvdb code base so changing the tree size might also not be the most effective approach for my use case.

Instead of changing the tree defaults I can increase the voxel size to increase the attribute size per leaf to utilize more of the caches during a single threads processing.  However, at least from what I understand this has a major down side. When there are multiple points per voxel you are forced to search through all points at a particular voxel if you need to access a random point. My algorithm iterates over a sparse (.1 - 3% active in original image bounding index space) set of points from a FIFO or queue specific to each leaf such that the needed leaf attributes are not constantly reloaded and the accesses are fast using all the engineering behind the attributes classes. Pulling from a FIFO means that the point traversal within a leaf is random however. Additionally I do star stencil gather or scatters at these points from the FIFO. The access indirection cost of having too many points per voxel doesn't appear worth it in my stencil access of exact coordinates, so I currently have 1 point per voxel via voxel size 1, set in world/local space. Like other posters on this forum, I don't ever load the position attribute until visualizing in Houdini. Can the PointIndexGrid prevent having to iterate over the points per voxel, are any other tricks? Doesn't seem like I can prevent all those unnecessary accesses since it's just a sparse index list, right?

I haven't implemented or tested yet whether my current approach is better than separate non-point grids, separating the attributes needed at each point. I also could have a grid of type struct that contains all of the needed fields corresponding to the attributes instead of using the PointDataGrid. It may also be possible to adapt some of my algorithms to have the traversal pattern as in fastsweeping.h described in the 2017 fastsweeping paper and remove the FIFOs.