Jump to content
  • Advertisement
Sign in to follow this  
luca-deltodesco

photon mapping, problem in building kd-tree

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!