Lecture 16 Quiz

Question 1:

Here's another way to think about a SIMD-efficient ray tracer:

Imagine I gave you a function int partition(vector<Ray>, BVHnode, int active). The function takes a vector of rays, and sorts the first active elements of the vector so that all rays in this segment of the vector that hit the specified node are placed at the front of the vector, and all nodes that miss the vector are placed at the end of the segment. It returns an integer that gives how many rays hit the node. For example, if you assume that r1 and r2 hit myNode, but r0 and r3 do not, then a call to:

int num = partition( {r0,r1,r2,r3,r4,r5,r6} , myNode, 4);   

Yields num = 2, and the sorted list is: {r1, r2, r0, r3, r4, r5, r6}

Given this function, implement a simple ray tracer by completing the function trace below. you should assume that to render a picture, trace is called on the root node of the scene's BVH, and with a vector containing all the camera rays in the scene.

void trace(vector<Ray> rays, BVHNode node, int active) {

     if (node.leaf) {

          // assume leaf case is handled here. For those that are wondering
          // where the intersection results go, just assume intersection info
          // is stuck in the ray struct (e.g., ray.is_hit and ray.hit_t).  You can
          // also assume that an intersection updates ray.max_t (which is used by
          // subsequent ray-primitive and ray-bbox intersection routines)

     } else {

          // TODO: implement this code here using partition()

     }
}

Solution:

Calling partition on the current node moves all nodes that hit the current node's box to the front of the vector of rays.

void trace(vector<Ray> rays, BVHNode node, int active) {

     if (node.leaf) {

       // leaf code not considered in this problem, but
       // here's some pseudocode anyway (note, we'd be better off
       // with a bounding box check to first see if the rays hit
       // the node's bbox.
       for each r in active portion of rays:
          for each p in node->primitives:
             intersect(r, p);

     } else {

       int num = partition(rays, node, active);
       if (num > 0) {
          trace(rays, node->left, num);
          trace(rays, node->right, num);
       }
     }
}

Another valid answer was:

void trace(vector<Ray> rays, BVHNode node, int active) {

     if (node.leaf) {

       // leaf code not considered in this problem, but
       // here's some pseudocode anyway
          for each r in active part of rays:
             for each p in node->primitives:
                 intersect(r, p);

     } else {

          int num = partition(rays, node->left, active);
          trace(rays, node->left, num);
          num = partition(rays, node->right, active);
          trace(rays, node->right, num);

     }
}

Question 2:

How is the implementation above related to the packet tracing implementation discussed in class? How is it related to the ray reordering optimization discussed in class? (A couple of sentences is fine.)

Solution:

Notice that in the solution above, a large group of rays visit a BVH node at the same time. So you can think of the implementation above as grouping all camera rays in the scene into a single, large packet. At each step in traversal, the code resorts the rays to dynamically form as big a packet as possible to trace against the child node. If you assume that the only rays needed to make the picture are camera rays, then rendering the scene requires visiting each BVH node exactly once.

This is a good example of how there's a very blurry line between a rasterizer and a ray tracer. For example, imagine changing the implementation in the leaf node to project all primitives (and rays) in the leaf node to an image plane, and then just computing hits in 2D on this plane via rasterization!