KD Tree

This section demonstrates how the creation of a KD Tree using the Surface Area Heuristics (SAH), can drastically improve performances when searching for an element. However, for my photon map that I am working on, I will have to use the median split method instead. Indeed SAH is very slow when operating on data sets as huge as photon maps (Millions of photons) .

BSP Tree

This video renders a scene using a BSP tree of triangles and without hardware depth test. The test happens in the software. At render time, given the eye position, the application figures out the order in which to traverse the tree such that objects further from the eye are render last. This algorithm requires some polygons to be split so that they are properly stored in the tree.

Hierarchical Occlusion Mapping (HOM)

HOM is a technique that tries to determine which objects are being occluded based on a hierarchy of buffers and some potential occluders. The buffers store some screen space information about the scene being rendered such as the pixels occupied buy the occluders and  their depth. This information is then used to determine if the objects are occluded or not. In the upper left hand corner you can see the various levels of the HOM (Red and black) and the DEB (shades of red, it represents the depth of the occluder).