How to get the number of points corresponding to an octree node

[lopeLH]

Assuming we have an initialized a FEMTree instance using FEMTreeInitializer with a point stream, is there a simple way to obtain the number of points contained in a given leaf node of the tree?

[mkazhdan]

Yep. When you call FEMTreeInitializer::Initialize, the 6th argument is of type: std::vector< typename FEMTree< Dim , Real >::PointSample >. This an std::vector of objects of type NodeAndPointSample: template< unsigned int Dim , class Real > struct NodeAndPointSample { RegularTreeNode< Dim , FEMTreeNodeData , depth_and_offset_type > *node; ProjectiveData< Point< Real , Dim > , Real > sample; };

The first member, "node", points to the octree node associated with this piece of data. The second member, "sample", is an object of type ProjectiveData: template< class Data , class Real > struct ProjectiveData { Data data; Real weight; ... } The first member, "data", stores the accumulation of the point positions falling in the node. The second member, "weight", stores the count of number points falling in the node. (The average is the ratio, but I believe you just want the count.)

[lopeLH]

Great, thanks a lot for your answer. I do have a few follow up questions: I want to find the sample count for a FEMTreeNode * I got by calling tree.leaf() on a 3D position.

1. Are all leaf nodes guaranteed to have an associated entry in the NodeAndPointSample vector you mentioned?
2. If not, can I assume leaf nodes not referenced in the vector have sample count of zero?
3. What about non-leaf nodes? I assume those will not be present, and that in order to get the sample count for a non-leaf I need to recursively traverse its children until I reach and sum-up the sample count of all leaf nodes bellow it.
4. Any tips on how to efficiently find the NodeAndPointSample within the vector for which .node is my query node? First thing that comes to mind is creating a std::unordered_map<FEMTreeNode *, size_t> at the beginning to accelerate subsequent queries. But maybe there is a built-in mechanism already.

Thanks again for your time. Very much appreciated.

[mkazhdan]

1. Child nodes are generated as "broods" (either a node is not refined or all eight children are generated) so there could be nodes without samples.
2. Yes. I believe so.
3. I believe they are included, and they store the sum of the counts from their children.
4. Within the FEMTreeNodeData object, every octree node stores a unique index (FEMTreeNodeData::nodeIndex). The value should be in the range [0,FEMTree::nodeCount). You can use this by proceeding in two steps. (1) Create a sample_count_per_node array of size FEMTree::nodeCount, initialized to zero. (2) Run through the vector of NodeAndPointSample data, get the index of the associated node, and write the sample count into the sample_count_per_node array. This way, when you are given a node, it's just a matter of using its index to look up the appropriate entry in the sample_count_per_node . (One thing to look out for is that at certain points in the code, the nodes are re-indexed. However, indices will befinalized after the call to FEMTree::finalizeForMultigrid so if you construct the sample_count_per_node array after that call, you should be OK.)

[lopeLH]

Thanks again. I am getting a FEMTreeNodeData::nodeIndex of -1 for some of the entries in the NodeAndPointSample vector. Is that expected?

sample_count_per_node.resize(m_tree->nodeCount(), 0.0f);
for (const auto & p: samples){
    if (p.node->nodeData.nodeIndex >= sample_count_per_node.size()){
        std::cout << "Bad index: " << p.node->nodeData.nodeIndex << std::endl;
        throw std::runtime_error("Bad index while filling sample_count_per_node");
    }
    sample_count_per_node[p.node->nodeData.nodeIndex] = p.sample.weight;
}

which gives Bad index: -1.

[mkazhdan]

For the implementation, the code "trims off" nodes in regions of sampling density. However, it doesn't explicitly remove them. In practice, it "zeros" them out by setting their index to -1. You can try to mitigate this by setting the number of samples-per-node to a small value. (e.g. less than one).

[mkazhdan]

Looking at it some more, I realize that my answer to the second question was wrong -- values are only stored for the leaf nodes. Unfortunately, this also means that what I described above wouldn't quite work.

If you're only interested in getting the number of samples sitting in nodes after trimming, you can get that by running the following code after the call to finalize the tree (FEMTree::finalizeForMultigrid):

    std::vector< Real > samplesPerNode( implicit.tree.nodeCount() , 0 );
    for( auto s : *samples )
        for( const FEMTreeNode *n = s.node ; n ; n=n->parent )
            if( n->nodeData.nodeIndex!=-1 )
                samplesPerNode[ n->nodeData.nodeIndex ] += s.sample.weight;

This populates the vector samplesPerNode with the sample counts.

In particular, given an FEMTreeNode pointer node, with node->nodeData.nodeIndex!=-1, the count of samples falling inside node is samplesPerNode[ node->nodeData.nodeIndex ].

[lopeLH]

That makes a lot of sense, and matches what I was observing. Will try this out early next week, and close the issue if I encounter no further difficulties.

Thanks a lot for the support.

[lopeLH]

This worked as expected. Thanks for the support. closing the issue :+1: