拆分從「基於物理渲染」

我想實現光線跟蹤，我用從書‘的基礎基於物理渲染’KD樹構造方法在KD-tree構造邊界框。拆分從「基於物理渲染」

書使用一種稱爲SAH的方法來選擇分割邊界框的位置它從場景中對象的邊界框的邊緣選擇分割位置。邊沿沿軸線從低到高排序。

它和它找到像這樣的最佳分割：

//<Compute cost of all splits for axis to find best> 
int nBelow = 0, nAbove = nObjects; 
for(int i = 0; i < 2 * nObjects ; ++i){ 
    if(edges[axis][i].type == END) -- nAbove; 
    float edget = edges[axis][i].t; 
    if(edget > nodeBounds.pMin[axis] && 
     edget < nodeBounds.pMax[axis]){ 
      //<Compute cost for split at ith edges> 
    } 
    if(edges[axis][i].type == START) ++ nBelow; 
}

我把球體100在場景隨機這樣的：

for(int i = 1 ; i < 100 ; ++ i){ 
    float x,y,z,r; 
    x = 800 * float(rand())/float(RAND_MAX) - 200 ; 
    y = 800 * float(rand())/float(RAND_MAX) - 200 ; 
    z = 400 * float(rand())/float(RAND_MAX) - 100 ; 
    r = 50 * float(rand())/float(RAND_MAX) + 25; 
    initSphere(..., Point3D(x,y,z) , r ,...); 
}

明顯，球體可以相互重疊。

並沒有好的分割位置，可以讓兩個子盒子覆蓋所有的對象。跨越分割位置的對象將不在任何子框中。我增加了一個新的條件，只有當分割位置下方的對象數加上面的數字等於邊界框中所有對象的數量時，纔會記錄位置。

//update best split if this is lowest cost so far 
    if(cost < bestCost && (nBelow + nAbove == nObjects)){ 
     bestCost = cost; 
     bestAxis = axis; 
     bestOffset = i; 
    }

（nBelow + nAbove == nObjects）總是「假」。如果

如果我們在這裏創建一個葉節點，那麼kd-tree是無意義的，它簡單地退化爲順序遍歷，因爲整棵樹將只包含一個葉節點。

那麼，有沒有解決方案？謝謝！

這裏是一些定義：

struct Point3D{ 
    float x,y,z; 
} 
struct BBox{ 
    float pMax[3],pMin[3]; 
} 
struct BoundEdge{ 
    float t; 
    int type; // START or END 
} 
BoundEdge *edges[3];

ps.i希望我的英語不好解釋清楚的問題...

來源

2013-05-27 Clones1201

KD樹需要存儲渡分光面上的兩個子中的所有對象 - 樹。你假設一個對象只存儲在一個子樹中是不正確的。正確的說法是：

（nBelow + nShared + nAbove == nObjects）

這就是爲什麼BVH往往優於KD樹的原因之一（即BVH存儲在只有子的一個對象因爲子樹邊界框可以重疊）。

具有許多交叉對象的分割平面將具有更高的SAH成本（因爲交叉對象被計數2次），所以KD樹分割代碼仍然會盡量減少共享對象的數量（但通常會有一些重複）。

來源

2013-05-28 07:30:00 Dade916

拆分從「基於物理渲染」

回答

相關問題