KD-Tree transversal (raytracing): ¿me falta un caso?

Question

Estoy tratando de atravesar un árbol 3D KD en mi raytracer. The Tree es correcto, pero parece que hay algo mal con mi algoritmo transversal, ya que estoy obteniendo algunos errores en comparación con el uso de un enfoque de fuerza bruta (algunas áreas pequeñas parecen ser ignoradas).

Nota: ninguno de los rayos en cuestión es paralelo a ningún eje.

Ésta es mi algoritmo de recorrido:

IntersectionData* intersectKDTree(const Ray &ray, KDTreeNode* node, double tMin, double tMax) const{ 

if (node->GetObjectCount()==0) return 0; 

IntersectionData* current = 0; 
bool intersected = false; 

if (node->m_isLeaf){ 
     ...test all primitives in the leaf... 
} 
else{ 
    int axis = node->m_splitAxis; 
    double splitPos = node->m_splitPos; 
    double tSplit = (splitPos-ray.point[axis])/ray.direction[axis]; 
    KDTreeNode* nearNode = ray.point[axis]<splitPos?node->m_leftnode:node->m_rightnode; 
    KDTreeNode* farNode = ray.point[axis]<splitPos?node->m_rightnode:node->m_leftnode; 

    if (tSplit > tMax) 
     return intersectKDTree(ray, nearNode , tMin, tMax);//case A 
    else if (tSplit < tMin){ 
     if(tSplit>0) 
      return intersectKDTree(ray, farNode, tMin, tMax);//case B 
     else if(tSplit<0) 
      return intersectKDTree(ray, nearNode, tMin,tMax);//case C 
     else{//tSplit==0 
      if(ray.direction[axis]<0) 
       return intersectKDTree(ray, farNode, tMin, tMax);//case D 
      else 
       return intersectKDTree(ray, nearNode, tMin, tMax);//case E 
     } 
    } 
    else{ 
     if(tSplit>0){//case F 
      current = intersectKDTree(ray, nearNode, tMin, tSplit); 
      if (current != 0) 
       return current; 
      else 
       return intersectKDTree(ray, farNode, tSplit, tMax); 
     } 
     else{ 
      return intersectKDTree(ray,nearNode,tSplit, tMax);//case G 
     } 
    } 
} 
} 

que creó un gráfico con todos los casos diferentes:

alt text http://neo.cycovery.com/KDTree_traversal.jpg

me estoy perdiendo un caso?

gracias por la ayuda!

Answer 1

por si alguien está interesado - el error que hice fue no considerar un caso especial descrito en este documento

http://www.cs.utexas.edu/ftp/pub/techreports/tr88-07.pdf página 12

Ocurre si un polígono se encuentra en el plano de división, de modo que es parte de ambas celdas y el rayo pasa por ambas celdas. si se prueba la nearcell, pero la intersección real ocurre en el espacio de la farcell (esto es posible porque el polígono que se cruza es parte de ambas celdas), aún existe la posibilidad de que en la celda lejana se encuentre una intersección que está realmente más cerca que el ya encontrado. Por lo tanto, si la t encontrada para la intersección es mayor que tSplit, entonces ya se debe probar farCell

Answer 2

que he tomado un enfoque diferente al problema, aquí es lo que hago:

if(ray.direction(current_node.split_axis)>0) { 
    near=current_node.left_child 
    far=current_node.right_child 
} else { 
    near=current_node.right_child 
    far=current_node.left_child 
} 
tsplit=(current_node.split_value-ray.origin[current_node.split_axis])/ray.direction[current_node.split_axis] 
if(tsplit>current_stack.tmax||tsplit<0) { 
    only near child 
} else if(tsplit<tmin) { 
    only far child 
} else { 
    both childs 
} 

Ves que yo no uso el origen del rayo para elegir qué del hijo izquierdo/derecho es cerca/lejos, y tomo en cuenta el caso de que denomina C mediante el uso de la tsplit < 0 condición