Object KDTree

Course: CS350 (Space Partitioning)
Used Tech: Self-made Native C++ and OpenGL engine.

This is a project I did for my CS350 class (Space Partitioning) at Digipen Bilbao. It showcases the use of an KDTree to have more precise collisions against an object.

It is truly a different approach to solve the same problem as the octree approach I used before, you can check it here.

The objects bounding volume is divided recursively in two sub volumes forming a tree. The dividing plane that divides each volume is axis aligned but can be aligned to any axis and cut the volume in any place.

In addition to the max number of levels there is an additional mechanism for the recursion to stop. This is that the cost of doing raw collisions against the geometry would be smaller than checking another level of the KDTree.

When a collision is tested it starts at the root node, if there is collision the children nodes are tested if not the recursion stops. If a leaf node is reached there is collision against the object, otherwise it is a miss.

Leave a Reply

Your email address will not be published. Required fields are marked *