Обход дерева KD (raytracing) - я пропустил дело? - PullRequest
Новая
       44

Обход дерева KD (raytracing) - я пропустил дело?

11 голосов
/ 05 декабря 2009

Я пытаюсь пройти 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
        }
    }
}
}

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

alt text
(источник: cycovery.com )

Я пропустил дело?

спасибо за помощь!

Ответы [ 2 ]

8 голосов
/ 09 декабря 2009

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

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

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

0 голосов
/ 09 декабря 2009

Я использовал другой подход к проблеме, вот что я делаю: 

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 </p>

...