I'm constructing kd trees for my raytracer, and I've only used spatial center heuristic, so I'm looking to improve this. I want to calculate the SAH. So, I've come up with the following algorithm (in my head): Before recursive function: calculate all triangles to the left or right of each possible split position (only triangles that are fully left or right, the other number is arrived at using total = straddling + left + right, therfore straddling = total - left - right); using this structure, send a left splitposition boundrary and right splitposition boundrary to the recursive construction formula. now, go through all the split positions, and calculate the SAH for every position within the left and right boundraries, using leftCount = currentPos.leftCount - leftBoundrary.leftCount, and the same for rightCount Finally, calculate SAH and determine everything else. Is there a more accepted of potentially faster way of doing this? This way, every node has to test to see if all the splitPositions are within the node, and calculate only for the positions that are in this node. Also, if I had a object consisting of a whole lot of triangles, this structure would take up alot of memory, right? If I use 1 float and two unsigned integers, thats 12 bytes, and it will be alligned to 16 bytes probably, so thats like 16 bytes * 30 000 000, so like 480 MB. Of course, it can be deleted, but that's alot of memory for just one function, if you had 30 000 000 polygons. Thanks for taking a peek.

If you have a 30 million triangles mesh then you have bigger problems. Not only do you have the cost of the kd-tree (which per-node could be 4 bytes if you are linearizing the tree or 8 bytes if you have a single explicit link), you also have to store the chosen triangle structure (Wald or Moller triangles or something else)

The SAH can be done the following way:
1. Sort the elements from min to max on the axis tested (NlogN)
2. Visit the list once, compute left, right, straddle for each element and compute cost
3. Return cost for each axis, choose the best axis, keep going recursively

For 30 million triangles it might be fairly slow, note that you can potentially multi-thread cost function for each axis.

Look for papers written by Ingo Wald, you need to be careful with axis aligned triangles, make sure you have a bonus heuristic for empty space and for perfect splits (no straddle), ompf.org is a good resource

I read some stuff by him. I will look into it and see what I get.

30 million triangles is a bit much, I am only testing with 60k to 1 million triangles, but I wanted to be able to eventually render some complex scenes.

Also, what is the performance impact of having an abstract base primitive class (I'm using c++). I understand there has to be a table lookup to find the correct function. Is there a huge overhead?

I'm not after crazy performance, this is after all just for my own amusement.

Be careful with the overhead, the best way to tell is by profiling the code. You will be spending most of your time inside kd-tree traversal, and a fraction on ray/primitive intersection, everything else should be minimal, so spend time optimizing where it matters

Just a Q: how would one sort triangles left to right? I'm confused.

Currently, I sort them either to the left or right for every single splitting position.

I'm sure there's a better way? It takes a long time (maybe 1 min) to determine all the left/right counts. It would be painfully obvious if no objects straddled the splitting position, but this is clearly not the case.

Thanks!

Quote:Original post by ldeej
Be careful with the overhead, the best way to tell is by profiling the code. You will be spending most of your time inside kd-tree traversal, and a fraction on ray/primitive intersection, everything else should be minimal, so spend time optimizing where it matters

I remember getting almost abysmal performance, or at least inconsistent performance before.

At small resolutions, I was still only getting 100 ms rendering times, with a plane and two spheres.

I have optimized since then, and also added kd-trees and meshes. I need to actually get SAH to work before I start again.

There is a downloadable kd-tree compiler on my site:
http://igad.nhtv.nl/~bikker , which emits the kd-tree as a text file.
You can use it to get an impression of reasonable performance. It's not the fastest kd-tree compiler in the world, but it comes pretty close. :)

Quote:Original post by solinent
Just a Q: how would one sort triangles left to right? I'm confused.

Currently, I sort them either to the left or right for every single splitting position.

I'm sure there's a better way? It takes a long time (maybe 1 min) to determine all the left/right counts. It would be painfully obvious if no objects straddled the splitting position, but this is clearly not the case.

Thanks!

It should work the following way:
1. Create an axis aligned bounding box for each triangle
2. For each split axis (x,y,z)
Sort the boxes in question on the chosen axis, choosing the start plane
At this point you have a list of boxes sorted on the given coordinate
3. Visit the list of boxes linearly
Initialize the number of elements on the right of the splitting plane to be equal to the number of boxes
For each start bounds +1 to the total count for the items on the left of the current splitting plane
For each end bounds -1 to the count of boxes to the right of the splitting plane
Find straddle by doing left+right-total
Compute SAH for the current split position

Choose every single start and end bounds as a possible split plane

Does it make sense?

I think so.

So I should have a structure to store the splitpositions simillar to the following:

struct SplitPosition {
float pos;
bool isStart;
};

Quote:
There is a downloadable kd-tree compiler on my site:
http://igad.nhtv.nl/~bikker , which emits the kd-tree as a text file.
You can use it to get an impression of reasonable performance. It's not the fastest kd-tree compiler in the world, but it comes pretty close. :)

I'll check it out :) (edit: I'm using linux, I'll check it out when I switch back to Windows, and when I've completed my kd-tree to get some idea of performance).

I'll also take a peek at the source, but I'll likely be overwhelmed, as you seem to be doing GI and alot of other stuffs in there.

Quote:Original post by solinent
I think so.

So I should have a structure to store the splitpositions simillar to the following:

struct SplitPosition {
float pos;
bool isStart;
};
...

Something like that, you also need the element index (or pointer or something) to make sure that you can actually build the left and right lists, then keep going recursively

This site might also help you:
http://www.pbrt.org/

The book referenced there has code for how to build the kd-tree, and luxrender might be another good resource