KD-Baum-Traversal (Raytracing) - bin ich dabei einen Fall?

Question

Ich versuche, einen 3D-KD-Baum in meinem Raytracer zu durchqueren. Der Baum ist richtig, aber es scheint etwas falsch mit meinem Traversierungsalgorithmus zu sein, da ich einige Fehler bin immer im Vergleich zu einem Brute-Force-Ansatz (einige kleine Flächen zu erhalten ignoriert scheinen).

. Hinweis: keine der Strahlen in Frage ist parallel zu einer Achse

Das ist mein Traversierungsalgorithmus:

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

Ich habe eine Grafik mit allen verschiedenen Fällen:

_{(Quelle: cycovery.com )}

Bin ich einen Fall fehlen?

Danke für die Hilfe!

Answer 1

Für den Fall, jemand interessiert - der Fehler, den ich tat, war nicht einen Sonderfall in diesem Papier beschrieben betrachten

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

Es passiert, wenn ein Polygon auf der Teilungsebene liegt, so dass es Teil der beiden Zellen und der Strahl geht durch beide Zellen ist. wenn die nearcell getestet wird, aber die eigentliche Kreuzung passiert in dem Raum des farcell (dies ist möglich, weil das Polygon, das Teil der beiden Zellen schneidet), dann gibt es noch die Möglichkeit, dass in der weit eine Kreuzung Zelle gefunden werden könnte, die ist eigentlich näher als der ihn schon gefunden. Deshalb - wenn die gefunden t für die Kreuzung größer als tSplit ist, dann bereits die farCell getestet werden muss

Answer 2

ich eine andere Herangehensweise an das Problem genommen haben, hier ist was ich tun:

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
}

Sie sehen, dass ich den Ursprung des Strahls für Wahl nicht, welche der linken / rechten Kind in der Nähe ist / weit, und ich nehme den Fall Konto C benannt durch den tsplit mit <0 Bedingung