KD-Tree遍历(光线追踪) - 我错过了一个案例吗？

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

我创建了一个包含所有不同情况的图形:

替代文字http://neo.cycovery.com/KDTree_traversal.jpg

我错过了一个案子吗？

感谢您的帮助!

Answer 1

以防万一有人感兴趣 - 我做的错误是不考虑本文所述的特殊情况

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

如果一个多边形位于分裂平面上,则会发生这种情况,因此它是两个单元的一部分,并且光线穿过两个单元.如果测试近区,但是实际的交叉点发生在远场的空间中(这是可能的,因为相交的多边形是两个单元的一部分),那么仍然有可能在远端单元中找到一个交叉点实际上比已经找到的更接近.因此 - 如果找到的交叉点的t大于tSplit,则必须测试farCell