11

raytracer で 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 )

ケースがありませんか？

お手伝いありがとう！

4

2 に答える 2

8

誰かが興味を持った場合に備えて - 私がした間違いは、この論文で説明されている特別なケースを考慮しなかったことです

http://www.cs.utexas.edu/ftp/pub/techreports/tr88-07.pdf 12 ページ

1 つのポリゴンが分割平面上にあり、それが両方のセルの一部であり、光線が両方のセルを通過する場合に発生します。ニアセルがテストされたが、実際の交差がファーセルの空間で発生した場合 (これは、交差するポリゴンが両方のセルの一部であるため可能です)、ファーセルで交差が見つかる可能性がまだあります。実際には、すでに見つかったものよりも近いです。したがって、交差点で見つかった t が tSplit より大きい場合は、すでに farCell をテストする必要があります。

于 2009-12-09T19:52:29.900 に答える
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
}

左/右の子のどちらが近くにあるか遠くにあるかを選択するために光線の原点を使用していないことがわかります.tsplit <0条件を使用してCに名前を付けた場合を考慮しています

于 2009-12-09T18:14:25.973 に答える