KD-Tree traversal (raytracing) - Tôi có thiếu một trường hợp không?

Question

Tôi đang cố gắng duyệt qua một cây KD 3D trong bộ lọc tia. Cây là chính xác, nhưng có vẻ là một cái gì đó sai với thuật toán traversal của tôi kể từ khi tôi nhận được một số lỗi so với cách sử dụng một cách tiếp cận brute-force (một số diện tích bề mặt nhỏ dường như bị bỏ qua).

Lưu ý: không có tia nào trong câu hỏi song song với bất kỳ trục nào.

Đây là thuật toán traversal của tôi:

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

Tôi tạo ra một hình ảnh với tất cả các trường hợp khác nhau:

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

Tôi có thiếu một trường hợp?

cảm ơn sự giúp đỡ của bạn!

Answer 1

Chỉ trong trường hợp ai đó quan tâm - những sai lầm tôi đã làm là không xem xét một trường hợp đặc biệt được mô tả trong bài báo này

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

Điều này xảy ra nếu một đa giác nằm trên mặt phẳng phân tách, sao cho nó là một phần của cả hai ô và tia đi qua cả hai ô. nếu gần được kiểm tra, nhưng giao điểm thực tế xảy ra trong không gian của farcell (điều này là có thể bởi vì đa giác giao nhau là một phần của cả hai ô) thì vẫn có khả năng, trong ô xa có thể tìm thấy giao lộ thực sự gần hơn so với cái đã tìm thấy. Do đó - nếu t được tìm thấy cho giao lộ lớn hơn tSplit, thì đã phải kiểm tra farCell

Answer 2

Tôi đã thực hiện một cách tiếp cận khác nhau cho vấn đề, đây là những gì tôi làm:

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 
} 

Bạn thấy rằng tôi không sử dụng nguồn gốc của các tia cho lựa chọn đó của đứa trẻ trái/phải là gần/xa, và tôi mất trong tài khoản trường hợp bạn đặt tên C bằng tsplit < 0 điều kiện