[ LiB ] |
After the KD Tree is constructed , you'll use it in the rendering process to find the nearest neighbor for the point of intersection. The general idea is to find the photons within a given volume for n amount of photons. Because the photon map is now constructed spatially it returns the relevant photons faster. The process for returning the nearest photons is as follows :
You know that the space was divided in a cube-like manner where cubes make up other cubes. The whole world sits within one big parent cube. All you need to do is find the right cube (or perhaps the neighboring cubes as well) in a specific cube (volume) to find the relevant photons.
You begin from the root of the tree and then search through each ele-ment respectively.
As the algorithm runs through a series of nodes in a specific area, a local photon pool is allocated with photons that are within a certain distance.
The maximum distance between points determines the dimension to search for next .
The input point is constantly tested with each splitting node, which means the search is branched down into the left or right subtree and the process begins once again.
[ LiB ] |