Page 1 of 2

Total SAH of a BVH

Posted: Wed Feb 22, 2012 10:46 am
by Dade
I'm familiar with the concept of SAH (Surface Area Heuristic) to evaluate the quality of a split in a BVH:

C = Ct + SA(B1) / SA(B) * P1 *Ci + SA(B2) / SA(B) * P2 *Ci

where:

Ct = node traversal cost
SA() = surface area
B1 = left node bounding box
B2 = right node bounding box
B = parent node bounding box
P1 = left node primitive count
P2 = left node primitive count
Ci = primitive intersection cost

However recently, while I was rereading an old paper, I have found the concept of "total SAH" of an complete BVH. It is indeed a very useful value to compare the quality of different BVH building methods but the paper doesn't explain how to compute the total SAH so I was wondering what is the best way.

For instance, is it just the sum of the above formula applied to each node of the BVH ? Should I divide by the SA(parent node) or SA(root node) ?

Re: Total SAH of a BVH

Posted: Wed Feb 22, 2012 12:24 pm
by darkhorse64
There is an example of doing that in the Embree source code

Re: Total SAH of a BVH

Posted: Wed Feb 22, 2012 3:01 pm
by graphicsMan
It seems to me that you'd want more-or-less an average cost of traversing the tree. If you had this, you could insert the tree as a node into another tree with the SAH :)

If you think about this at any given node, it would be

Ct + Pl*Cl + Pr*Cr

where
Ct = node traversal cost
Pl = probability of traversing left
Pr = probability of traversing right
Cl = cost of traversing left subtree (recursive)
Cr = cost of traversing right subtree (recursive)

With a kd-tree, the probabilities will always be summed to >= 1, while with a BVH they may be < 1. If you start this recurrence at the root, you ought to arrive at the average cost of traversing the tree, unless I missed something (this is my first time formulating this, so maybe I missed something?). Note that only at the leaves will you have the SAH that you're familiar with in your first post.

Re: Total SAH of a BVH

Posted: Wed Feb 22, 2012 3:31 pm
by jbarcz1
For a BVH, you can actually expand the recurrance into something like:

sum( Ci * Ai/Aroot )

Where Ci is the cost of node i (Ct for an inner node, sum of primtiives for a leaf), and Ai is its area.
(I may have it wrong above, I worked it out and wrote it down, but I dont have my notebook handy).

The neat thing about it is that if you assume one primitive per leaf, the cost of any given BVH depends only on the sum of inner node surface areas. I've often wondered if you couldn't derive some cool new tree construction technique based on this: start at one prim/leaf, then optimize the inner nodes, then bottom-up merging of leaves until cost doesn't improve.

Re: Total SAH of a BVH

Posted: Thu Feb 23, 2012 11:43 am
by Dade
darkhorse64 wrote:There is an example of doing that in the Embree source code
Oh, thanks, I didn't know, going to check the sources.

Re: Total SAH of a BVH

Posted: Thu Feb 23, 2012 2:11 pm
by Dade
Dade wrote:
darkhorse64 wrote:There is an example of doing that in the Embree source code
Oh, thanks, I didn't know, going to check the sources.
Embree uses "Total SAH" that matches graphicsMan's definition however they seems to use an "un-normalized" value:

SAH(node) = SA(node.parentNode.BBox) * Ct + SAH(node.leftChild) + SAH(node.rightChild)
SAH(leaf) = Ci * SA(leaf.parentNode.BBox) * leaf.primitiveCount

I'm missing something or their "Total SAH" changes if you change the scale of the objects ? Wouldn't be better to use a "normalized" value ? Something like:

SAH(node) = Ct + SAH(node.leftChild) / SA(node.parentNode.BBox) + SAH(node.rightChild) / SA(node.parentNode.BBox)
SAH(leaf) = Ci * leaf.primitiveCount

(i.e. divide everything for the parent node surface area)

P.S. it is quite amazing the pervasive way Embree uses SSE (and in a readable way, intrinsics are such a pain to use) :!:

Re: Total SAH of a BVH

Posted: Thu Feb 23, 2012 3:59 pm
by jj99
I was looking at this code too. Their value seems completely useless IMHO :)... But I mupltiplied the SAH(leaf) by the area of the child box. It seems working. If I remove the bvh rotation, it increases.

Re: Total SAH of a BVH

Posted: Thu Mar 01, 2012 10:42 am
by Dade
After a bit of tests the graphicsMan's formulation seems the most coherent with experimental results (i.e. an accelerator structure with better total SAH leads to better performances):

// The cost of a node is equal to the probability to hit a child multiplied for the cost of the child
SAH(node) = Ct + (SA(node.leftChild) / SA(node.BBox)) * SAH(node.leftChild) + (SA(node.leftChild) / SA(node.BBox)) * SAH(node.rightChild)

// Classic SAH applied to leafs
SAH(leaf) = SA(node) / SA(node.parentNode.BBox) * Ci * leaf.primitiveCount

Where:

Ct = node traversal cost
Ci = primitive intersection cost
SA() = surface area

It is also trivial to adapt the formula to BVHs with more than 2 child per node (i.e. QBVH) and with leafs with rounded number of primitives (i.e. groups of 4xTriangles for SSE 1xRay/4xTriangles intersection) by rounding the leaf.primitiveCount value (for instance (leaf.primitiveCount + 3) / 4 for group of 4).

Re: Total SAH of a BVH

Posted: Thu Jul 31, 2014 4:47 am
by shiqiu1105
Dade wrote:After a bit of tests the graphicsMan's formulation seems the most coherent with experimental results (i.e. an accelerator structure with better total SAH leads to better performances):

// The cost of a node is equal to the probability to hit a child multiplied for the cost of the child
SAH(node) = Ct + (SA(node.leftChild) / SA(node.BBox)) * SAH(node.leftChild) + (SA(node.leftChild) / SA(node.BBox)) * SAH(node.rightChild)

// Classic SAH applied to leafs
SAH(leaf) = SA(node) / SA(node.parentNode.BBox) * Ci * leaf.primitiveCount

Where:

Ct = node traversal cost
Ci = primitive intersection cost
SA() = surface area

It is also trivial to adapt the formula to BVHs with more than 2 child per node (i.e. QBVH) and with leafs with rounded number of primitives (i.e. groups of 4xTriangles for SSE 1xRay/4xTriangles intersection) by rounding the leaf.primitiveCount value (for instance (leaf.primitiveCount + 3) / 4 for group of 4).
I found this very interesting.
How do we use this formula if we build the BVH top-down though. We rely on SAH to split the node, yet the formula requires the node splitted to evaluate.

Re: Total SAH of a BVH

Posted: Thu Jul 31, 2014 6:08 am
by shiqiu1105
jj99 wrote:I was looking at this code too. Their value seems completely useless IMHO :)... But I mupltiplied the SAH(leaf) by the area of the child box. It seems working. If I remove the bvh rotation, it increases.
So the SAH calculation of embree is wrong?