KD樹遍歷（光線跟蹤） - 我錯過了一個案例？

我想在我的raytracer中遍歷一個3D KD-Tree。樹是正確的，但似乎我的遍歷算法出了問題，因爲與使用暴力破解方法相比，我遇到了一些錯誤（一些小的表面區域似乎被忽略）。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 
     } 
    } 
} 
}

我創建了各種不同情況下的圖形：

alt text http://neo.cycovery.com/KDTree_traversal.jpg

我缺少的情況下？

感謝您的幫助！

來源

2009-12-05 Mat

萬一某人的興趣 - 的錯誤，我所做的就是不考慮在本文中所描述的特殊情況

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

如果一個多邊形位於分割平面上，使其成爲兩個單元的一部分並且光線穿過兩個單元，就會發生這種情況。如果測試了nearcell，但實際的交叉發生在farcell的空間中（這是可能的，因爲相交的多邊形是兩個小區的一部分），那麼仍然存在這樣的可能性，即在遠程小區中可以找到哪個交點實際上比已經找到的更接近。因此 - 如果發現交點的t大於tSplit，則farCell已被測試

來源

2009-12-09 19:52:29 Mat

關於作者或論文名稱的想法？該鏈接似乎已停止工作。 – Arend 2014-08-20 20:21:35

ftp://ftp.cs.utexas.edu/.snapshot/backup/pub/techreports/tr88-07.pdf – gamers2000 2014-12-09 09:38:42

由於第二個鏈接也死了，我再次追查這篇文章。 [快速射線追蹤使用KD樹（ftp://ftp.cs.utexas.edu/pub/techreports/tr88-07.pdf）唐納德·福塞爾，計算機科學KR薩勃拉曼尼亞部德克薩斯大學奧斯汀分校1988年3月， – winnetou 2016-04-26 06:49:44

我已經採取了不同的方法解決問題，這是我做的：

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條件

來源

2009-12-09 18:14:25

嗨！但是例如在C的情況下你會穿過錯誤的孩子，因爲'near'會留下孩子，但是你應該穿過右邊的孩子。 – Mat 2009-12-09 19:48:49

@Mat，因爲它應該是'ray.direction（current_node.split_axis）> = 0'？或者你爲什麼這麼說？ – luckydonald 2017-01-13 00:10:47

KD樹遍歷（光線跟蹤） - 我錯過了一個案例？

回答

相關問題