# photon mapping, problem in building kd-tree

This topic is 3964 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Im experimenting with my own photon mapping implementation, but i soon came across a problem when advancing from casting photons, to building the kd-tree for them, and i've finnaly figured out why its happening. the problem is that kd-tree build should be pretty much constant time for the same number of items with othe parameters the same. the problem is that for example, in a cube, any photons are always going to be stored on one of the 6 faces, which means that every photon on each face has one coordinate exactly the same, which means that when it goes to build the kd-tree if it tries to split along this face it pretty much crashes, because of how i have the build function In my kd-tree implementation, for building the tree, what im doing is choosing the axis based on the dimensions of the current bounding box for that node, i then use an in-place quicksort to sort all the objects along that axis so that in sorting i can auomaticaly find the median by choosing the middle value, and then since the objects are all sorted, rather than having to split the objects into two seperate arrays for the next recursion, i can just pass the first half to one recursion, and the second half to the other. the problem from above with the cube, is that if it tries to split along one of the axis, because there are hundreds of thousands of photons all with the same coordinate component, when it goes to sort the objects with quick-sort it ends up going almost into an infinite loop since it starts with all the objects, then does one recursion, but because all the coordinates are the same almost along that axis, no matter how i choose the pivot object, the next recursion almost always ends up with 2 arrays of size 1, and the previous length - 1. the worst case scenario for the quick sort basicly which is making it tremendously slow going in the kd-tree builder. Any suggestions on how better to implement the kd-tree building to be able to deal with this well?

##### Share on other sites
well, i managed to fix the issue in a different way, by displacing photons by a small random amount from the surface so that for the cube instance, the photons are not all stored in 6 exact axial planes which did make it go much faster for the sorting of the objects.

however i'd still like to know what would be a better way to build the kd-tree from the photons than what i'm currently doing

##### Share on other sites
You say you choose which way to sort based on the bounding box. The best way to do this is to sort along the longest dimension of the bounding box. That way it will never be zero size.

1. 1
2. 2
3. 3
Rutin
19
4. 4
khawk
14
5. 5
frob
12

• 9
• 11
• 11
• 23
• 12
• ### Forum Statistics

• Total Topics
633659
• Total Posts
3013207
×