Lecture 10 Quiz

Question 1

Imagine you need to build an bounding volume hierarchy for efficiently answering ray-scene queries for a set of triangles. What if I promised you that all queries would be for rays traveling in the positive x direction (r.d = [1 0 0]^T). How might you modify the surface area heuristic to utilize this extra information about the workload?

Solution:

The surface area heuristic is based on the assumption that rays are randomly distributed throughout the scene (have random direction and origin). Under this assumption the probability that a ray hits a box is proportional to the surface area of the box. However, in this case, rays are not randomly oriented, they are all pointed in the +X direction. This means that the rays will only intersect bounding boxes on their Y-Z planes. So a box that has a huge exent in the X direction but a very small profile in its Y-Z face might not be hit often. Therefore, the surface area heuristic could be modified to use the surface area of the Y-Z faces of the bbox (rather than the entire surface area) as the probability of a ray hitting the box.

Question 2

Consider the scene below (in 2D) with 11 total primitives: 10 triangles (unit base, unit height) and one quadrilateral primitive (width=10, height=0.95) that spans almost the entire bounding box (dotted red line) of the scene.

Image

Assume partitioning planes partition the X axis (no Y splits), where would a 2D version of the surface area heuristic partition this scene? (what cut minimizes the predicted cost?)

One of the constraints on the BVH build algorithms we discussed in class (which is imposed to make splitting tractable) is to only partition primitives by their position relative to a chosen axis-aligned splitting plane. Now ignore the algorithms discussed in class and imagine that you want to build a BVH for the above scene that is efficient for answering ANY HIT queries for random 2D sample points positioned within the scene's bounds. (By "any hit", we mean: does ANY piece of geometry cover the sample point?) How might you origanize the primitives in a BVH for this situation? (A quick sketch of the BVH + a sentence or two on why you chose the organization you did is sufficient).

Solution:

The SAH is minimized by dividing the domain in the middle, placing 5 triangles and the rectange in one child node, and five triangles in the other. You can plot the surface area heuristic by plotting: C(x) = (x * x / 10) + (10-x) (where X is the position on the X axis of the splitting plane).

In the proposed "any hit" scenario, the goal is to find other whether the ray hints ANY GEOMETRY as quickly as possible. Sicne most rays do hit the rectangle, it would be advantageous to test a ray against the rectangle first. For example, you could imagine a BVH with a root node with one child containing only the rectangle, and a second child containing a subtree with all the triangles.

Question 3 (Optional, just for kicks, and tricky)

Kayvon claims that there is no need to check for divide by zero in the ray-axis-aligned plane intersection logic used in the ray-bbox intersection test (see slide 6). Why? (Hint: recall the definition of IEEE floating point math from 15-213.)