# SAH and kd trees

## Recommended Posts

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.

##### Share on other sites
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

##### Share on other sites
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.

##### Share on other sites
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

##### Share on other sites
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!

##### Share on other sites
Quote:
 Original post by ldeejBe 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.

##### Share on other sites
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. :)

##### Share on other sites
Quote:
 Original post by solinentJust 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?

##### Share on other sites
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.

##### Share on other sites
Quote:
 Original post by solinentI 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

http://www.pbrt.org/

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

##### Share on other sites
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.

##### Share on other sites
Quote:
Original post by ldeej
Quote:
 Original post by solinentI 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

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:
for (size_t axis=0; axis<3; axis++) {		size_t leftCount(0), rightCount=faceCount, straddleCount(0);		for (size_t i=0; i<faceCount; i++) {			if (splitPosition[axis][i].isLeft) {				straddleCount++;				rightCount--;				splitPosition[axis][i].rightCount = rightCount;				splitPosition[axis][i].leftCount = leftCount;				splitPosition[axis][i].straddleCount = straddleCount;			}			else {				//set equal, nothing changes except in the next position				splitPosition[axis][i].rightCount = rightCount;				splitPosition[axis][i].leftCount = leftCount;				splitPosition[axis][i].straddleCount = straddleCount;				//decrease it for the next iteration, and increase leftCount for the next iteration				straddleCount--;				leftCount++;			}		}	}

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).

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account

• ### Forum Statistics

• Total Topics
628345
• Total Posts
2982191

• 9
• 24
• 10
• 9
• 13