Sounds good.

I actually implemented some naive methods of SAH, but only increased marginally in performance.

I then scratched all my SAH code, and changed my code from only splitting the x axis (I made this so to understand the code beter), to splitting depth%3 axis (so 0 depth would be x, 1 y, 2 z, 3 x etc). It increased in speed dramatically (probably because average interseciton tests per pixel went from like 2000 or 1000 to 50 or 60.

Now SAH should reduce this to less than 10, but I'm still having trouble.

I'll look at the quoted resources.

I assume you've built a SAH -kd tree based raytracer? any specifics?

Again, thanks for the help. If you don't mind, I'll post my code here later in hopes that you'll be able to correct where I'm going wrong.

How do I linearly calculate ALL of the left and right counts of the split positions? Do I have to use a stack of some sort?

I think I understand, we can use the sorted list and calculate as we go and store left and right counts as we go.

Quote:Original post by ldeej

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

Wait, why do you need an element index? This isn't required for SAH, correct? This is required to determine the actual objects that intersect the left and right nodes (the actual objects, not the count), right?

I drew some stuff and now I almost fully understand the correct algorithm, so thanks! I still have to overcome how to reduce the list of splitting positions based on the chosen splitting position. Maybe just have a min, max like in quicksort and send that to the recursive tracer? Ideas are flowing now, thanks.

EDIT:
Could you look at this code and tell me if it will work:


I know this works for the simple cases I have visualized (involving three triangles), but will it work for everything else?

Obviously, I don't need to store the positions, Those places is where I'd calculate SAH and determine the cost. This is linear (well, quadratic because it tests every axis in this case, but we would no the axes in the implementation).