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) &= 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 \\ &= 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?