CODEWITHSUNDEEP
algorithmgraphicsraytracing
Clones1201
Clones1201

Reputation: 343

Split of Bounding box in KD-Tree construction from “Physically Based Rendering"

i am trying to implement a raytracer and i am using the kd-tree construction method from the book "Physicall Based Rendering".

the book uses a method called SAH to choose the position to split the bounding box. it choose split position from the edges of bounding boxs of objects in the scene.the edges are sort from low to high along the axis.

and it find the best split like this:

//<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;
}

i put 100 spheres in the scene randomly like this:

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 ,...); 
}

obviously, spheres can overlap each other.

and there is no good split position which could let two sub-boxs to cover all the objects. the object which crosses the split position will not be in any sub-box. i added a new condition that only when the number of objects below the split position plus the number above equal the number of all the objects in the bounding box then the position will be recorded.

//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 ) is always "false". if

if we make a leaf node here then the kd-tree is meaning-less, it simply degenerated into sequential traversal because the whole tree will only contain one leaf node.

so, is there any solution? thanks!

here is some definitions:

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 hope my poor english explained the question clearly...

Upvotes: 1

Views: 2034

Answers (1)

Dade916
Dade916

Reputation: 315

A KD-tree requires to store all objects crossing the splitting plane in both sub-trees. Your assumption that an object is stored in only one of the sub-tree is just not correct. The correct assertion is:

( nBelow + nShared + nAbove == nObjects )

This is one of the reasons why BVH is often superior to KD-Tree (i.e. BVH stores the objects in only one of the sub-trees because the sub-tree bounding boxes can overlap).

A split plane with many crossing objects will have an higher SAH cost (because crossing objects are counted 2 times) so KD-tree splitting code will still try to minimize the number of shared objects (but there will often some duplication).

Upvotes: 3

Related Questions