Quick KD-Tree Tutorial
This diagram came about as the result of yet another illuminating IRC chat with a random graphics coder in the UK. This guy was hashing out a KD-tree algorithm to use for collision detection in his class project, and needed help so he could make it to the club in time and get his slant on. I wasn't familiar with the KD-tree method, so he sent me some .PDF's to help out.
One hour later, I created this diagram to help explain the process (it turns out his code had some bad branching logic).
The algorithm implicitly encodes partitions of 3-space using orthogonal planes. Thus, it can be viewed as a minimal representation for BSP trees comprised of axis-aligned split planes.
The big difference is in how the partial order is defined on the tree. For a BSP-tree, the ordering is based on the distance of a point along the normal of the split plane. For a KD-tree, the ordering depends on what level of the tree we're looking at.
If you're still confused, just think of a KD-tree as a kind of binary search in N dimensions.