Total SAH of a BVH
Total SAH of a BVH
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) ?
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) ?

 Posts: 7
 Joined: Wed Jan 25, 2012 10:20 am
Re: Total SAH of a BVH
There is an example of doing that in the Embree source code

 Posts: 167
 Joined: Mon Nov 28, 2011 7:28 pm
Re: Total SAH of a BVH
It seems to me that you'd want moreorless 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 kdtree, 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.
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 kdtree, 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
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 bottomup merging of leaves until cost doesn't improve.
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 bottomup merging of leaves until cost doesn't improve.
Re: Total SAH of a BVH
Oh, thanks, I didn't know, going to check the sources.darkhorse64 wrote:There is an example of doing that in the Embree source code
Re: Total SAH of a BVH
Embree uses "Total SAH" that matches graphicsMan's definition however they seems to use an "unnormalized" value:Dade wrote:Oh, thanks, I didn't know, going to check the sources.darkhorse64 wrote:There is an example of doing that in the Embree source code
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
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
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).
// 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).

 Posts: 138
 Joined: Sun May 27, 2012 4:42 pm
Re: Total SAH of a BVH
I found this very interesting.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).
How do we use this formula if we build the BVH topdown though. We rely on SAH to split the node, yet the formula requires the node splitted to evaluate.

 Posts: 138
 Joined: Sun May 27, 2012 4:42 pm
Re: Total SAH of a BVH
So the SAH calculation of embree is wrong?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.