Community
cancel
Showing results for
Did you mean:
Beginner
101 Views

## baffling leaf count

If I traverse the bvh2 tree and count the number of leaves, I come up with the correct number of leaf nodes but if I linearly go through the nodes array using the following code, I come up short:
int leaves = 0;
size_t numnodes = getNumNodes();
for (size_t i = 0; i < numnodes ; i++) {
const int nodeID = id2offset(i);
const Node& n = node(nodes, nodeID);
if (n.child[0] < 0)
++leaves;
if (n.child[1] < 0)
++leaves;
}

The actual numbers computed by getNumNodes and getNumLeaves are:
nodes = 18935
leaves = 18936
The numbers I come up by going through the nodes array:
nodes=18935
leaves=15121

What am I doing wrong here?

thanks,
vf

4 Replies
Moderator
101 Views
You have to iterate over the number of nodes allocated in the node array (numAllocatedNodes). However, even then you have to make sure that not used nodes are initialized to some value for this iteration to make sense.
Some nodes in these arrays are not used as multiple threads take blocks of nodes out of this array. Some blocks at the end might end up partly filled.
Beginner
101 Views
Hi Sven,

Thanks for your reply. I realized that last night when I started printing the nodes and seeing all these empty ones. I thought the following piece of code is getting rid of the unused space:
/*! free temporary memory again */
bvh->nodes
= (BVH2::Node*) alignedRealloc(bvh->nodes, atomicNextNode
* sizeof(BVH2::Node));

So the above instruction removes the unused blocks, but there are still unused space withing the currently used blocks? Could you please clarify this?

thanks,
vf
Moderator
101 Views
The instruction you cited removes overallocated memory. However, each thread grabs a block of nodes from the node array atomically. The thread then fills this block until it is full and then takes a new block and so on. At the end of the build the threads will however very likely not have filled up their current block completely.
Beginner
101 Views
Got it.

Thanks again for your help.

best,
vf