Hello!

I have been reading about kd-trees to improve my hit test algorithms performance and I have a couple of questions. For starters I want to build a tree by simply splitting the voxels in half (no SAH, that I will implement later). As I understand I first need to split the x axis (deph 1), then y axis (deph 2), z (deph 3), x(deph 4) and so on. Am I correct?
My kd tree node structure looks like this:


struct kdNode
{
QVector<triangle>triangles; //list of triangles in current voxel
kdNode* left;
kdNode* right;
};


Do I need something else?
And one last question: When I have the tree, how do I use it in ray tracing? Do I somehow need to check which voxel the ray touches and then find the voxel in the tree and check only the triangles that the voxel contains?

You don't necessarily need to cycle the directions. In that case, you'll need to store some info that will tell you what axis was used to split the node and any all cases you'll need the position of the splitting plane! The rest I don't have time to answer now, someone will.

You don't necessarily need to cycle the directions. In that case, you'll need to store some info that will tell you what axis was used to split the node and any all cases you'll need the position of the splitting plane! The rest I don't have time to answer now, someone will.

Thank you for your answer!

Ok here is my plan:

If I split the plane along the x-axis, then the normal for that plane would be: (1,0,0), y-axis (0,1,0), z-axis (0,0,1)...Am I correct?
I will determine if the triangles all on the right/left side of the plane with a simple test:

vertex1 . planeNormal
vertex2 . planeNormal
vertex3 . planeNormal

if all point are > 0 then triangle is in front, if < 0 then triangle is behind.

And how can I split the voxels without cycling through the axes.

You can always split along the longest axis of the bounding box.
Also if your planes are axis aligned you don't need to do a dot product you can just check the principle component of the axis.

Thanks!

Ok, when I have the tree, how exactly do I use it for ray tracing? Find ray intersection with all the voxels in the tree?
My structs:

struct boundingBox
{
vector3 maxPos;
vector3 minPos;
};

struct kdNode
{

QVector<triangle>trianglesInVoxel;
kdNode* leftVoxel;
kdNode* rightVoxel;
boundingBox bBox;
kdNode()
{
leftVoxel = NULL;
rightVoxel = NULL;
}

};

A big advantage of kD-trees (over BVH for example) is that you don't need to store the whole bounding box (that is 6 floats) but just a single float for the plane position (in case of implicit directions), or a single float and 2 bits for the plane direction/axis. You will not need to test your rays against the bounding box, just against the plane. Of course, each ray must be tested against the whole scene AABB, too.

A big advantage of kD-trees (over BVH for example) is that you don't need to store the whole bounding box (that is 6 floats) but just a single float for the plane position (in case of implicit directions), or a single float and 2 bits for the plane direction/axis. You will not need to test your rays against the bounding box, just against the plane. Of course, each ray must be tested against the whole scene AABB, too.

I have chosen a stack based traversal algorithm (Recursive Ray Traversal Algorithm) and I am having a little trouble understanding it.

Here is what I understand: I need to find a point where the ray enters the voxel (then calculate the distance ray origin and that point), where it exits (then calculate the distance between ray origin and that point), distance between ray origin and plane (in some papers I saw the formula: (splitPoint - rayOrigin[currentAxle])/rayOrientation[currentAxle] ....my ray orientation is (0,0,-1) and then in some cases I will be dividing with zero (x,y axis)...how can this be)? And in the init of the algorithem, the ray origin is in the main voxel, how do I get the distance where the ray enters the voxel? Do I understand this correct? Can someone explain?