Total SAH of a BVH

Practical and theoretical implementation discussion.
Dade
Posts: 206
Joined: Fri Dec 02, 2011 8:00 am

Total SAH of a BVH

Postby Dade » Wed Feb 22, 2012 10:46 am

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

darkhorse64
Posts: 7
Joined: Wed Jan 25, 2012 10:20 am

Re: Total SAH of a BVH

Postby darkhorse64 » Wed Feb 22, 2012 12:24 pm

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

graphicsMan
Posts: 160
Joined: Mon Nov 28, 2011 7:28 pm

Re: Total SAH of a BVH

Postby graphicsMan » Wed Feb 22, 2012 3:01 pm

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.

jbarcz1
Posts: 6
Joined: Sun Dec 11, 2011 11:47 pm

Re: Total SAH of a BVH

Postby jbarcz1 » Wed Feb 22, 2012 3:31 pm

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.

Dade
Posts: 206
Joined: Fri Dec 02, 2011 8:00 am

Re: Total SAH of a BVH

Postby Dade » Thu Feb 23, 2012 11:43 am

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.

Dade
Posts: 206
Joined: Fri Dec 02, 2011 8:00 am

Re: Total SAH of a BVH

Postby Dade » Thu Feb 23, 2012 2:11 pm

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) :!:

jj99
Posts: 1
Joined: Thu Feb 23, 2012 3:52 pm

Re: Total SAH of a BVH

Postby jj99 » Thu Feb 23, 2012 3:59 pm

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.

Dade
Posts: 206
Joined: Fri Dec 02, 2011 8:00 am

Re: Total SAH of a BVH

Postby Dade » Thu Mar 01, 2012 10:42 am

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

shiqiu1105
Posts: 138
Joined: Sun May 27, 2012 4:42 pm

Re: Total SAH of a BVH

Postby shiqiu1105 » Thu Jul 31, 2014 4:47 am

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.

shiqiu1105
Posts: 138
Joined: Sun May 27, 2012 4:42 pm

Re: Total SAH of a BVH

Postby shiqiu1105 » Thu Jul 31, 2014 6:08 am

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?


Return to “General Development”

Who is online

Users browsing this forum: No registered users and 3 guests