KD -Tree Traversal (Raytracing) - 케이스가 없습니까?

StackOverflow https://stackoverflow.com/questions/1852391

  •  13-09-2019
  •  | 
  •  

문제

레이 트레이서에서 3D KD-Tree를 통과하려고합니다. 트리는 맞지만, 무차별적인 접근법을 사용하는 것과 비교하여 약간의 오류가 발생하기 때문에 내 트래버스 알고리즘에 문제가있는 것 같습니다 (일부 작은 표면 영역은 무시되는 것 같습니다).

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

이것은 내 트래버스 알고리즘입니다.

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

모든 다른 경우가있는 그래픽을 만들었습니다.

alt text
(원천: cycovery.com)

내가 사건이 없어?

도움을 주셔서 감사합니다!

도움이 되었습니까?

해결책

누군가가 관심있는 경우를 대비하여 - 내가 한 실수는이 백서에 설명 된 특별한 사례를 고려하지 않는 것이 었습니다.

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

하나의 다각형이 분할 평면에 놓여있는 경우, 세포의 일부이며 광선은 두 세포를 모두 통과합니다. 니어 셀이 테스트되었지만 실제 교차로가 패셀의 공간에서 발생한다면 (교차하는 다각형이 두 세포의 일부이기 때문에 가능합니다), 여전히 가능성이 있으며, 먼 셀에서 교차로가 발견 될 수 있습니다. 실제로 이미 발견 된 것보다 가깝습니다. 따라서 - 교차로의 발견 된 t가 tsplit보다 크면 이미 Farcell을 테스트해야합니다.

다른 팁

문제에 대해 다른 접근 방식을 취했습니다. 여기에 내가하는 일이 있습니다.

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 조건을 사용하여 C라는 케이스를 고려합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top