3
$\begingroup$

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.

Assignment

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?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ This is a great example of a homework question where you've "done your homework": you've shown how far you got and what you have, and where you're stuck. Good work! $\endgroup$
    – Dan Hulme
    Jan 29, 2018 at 11:14
  • 1
    $\begingroup$ Thank you, now if only someone could help me figure it out,haha :D $\endgroup$
    – Robin Haveneers
    Jan 29, 2018 at 11:22

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ Oh, you were probably typing out your answer when I replied above! Thank you very much for the detailed answer, Dan! Everything is much clearer now. $\endgroup$
    – Robin Haveneers
    Jan 29, 2018 at 12:22
  • $\begingroup$ One question though, about the tea-pot. If the bounding box does not change, am I correct to assume that the enclosed object does not matter? The tea pot fits within the bounding box but the bounding box remains the same (cfr. the question), so it does not affect the surface area, which is still calculated using the 6 surfaces of the cubic bounding box. $\endgroup$
    – Robin Haveneers
    Jan 29, 2018 at 12:27
  • $\begingroup$ Oh of course, this version of the SAH just uses the box volume. Ignore that bit then! I was thinking of a different version that actually uses the triangle areas in the leaf nodes. In that case, ask yourself the same question as for the last part: will changing the objects change any number in the heuristic? Will they change the actual hit-ratio of the box? What does this tell you about how the heuristic relates to the measured performance? $\endgroup$
    – Dan Hulme
    Jan 29, 2018 at 13:07
  • $\begingroup$ I would say that changing the objects or the camera position doesn't change the heuristic, seen as though the surface area is based on Crofton's theorem (independent of the camera). So I'd assume that (in line with what you said) the position of the camera does not influence the score. But, it's only a heuristic so the position of the camera WILL influence the hit ratio. E.g: the 1st setup when we view a camera from above (y axis): if a ray hits the bounding box there, we have a much higher probability of actually hitting an object which is not the case if we have a camera along the z-axis. $\endgroup$
    – Robin Haveneers
    Jan 29, 2018 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.