Total SAH of a BVH back

(L) [2012/02/22] [tby Dade] [Total SAH of a BVH] Wayback!

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) ?

(L) [2012/02/22] [tby darkhorse64] [Total SAH of a BVH] Wayback!

There is an example of doing that in the Embree source code

(L) [2012/02/22] [tby graphicsMan] [Total SAH of a BVH] Wayback!

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 [SMILEY :)]
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.

(L) [2012/02/22] [tby jbarcz1] [Total SAH of a BVH] Wayback!

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.

(L) [2012/02/23] [tby Dade] [Total SAH of a BVH] Wayback!

>> 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.

(L) [2012/02/23] [tby Dade] [Total SAH of a BVH] Wayback!

>> 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) [SMILEY :!:]

(L) [2012/02/23] [tby jj99] [Total SAH of a BVH] Wayback!

I was looking at this code too. Their value seems completely useless IMHO [SMILEY :)]... But I mupltiplied the SAH(leaf) by the area of the child box. It seems working. If I remove the bvh rotation, it increases.

(L) [2012/03/01] [tby Dade] [Total SAH of a BVH] Wayback!

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).

(L) [2014/07/31] [tby shiqiu1105] [Total SAH of a BVH] Wayback!

>> 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.

(L) [2014/07/31] [tby shiqiu1105] [Total SAH of a BVH] Wayback!

>> 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?