KD-Tree traversal (raytracing) - Ai-je manqué un étui?

Question

J'essaie de traverser un 3D KD-Tree dans mon raytracer. L'arbre est correct, mais il semble y avoir quelque chose qui ne va pas dans mon algorithme de traversée, car j'ai des erreurs par rapport à l'approche par force brute (certaines petites surfaces semblent être ignorées).

Note: aucun des rayons en question est parallèle à un axe quelconque.

Ceci est mon algorithme traversal:

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 
     } 
    } 
} 
} 

J'ai créé un graphique avec tous les différents cas:

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

Suis-je manque un cas?

merci de votre aide!

Answer 1

Juste au cas où quelqu'un est intéressé - l'erreur je l'ai fait était de ne pas considérer un cas particulier décrit dans cet article

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

Ce qui se passe si un polygone se trouve sur le plan de division, de telle sorte qu'elle fait partie des deux cellules et le rayon passe par les deux cellules. si la quasi-cellule est testée, mais que l'intersection réelle se produit dans l'espace de la cellule éloignée (ceci est possible parce que le polygone qui croise fait partie des deux cellules), il y a toujours la possibilité de trouver dans la cellule lointaine est en réalité plus proche que celui déjà trouvé. Par conséquent - si le t trouvé pour l'intersection est plus grand que tSplit, puis déjà le farCell doit tester

Answer 2

J'ai pris une approche différente du problème, voici ce que je fais:

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 
} 

Vous voyez que je n'utilise pas l'origine du rayon pour choisir lequel l'enfant gauche/droite est proche/lointain, et je prends en compte le cas que vous avez nommé C en utilisant le tsplit < 0 état