topic baffling leaf count in Intel® Embree Ray Tracing Kernels

baffling leaf count

vectorfarmer — Mon, 02 Jul 2012 18:33:44 GMT

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

baffling leaf count

SvenW_Intel — Tue, 03 Jul 2012 05:19:34 GMT

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.

baffling leaf count

vectorfarmer — Tue, 03 Jul 2012 15:02:56 GMT

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

baffling leaf count

SvenW_Intel — Tue, 03 Jul 2012 16:47:44 GMT

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.

baffling leaf count

vectorfarmer — Tue, 03 Jul 2012 17:19:34 GMT

Got it.

Thanks again for your help.

best,
vf