KD-Tree遍历（光线跟踪）-我是否遗漏了某些情况？

Question

KD-Tree遍历（光线跟踪）-我是否遗漏了某些情况？

11

我正在尝试在我的光线追踪器中遍历一个3D KD-Tree。树是正确的，但由于我的遍历算法存在问题，与使用暴力方法相比（一些小表面区域似乎被忽略了），我得到了一些错误。

注意：所涉及的光线都不与任何轴平行。

这是我的遍历算法：

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

请问我是否遗漏了某种情况？

感谢您的帮助！

- Mat

2个回答

0

我对这个问题采取了不同的方法，以下是我的做法：

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的条件

- user228165

嗨！例如在C语言中，你可能会遍历错误的子节点，因为“near”将成为左子节点，但是你应该遍历右子节点。 - Mat

@Mat 因为它应该是 ray.direction(current_node.split_axis)>=0 吗？或者你的意思是什么？ - luckydonald

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mat · Accepted Answer

如果有人感兴趣的话 - 我犯的错误是没有考虑到这篇论文中描述的特殊情况。

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

如果一个多边形位于分裂平面上，使得它既是一个单元格的一部分，又是另一个单元格的一部分，并且射线穿过了两个单元格，则会发生这种情况。如果测试的是近单元格，但实际交点出现在远单元格的空间中（这是可能的，因为相交的多边形是两个单元格的一部分），那么仍然存在这样的可能性，即在远单元格中可以找到一个比已经找到的更接近的交点。因此 - 如果找到的交点的t值大于tSplit，则必须测试远单元格。