1

我正在尝试实现一个光线跟踪器，并且我正在使用“基于物理的渲染”一书中的 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.我希望我糟糕的英语清楚地解释了这个问题......

4

1 回答 1

3

KD-tree 需要在两个子树中存储所有穿过分裂平面的对象。您认为对象仅存储在其中一个子树中的假设是不正确的。正确的说法是：

（nBelow + nShared + nAbove == nObjects）

这就是为什么 BVH 通常优于 KD-Tree 的原因之一（即 BVH 将对象仅存储在其中一个子树中，因为子树边界框可以重叠）。

具有许多交叉对象的分割平面将具有更高的 SAH 成本（因为交叉对象被计算 2 次），因此 KD-tree 分割代码仍将尝试最小化共享对象的数量（但通常会有一些重复）。

于 2013-05-28T07:30:00.280 回答