Classify acceleration structure using surface area heuristic My professor gave me the following example exam question:


  Given 4 spheres with diameter = 1. Their centers are located on
  coordinates (2,4,0), (4,2,0), (4,6,0) and (6,4,0), as seen in the
  picture below. Three different hierarchies of tightest possible
  axis-aligned bounding volumes (AABB) are given:
  
  
  A single AABB around every sphere
  An AABB around the spheres with center (2,4,0) and (4,2,0) and    another around the spheres located at (4,6,0) and (6,4,0).
  An AABB around the spheres with center (2,4,0) and (6,4,0) and    another around the spheres located at (4,2,0) and (4,6,0).
  
  
  For every one of these the all-containing AABB is constructed.




The questions are:


  
  Rank these 3 structures based on efficiency for intersecting a ray    with these spheres (best to worst)
  Does this ranking change if we change the spheres with a (scaled) tea-pot that still fits within the bounding volume?
  Can this ranking depend on the position of the camera, when we only    consider visibility rays (so no shadow rays, for example)? You can assume you're working with an orthographic camera.
  


He insisted on not giving a 'philosophical' answer (like: 'this depends on ...') but rather actually calculating the cost using the surface are heuristic etc.

Only, I have no idea how to start. The cost function we have seen is defined as follows
$$Cost(cell) = C_t + \frac{S_L}{S_{Cell}} \times N_L \times t_i + \frac{S_R}{S_{Cell}} \times N_R \times t_i$$
With:


$C_t$ the cost of traversal (which is an arbitrary constant, I think)
$S_L$/$S_R$ the surface area of the left/right child cell
$S_{cell}$ the surface area of the entire cell
$N_L$/$N_R$ the number of objects in the left/right child cell
$t_i$ the cost of object intersection (which is also an arbitrary
constant)


However, the first hierarchy has 4 child cells, how would I calculate the cost here? Any tips on how to start this exercise would be very helpful.

EDIT: Okay, so for the second and third setup, is it as simple as filling in the formula? For the second setup, this would lead to (assuming I made no numerical errors :) ):
$$\begin{align*}Cost(cell) &amp;= C_t + \frac{2*3^2 + 4*3*1}{2*5^2 + 4*5*1} * 2 * t_i + \frac{2*3^2 + 4*3*1}{2*5^2 + 4*5*1} * 2 * t_i \\ &amp;= C_t + \frac{120}{70} * t_i \end{align*}$$

For the third setup this would, analogously, lead to:
$$Cost(cell) = C_t + \frac{88}{70}*t_i$$.

So now my question would boil down to: can I just do the same for the first setup, but instead evaluate 4 sub-cells? Also, am I correct in assuming $C_t$ and $t_i$ are fixed constants or do they depend on the setup?
You gave the formula as:

$$Cost(cell) = C_t + \frac{S_L}{S_{Cell}} \times N_L \times t_i + \frac{S_R}{S_{Cell}} \times N_R \times t_i$$

(You put $r_i$ at the right-hand end, but I assume that was a typo.) 

There's a more general form of this formula

$$Cost(cell) = C_t + \sum_{k\ \in\ K} \frac{S_k}{S_{Cell}} \times N_k \times t_i$$

where $K$ is the set of all child nodes; that is, to get back to the two-children form you started with, $K = \{L, R\}$.

By generalising the formula like this, you can now calculate the cost for the first possibility the same way as the second two.

You're right that this is a slightly odd question. In practice, your traversal cost is going to be less for a binary tree than a $(&gt; 2)$-ary tree.


  
  Does this ranking change if we change the spheres with a (scaled) tea-pot that still fits within the bounding volume?
  


To answer this, you'll need to consider how this affects the surface area, and how this changes each score in turn.


  
  Can this ranking depend on the position of the camera, when we only    consider visibility rays (so no shadow rays, for example)? You can assume you're working with an orthographic camera.
  


There's two things to consider here.

1) Does any part of the heuristic depend on the position of the camera? Can moving the camera change any of the numbers that feed into the score?

2) Moving the camera can change how the boxes overlap. Remember that rays that pass through the box need to be tested against the box behind, so needless overlaps make the structure worse.

I think the point is that the heuristic is only a general rule. It's not hard to construct an example with two proposals a and b, where a scores much better but b is actually a better split for a particular camera, and this last part of the question is trying to get you to think about this.