Searching the KD Tree

[ LiB ]

Searching the KD Tree

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 :

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

  2. You begin from the root of the tree and then search through each ele-ment respectively.

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

  4. The maximum distance between points determines the dimension to search for next .

  5. 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 ]


Focus On Photon Mapping
Focus On Photon Mapping (Premier Press Game Development)
ISBN: 1592000088
EAN: 2147483647
Year: 2005
Pages: 128
Authors: Marlon John

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net