libs/yocto/yocto_scene.cpp
// Intersect ray with a bvh->
Intersect ray with a bvh->
Intersect ray with a bvh - >
static bool intersect_shape_bvh(scene_shape* shape, const ray3f& ray_,
    int& element, vec2f& uv, float& distance, bool find_any) {
#ifdef YOCTO_EMBREE
  if (shape->embree_bvh) {
    return intersect_shape_embree_bvh(
        shape, ray_, element, uv, distance, find_any);
  }
#endif
  auto bvh = shape->bvh;
  if (bvh->nodes.empty()) return false;
  int  node_stack[128];
  auto node_cur          = 0;
  node_stack[node_cur++] = 0;
  auto hit = false;
  auto ray = ray_;
  auto ray_dinv  = vec3f{1 / ray.d.x, 1 / ray.d.y, 1 / ray.d.z};
  auto ray_dsign = vec3i{(ray_dinv.x < 0) ? 1 : 0, (ray_dinv.y < 0) ? 1 : 0,
      (ray_dinv.z < 0) ? 1 : 0};
  while (node_cur) {
    auto& node = bvh->nodes[node_stack[--node_cur]];
    if (!intersect_bbox(ray, ray_dinv, node.bbox)) continue;
    if (node.internal) {
      if (ray_dsign[node.axis]) {
        node_stack[node_cur++] = node.start + 0;
        node_stack[node_cur++] = node.start + 1;
      } else {
        node_stack[node_cur++] = node.start + 1;
        node_stack[node_cur++] = node.start + 0;
      }
    } else if (!shape->points.empty()) {
      for (auto idx = node.start; idx < node.start + node.num; idx++) {
        auto& p = shape->points[shape->bvh->primitives[idx]];
        if (intersect_point(
                ray, shape->positions[p], shape->radius[p], uv, distance)) {
          hit      = true;
          element  = shape->bvh->primitives[idx];
          ray.tmax = distance;
        }
      }
    } else if (!shape->lines.empty()) {
      for (auto idx = node.start; idx < node.start + node.num; idx++) {
        auto& l = shape->lines[shape->bvh->primitives[idx]];
        if (intersect_line(ray, shape->positions[l.x], shape->positions[l.y],
                shape->radius[l.x], shape->radius[l.y], uv, distance)) {
          hit      = true;
          element  = shape->bvh->primitives[idx];
          ray.tmax = distance;
        }
      }
    } else if (!shape->triangles.empty()) {
      for (auto idx = node.start; idx < node.start + node.num; idx++) {
        auto& t = shape->triangles[shape->bvh->primitives[idx]];
        if (intersect_triangle(ray, shape->positions[t.x],
                shape->positions[t.y], shape->positions[t.z], uv, distance)) {
          hit      = true;
          element  = shape->bvh->primitives[idx];
          ray.tmax = distance;
        }
      }
    } else if (!shape->quads.empty()) {
      for (auto idx = node.start; idx < node.start + node.num; idx++) {
        auto& q = shape->quads[shape->bvh->primitives[idx]];
        if (intersect_quad(ray, shape->positions[q.x], shape->positions[q.y],
                shape->positions[q.z], shape->positions[q.w], uv, distance)) {
          hit      = true;
          element  = shape->bvh->primitives[idx];
          ray.tmax = distance;
        }
      }
    }
    if (find_any && hit) return hit;
  }
  return hit;
}
static bool intersect_shape_bvh ( scene_shape * shape , const ray3f & ray_ , int & element , vec2f & uv , float & distance , bool find_any ) { #ifdef YOCTO_EMBREE if ( shape -> embree_bvh ) { return intersect_shape_embree_bvh ( shape , ray_ , element , uv , distance , find_any ) ; } #endif auto bvh = shape -> bvh ; if ( bvh -> nodes . empty ( ) ) return false ; int node_stack [ 128 ] ; auto node_cur = 0 ; node_stack [ node_cur ++ ] = 0 ; auto hit = false ; auto ray = ray_ ; auto ray_dinv = vec3f { 1 / ray . d . x , 1 / ray . d . y , 1 / ray . d . z } ; auto ray_dsign = vec3i { ( ray_dinv . x < 0 ) ? 1 : 0 , ( ray_dinv . y < 0 ) ? 1 : 0 , ( ray_dinv . z < 0 ) ? 1 : 0 } ; while ( node_cur ) { auto & node = bvh -> nodes [ node_stack [ -- node_cur ] ] ; if ( ! intersect_bbox ( ray , ray_dinv , node . bbox ) ) continue ; if ( node . internal ) { if ( ray_dsign [ node . axis ] ) { node_stack [ node_cur ++ ] = node . start + 0 ; node_stack [ node_cur ++ ] = node . start + 1 ; } else { node_stack [ node_cur ++ ] = node . start + 1 ; node_stack [ node_cur ++ ] = node . start + 0 ; } } else if ( ! shape -> points . empty ( ) ) { for ( auto idx = node . start ; idx < node . start + node . num ; idx ++ ) { auto & p = shape -> points [ shape -> bvh -> primitives [ idx ] ] ; if ( intersect_point ( ray , shape -> positions [ p ] , shape -> radius [ p ] , uv , distance ) ) { hit = true ; element = shape -> bvh -> primitives [ idx ] ; ray . tmax = distance ; } } } else if ( ! shape -> lines . empty ( ) ) { for ( auto idx = node . start ; idx < node . start + node . num ; idx ++ ) { auto & l = shape -> lines [ shape -> bvh -> primitives [ idx ] ] ; if ( intersect_line ( ray , shape -> positions [ l . x ] , shape -> positions [ l . y ] , shape -> radius [ l . x ] , shape -> radius [ l . y ] , uv , distance ) ) { hit = true ; element = shape -> bvh -> primitives [ idx ] ; ray . tmax = distance ; } } } else if ( ! shape -> triangles . empty ( ) ) { for ( auto idx = node . start ; idx < node . start + node . num ; idx ++ ) { auto & t = shape -> triangles [ shape -> bvh -> primitives [ idx ] ] ; if ( intersect_triangle ( ray , shape -> positions [ t . x ] , shape -> positions [ t . y ] , shape -> positions [ t . z ] , uv , distance ) ) { hit = true ; element = shape -> bvh -> primitives [ idx ] ; ray . tmax = distance ; } } } else if ( ! shape -> quads . empty ( ) ) { for ( auto idx = node . start ; idx < node . start + node . num ; idx ++ ) { auto & q = shape -> quads [ shape -> bvh -> primitives [ idx ] ] ; if ( intersect_quad ( ray , shape -> positions [ q . x ] , shape -> positions [ q . y ] , shape -> positions [ q . z ] , shape -> positions [ q . w ] , uv , distance ) ) { hit = true ; element = shape -> bvh -> primitives [ idx ] ; ray . tmax = distance ; } } } if ( find_any && hit ) return hit ; } return hit ; }
Intersect ray with a bvh->
Intersect ray with a bvh - >
// call Embree if needed // get bvh and shape pointers for fast access // check empty // node stack // shared variables // copy ray to modify it // prepare ray for fast queries // walking stack // grab node // intersect bbox // if (!intersect_bbox(ray, ray_dinv, ray_dsign, node.bbox)) continue; // intersect node, switching based on node type // for each type, iterate over the the primitive list // for internal nodes, attempts to proceed along the // split axis from smallest to largest nodes // check for early exit