KD Tree

KD TreeThe KD Tree belongs to the topic algorithms and data structures. In this demo it is used to split the graphic scene into several parts and the objects, visualized as colored cubes, are stored in the leaves of the tree. With the help of this data structure it is possible to solve the nearest pair problem, which might be useful to find the nearest enemy or player in a computer game. But in the sample application here, the KD-Tree serves for something else, namely for collision detection. By pressing the Enter-Key it is possible to cast a ray (red) and then the nodes of the tree are searched for intersections. Finally only the objects in the leave nodes with intersections have to be checked for collisions with the ray. The hidden triangles are rendered in black. The same principle can be used for determining the visibility of objects.

The demo was developed with C# and XNA. The source code can be found on GitHub.