Прохождение KD-Tree (raytracing) - я пропустил случай?

Я пытаюсь пройти 3D KD-Tree в моем raytracer. Дерево корректно, но, похоже, что-то не так с моим алгоритмом обхода, поскольку я получаю некоторые ошибки по сравнению с использованием метода грубой силы (некоторые небольшие участки поверхности, похоже, игнорируются).

Примечание: ни один из рассматриваемых лучей не параллелен ни одной оси.

Это мой алгоритм обхода:

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

Я создал графику со всеми различными случаями:

_{(источник: cycovery.com)}

Я пропускаю дело?

Спасибо тебе за помощь!

Ответ 1

На всякий случай кого-то заинтересовало - ошибка, которую я сделал, заключалась в том, чтобы не рассматривать специальный случай, описанный в этой статье

http://www.cs.utexas.edu/ftp/pub/techreports/tr88-07.pdf страница 12

Это случается, если один многоугольник лежит на плоскости расщепления, так что часть обеих ячеек и луч проходит через обе ячейки. если ближайшая ячейка проверена, но фактическое пересечение происходит в пространстве фарселла (это возможно, потому что многоугольник, который пересекает, является частью обеих ячеек), то есть еще возможность, что в дальней ячейке может быть найдено пересечение, которое на самом деле ближе, чем уже найденный. Поэтому - если найденное t для пересечения больше tSplit, то уже FarCell должен быть протестирован

Ответ 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
}

Вы видите, что я не использую источник луча для выбора, какой из левого/правого ребенка близок/далеко, и я учитываю случай, который вы назвали C, используя условие tsplit < 0