KD 트리 탐색 (광선 추적) - 사례가 누락 되었습니까?

Question

raytracer에서 3D KD 트리를 탐색하려고합니다. 트리는 정확하지만 무차별 접근법 (일부 작은 표면 영역은 무시되는 것처럼 보임)을 사용하는 것에 비해 약간의 오류가 발생하므로 내 트래버 설 알고리즘에 문제가있는 것으로 보입니다.

참고 : 문제의 광선은 어느 축과도 평행하지 않습니다.

이 내 탐색 알고리즘 :

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

가 나는 경우 실종 :

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

내가 모든 다른 경우와 그래픽을 만들어?

도움에 감사드립니다.

Answer 1

를 사용하여 계정에 당신이 C라는 이름의 사건을 맡아 - 내가했던 실수는이 문서에 설명 된 특별한 경우를 고려하지했다

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

하나의 다각형이 분할 평면에 있으면 두 셀의 일부이고 광선이 두 셀을 모두 통과하는 것처럼됩니다. nearcell이 테스트되었지만 실제 교차가 farcell의 공간에서 발생하면 (교차하는 다각형이 두 셀의 일부이기 때문에 가능합니다) 먼 셀에 교차가 발견 될 가능성이 여전히 있습니다. 실제로 이미 발견 된 것보다 더 가깝습니다. 따라서 교차점에 대해 발견 된 t가 tSplit보다 큰 경우 이미 farCell을 테스트해야합니다.

Answer 2

내가 문제에 대한 다른 접근 방식을 촬영했습니다, 여기에 내가 할 수있는 작업은 다음과 같습니다

당신은 내가이 왼쪽/오른쪽 아이의 어떤 선택을위한 광선의 원점을 사용하지 않는 것을 볼

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 
} 

가까이/멀리, 나는 누군가가 관심 다만 경우에 tsplit < 0 상태