Cycles: BVH traversal and intersection algorithm

Contributing to Blender
1

Trying to understand the BVH traversal/intersect portion of the code for Cycles, and had a couple questions. I am looking at the non-SSE code path in BVH_FUNCTION_FULL_NAME(BVH)() in cycles/kernel/bvh/bvh_traversal.h.

  1. I see that the main traversal loop is of the following form (beginning at line 100 in the commit I am looking at):
do {   //loop-A
  do { //loop-B
        /* traverse internal nodes */
        while (node_addr >= 0 && node_addr != ENTRYPOINT_SENTINEL) {
        ...
        }
        /* if node is leaf, fetch triangle list */
        if (node_addr < 0) {
        ...
        }
      } while (node_addr != ENTRYPOINT_SENTINEL);
    } while (node_addr != ENTRYPOINT_SENTINEL);

Question - Why do we need the outer do loop (marked as loop-A)? I understand that inner do loop is needed to complete traversing all the nodes on the traversal_stack as the nearest hit point may not lie in the nearest bounding volume. But I don’t understand why we need another sweep through the tree?

  1. In the same traversal loop, when checking for intersection with internal nodes, there is no code which checks for:
if (traversal_mask == 1) {}

When looking at bvh_aligned_node_intersect() in cycles/kernel/bvh/bvh_nodes.h, it seems to me that a return value of 1 is a possibility if c0 hits but c1 misses. Not sure what I am missing here.

Any help will be greatly appreciated. If you can point me to any papers which describes the algorithm for this exact portion of the implementation it would be very helpful.

Thanks,

2

  1. It’s to handle the two-level BVH. When it’s done traversing the object level BVH, it continues traversing the scene level BVH. The implementation is not entirely straightforward, but designed to avoid divergence on the GPU.

  2. This code outside the conditionals handles the traversal_mask == 1 case;

node_addr = __float_as_int(cnodes.z);
node_addr_child1 = __float_as_int(cnodes.w);
1 Like