KD-树的遍历（光线追踪） - 我缺少的情况下？

Question

我想在我的光线追踪器遍历3D KD树。树是正确的，但似乎是坏了我的遍历算法，因为我得到了一些错误相比，使用蛮力的方法（一些小的表面区域似乎被忽略）。

注意：没有有问题的射线的平行于任何轴

这是我的遍历算法：

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 ）

我缺少的情况？

感谢您的帮助！

Answer 1

万一某人的兴趣 - 错误我所做的就是不考虑在本文中所描述的特殊情况

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
}

您看，我不使用射线的原点选择其中左/右子的近/远了，我走在你的帐户名为C的情况下使用tsplit <0条件