Using the KD Tree Algorithm

[ LiB ]

Using the KD Tree Algorithm

A KD Tree is a spatial subdivision algorithm than can be used during orthogonal range searching. Before you learn about the KD Tree, take a look at Figure 13.4. You'll use these photons located in space and spatially subdivide them using the KD Tree algorithm.

Figure 13.4. A top view of photons situated in space and contained in the global photon map.

graphic/13fig04.gif


Try to partition the image so that you hierarchically deconstruct space into many smaller areas, known as cells . Again, the basic premise behind spatial subdivision is to limit the input search so that you search through the fewest objects (in this case, photons) in a specific area. The fewer the objects, of course, the faster the search and the faster the render. This means you need to subdivide the space so that every small area does not contain too many objects. This helps to find the closest set of relevant photons based on an input position (which is the point of intersection). You find the closest photons based on a position value by traversing (or searching) through the hierarchy of the KD Tree until you find a cell and sometimes the surrounding cells containing the nearest photons. The cell that contains the nearest photons is scanned until the relevant neighbors of the photon contribution method are identified.

NOTE

NOTE

The KD Tree algorithm is the perfect candidate for photon mapping because photons in the global pho- ton map are really points located in space with some extra information stored with them.

If you partition the space in the Figure 13.4 by half planes, each point is contained within its own cell, as shown in Figures 13.5 through 13.7. When you create a splitting node in a 2D environment, you can only split horizontally and vertically.

Figure 13.5. The first time a subdivision occurs,the photons in space are separated by a new splitting node.

graphic/13fig05.gif


Figure 13.6. The sec ond time a subdivision occurs,the photons in space are separated by another splitting node.

graphic/13fig06.gif


Figure 13.7. The third time a subdivision occurs,the photons in space are separated by yet another splitting node.

graphic/13fig07.gif


As you can see, each time the algorithm runs, it cuts the space into one of two dimensions with each cell containing only one point. Because this is a 2D example, it's very easy to convey the subdivisions because each cell is made up by a rectangle. Take a look at Figure 13.8 for an example of the new cells created based on point proximity.

Figure 13.8. The cells generated by the 2D KD Tree subdivision algo rithm.

graphic/13fig08.gif


Transforming the KD Tree into a 3D environment is very simple. All you need to do is simply take the third component of the splitting node into account when partitioning the space. Instead of splitting the partitioning point sets on the X and Y dimensions, the Z dimension is utilized as well.

[ 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