1

私はレイトレーサーを実装しようとしており、本「物理ベースのレンダリング」のkdツリー構築方法を使用しています。

この本では、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 ,...); 
}

明らかに、球は互いに重なり合うことができます。

また、2 つのサブボックスですべてのオブジェクトをカバーできる適切な分割位置がありません。分割位置を横切るオブジェクトは、どのサブボックスにもありません。分割位置の下にあるオブジェクトの数と上の数を足した数が、境界ボックス内のすべてのオブジェクトの数に等しい場合にのみ、位置が記録されるという新しい条件を追加しました。

//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 ) は常に「false」です。もしも

ここでリーフ ノードを作成すると、kd ツリーは無意味になり、ツリー全体にリーフ ノードが 1 つしか含まれないため、単純に順次トラバーサルに退化します。

それで、解決策はありますか？ありがとう！

ここにいくつかの定義があります：

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.私の下手な英語が質問を明確に説明してくれることを願っています...

4

1 に答える 1