Building the KD Tree

[ LiB ]

Building the KD Tree

The next logical step is to actually implement this concept. You build a KD Tree by taking a large input list of points ( photons in this case) and partitioning them based on their positions in the world. The input point list is going to be the photon map array located in the PhotonMap class. The resulting effect after the algorithm takes its course yields a hierarchy of point lists (or point sets) that are partitioned by each other. See Figure 13.9 for an example.

Figure 13.9. An example of the hierarchy of point lists that partition each other.

There has been much research conducted on building KD Trees over the past few years . Typically, it's a simple process whereby each node in the tree is defined by a rectangle (in a 2D environment) or a plane (in a 3D environment). In a 3D environment, the plane in each node dictates the type of dimensional split that takes place. Again, the divisions are made along the world X, Y, and Z planes depending on a decision variable. When a node is selected to be the splitter and the subdivision takes place, the partitioning node creates two child lists that are partitioned in a left or right order. See Figure 13.10.

Figure 13.10. The partitioning nodes split space into two sides in left or right order.The hierar chy of point lists is composed of left and right photon divisions.

When a subdivision occurs, the space is split into two halves . For example, the first time a subdivision occurs the whole world is cut into two regions by a selected node. This means each side (or child of the parent node) will carry half the photons of the parent node. Thus, the division of two point-sets separated by one node is known as the median split . If you had a total of six points you would have a left and right list of three points each. After the first split is conducted the new children that are generated are subdivided into equal halves by planes on different dimensions. Then those children are subdivided with the same procedure until each point of the original list sits within its own leaf cell .

This process creates a hierarchy of points separated by median splits and sub-trees. The partitioning stops after O (Log ₂ N) levels. Note that in a 2D environment the cells of a KD Tree are rectangles, but in 3D they are volumes known as cubes. Cubes are also known as bounding boxes that encompass a series of objects in a specific volume. See Figure 13.11. The objects included within a bounding box can be points, photons, spheres, polygons, triangles , meshes, and the like. The subdivision of space using the KD Tree in a 3D environment involves subdividing one large cube into smaller cubes. Those smaller cubes (or volumes ) are then divided again until each point sits within only one cube. This is essentially what the 3D KD Tree subdivision algorithm does.

Figure 13.11. This is an exam ple of the splitting nodes (planes) that subdivide the space into smaller cubes using the 3D KD Tree spatial subdivision algorithm.

[ LiB ]